《组合数学(3).docx》由会员分享，可在线阅读，更多相关《组合数学(3).docx（6页珍藏版）》请在三一文库上搜索。
1、组合几何(3)题型一覆盖定义 设G和F是两个平面图形.如果图形F或由图形F经过有限次的平移、 旋转、 对称等变换得到的大小形状不变的图形F上的每一点都在图形G上我们就说图 形G覆盖图形F;反之，如果图形F或F上至少存在一点不在G上，我们就说图 形G不能覆盖图形F.定义 对于图形G i,G2,，G “，假设图形F中的每一点都被这组图形中的某个 所覆盖，那么称这几个图形覆盖图形F 关于图形覆盖，下述性质是十清楚显的：(1) 图形G覆盖自身；(2) 图形G覆盖图形E,图形E覆盖图形F,那么图形G覆盖图形F. 定义 图形F中任意两点间的距离最大值d为图形F的直径.原那么1假设图形F的面积大于图形G的面
2、积，那么图形G不能覆盖图形F.原那么2直径为d的图形F不能被直径小于d的图形G所覆盖.1. 直径为1的图形F可被一个边长为的正三角形覆盖，试证明之.S的区域.求证:可以从中取出假设干个互2. 设平面上有有限个正三角形覆盖着面积为 不重叠的正三角形，使其覆盖面积大于S/16题型二极端原理和组合方法3. 平面上有n个红点与n个蓝点，任意三点都不共线.求证：可以用 n条线段连结这 2n个点，每条线段连结一个红点与一个蓝点，且这 n条线段没有公共点.题型三构造4 是否存在10个不同的整数，使得从中任选9个数，它们的和都是完全平方数?5. S是平面上n个不同的点组成的点集，S中任意两点距离的最小值为do
3、求证：存在一个S的由至少n/7个点组成的子集T, T中任意两点至少相距-Id6.在7X8的长方形棋盘的每个小方格的中心点各放一个棋子。如果两个棋子所在的 小方格共边或共顶点，那么称这两个棋子相连。现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线横、竖、斜方向上依次相连。问最少 取出多少个棋子才可能满足要求？并说明理由题型四格点及其性质皮克公式：格点多边形面积 二多边形一周的格点数 吃+多边形内部格点数-17设S是 n n的正方形，试证：S盖不住多于n 12个格点8.在7X 7的正方形方格表中，将k个方格的中心染成红点，使得其中任何4个红点都 不是一个边平行于网格线的矩形的
4、4个顶点，求k的最大值题型五组合求和9.设ai,aaJj|,an是1, 2,，n的一个排列，对于aj，假设满足：或者i=n，或者对于 一切j ij n有ai - aj那么称aj是此排列的一个“大数。设排列厂-印,|1, a* 中大数个数为r二，求S八r；题型六极值填数问题10 .是否存在自然数n使得n!的前4个数字为2021?图论(4)一、图的根本概念图：图G是指两个集合(V, E),集合V为图的顶点集，集合E为图的边集。|V 11 E | 均有限的图称有限图。有边相连的两顶点称为相邻。有些顶点本身有边相连，这样 的边称为环。假设联结两顶点的边不止一条，称这些边为平行边或重边。不含环和重 边的
5、图G称为简单图。对于两个图 G(V,E)和G(V,E)，如果V V,E E,就 称G是G的子图。有向图：每条边都是有向边的图。无向图：每条边都是无向边的图。出度：与顶点v相连的边数称为该顶点的 度数，记为d (v)，以该定点为始边的边数 为出度，记为d + (v)。入度：以该定点为终边的边数为入度，记为 d-(v)。无向完全图：无向图中如果任何两点都有一条边关连那么称此图是无向完全图。记为Kn完全有向图：有向图中如果任意两点都有方向相反的有向边相连称此图为完全有向 图。(n阶有向完全图的边数为n2;无向完全图的边数为n(n-1)/2 。)定理1设图G是具有n个顶点m条边的无向图，其中点集 V二
6、v1,v2,w刀 d (vi)=2m定理2在无向图中，度数为奇数的顶点个数为偶数1 某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次求证： 必有6场比赛，其12个参赛者各不相同2.某俱乐部共有100名成员，每个成员都声称只愿意和自己认识的人一起打桥牌。 每个成员至少认识67名成员。求证：一定有4名成员，他们可以一起打桥牌二、树链：由不同的边组成的序列。圈：如果链中始点与终点相同可达：在图G中如果存在一条v到d链那么称从v到d是可达。连通：在无向图中如果任意两点是可达的，称为连通的。树：一个连通且没有圈的图称为树；树上度为 1的点称为悬挂点 定理3假设树T顶点数?2，那么T至少有
7、两个悬挂点定理4顶点数为n的树边数e=n-13. 某区居民共有 1990 人,每天他们之中每个人把昨天听到的消息告诉给他认识的人 知道,而且任何消息到最后一定能让全区居民知道 .试证:可以指定 180 个居民,使得同 时向他们报导某一消息后 ,至多经过 10 天,这一消息全部的人都会知道三、欧拉图欧拉图 ：如果图中存在一条通过图中每条边一次且仅一次的圈， 那么称此圈为欧拉圈， 具有欧拉圈的图称为欧拉图。 欧拉链： 如果图中存在一条通过图中各边一 次且仅一次的链，那么称此链为欧拉链，具有欧拉链的图称为半欧拉图。一笔画定理 ：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数；一个 无向连通图
8、是半欧拉图的充要条件是图中至多有两个奇数度点。四、平面图平面图 ：一个图能画在平面上，使得它的边仅在端点相交欧拉定理：如果一个连通的平面图 G有v个顶点，e条边，f个面，那么v-e+f=2(由欧拉定理f 2e/3,e 3)中有一个圈是三角形的充分必要条件是有两个顶点的出度 相等5在象棋赛中，每两个选手都要赛一场。求证：可以给所有的选手编号，使得无论 哪个选手都没有输给紧接其后编号的选手六、博弈对策胜局：先走者有必胜策略的状态负局：后走者有必胜策略的状态胜负局性质：(1) 对胜局A必存在一种操作方式，使状态 A操作一次后只能得到一个负局(2) 对负局B,无论博弈者如何操作，对状态 B操作一次后只能得到一个胜局6一副扑克牌共 54 张，甲、乙依次从中任取 1 张、或 2 张、或 3 张，谁取到最后 一张谁就获胜， 先取者必胜的策略是什么？如果改成 52 张牌，先取者必胜的策略又 是什么？如果取到最后一张牌的人输，先取者的必胜策略，又是什 么？