[组合数学3.doc

组合几何（3） 题型一 覆盖 定义? 设Ｇ和Ｆ是两个平面图形．如果图形Ｆ或由图形Ｆ经过有限次的平移、旋转、对称等变换得到的大小形状不变的图形Ｆ′上的每一点都在图形Ｇ上．我们就说图形Ｇ覆盖图形Ｆ；反之，如果图形Ｆ或Ｆ′上至少存在一点不在Ｇ上，我们就说图形Ｇ不能覆盖图形Ｆ．定义? 对于图形Ｇ１，Ｇ２，…，Ｇｎ，若图形Ｆ中的每一点都被这组图形中的某个所覆盖，则称这几个图形覆盖图形Ｆ关于图形覆盖，下述性质是十分明显的： （１）?? 图形Ｇ覆盖自身； （２）?? 图形Ｇ覆盖图形Ｅ，图形Ｅ覆盖图形Ｆ，则图形Ｇ覆盖图形Ｆ． 图形Ｆ中任意两点间的距离最大值ｄ为图形Ｆ的直径．原则１? 若图形Ｆ的面积大于图形Ｇ的面积，则图形Ｇ不能覆盖图形Ｆ． 原则２? 直径为ｄ的图形Ｆ不能被直径小于ｄ的图形Ｇ所覆盖． 直径为１的图形Ｆ可被一个边长为的正三角形覆盖，试证明之．设平面上有有限个正三角形覆盖着面积为S的区域.求证:可以从中取出若干个互不重叠的正三角形,使其覆盖面积大于S/16d 6．在7×8皮克公式格点多边形面积=多边形一周的格点数÷2+多边形内部格点数-1的正方形，试证：S盖不住多于个格点 8．在7×7的正方形方格表中，将k个方格的中心染成红点，使得其中任何4个红点都不是一个边平行于网格线的矩形的4个顶点，求k的最大值 题型五 组合求和 9．设是1，2，…，n的一个排列，对于，若满足：或者i=n，或者对于一切j（ij≤n）则称是此排列的一个“大数”。设排列中大数个数为，求 题型六 极值填数问题 10．是否存在自然数n使得n！的前4个数字为2009？ 图论（4） 一、图的基本概念 图：图G是指两个集合(V，E)，集合V为图的顶点集，集合E为图的边集。均有限的图称有限图。有边相连的两顶点称为相邻。有些顶点本身有边相连，这样的边称为环。若联结两顶点的边不止一条，称这些边为平行边或重边。不含环和重边的图G称为简单图。对于两个图，如果，就称是的子图。 有向图：每条边都是有向边的图。 无向图：每条边都是无向边的图。 出度：与顶点相连的边数称为该的度数，以该定点为始边的边数为出度。 入度：以该定点为终边的边数为入度。 无向完全图：无向图中如果任何两点都有一条边关连则称此图是无向完全图。完全有向图：有向图中如果任意两点都有方向相反的有向边相连称此图为完全有向图。 n阶有向完全图的边数为n；无向完全图的边数为n(n-1)/2。 定理 设图G是具有n个顶点m条边的无向图，其中点集V={v,v2,…,vn} ∑d (vi)=2m 定理2 在无向图中，度数为数的顶点个数为偶数某地区网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次．求证：必有6场比赛，其12个参赛者各不相同。 ：如果中始点与终点相同。 可达：在图G中如果存在一条v到d则称从v到d是可达。 连通：在无向图中如果任意两点是可达的，连通的。  三、欧拉图 欧拉图 如果图中存在一条通过图中边一次且仅一次的，则称此为欧拉，具有欧拉的图称为欧拉图。 欧拉如果图中存在一条通过图中各边一次且仅一次的，则称此为欧拉，具有欧拉的图称为半欧拉图。 定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。）图：有向图图。 哈密顿图：如果图G中存在一条通过图G中各个顶点一次且仅一次的，则称此为图的哈密顿；具有哈密顿的图称为哈密顿图。 图存在长为n-1的哈密顿路 定理8 竞赛图（n≥3）中有一个圈是三角形的充分必要条件是有两个顶点的出度相等 5．在象棋赛中，每两个选手都要赛一场。求证：可以给所有的选手编号，使得无论哪个选手都没有输给紧接其后编号的选手 六、博弈对策 胜局：先走者有必胜策略的状态 负局：后走者有必胜策略的状态 胜负局性质： 对胜局A必存在一种操作方式，使状态A操作一次后只能得到一个负局 对负局B，无论博弈者如何操作，对状态B操作一次后只能得到一个胜局 6．一副扑克牌共54张，甲、乙依次从中任取1张、或2张、或3张，谁取到最后一张谁就获胜，先取者必胜的策略是什么？如果改成52张牌，先取者必胜的策略又是什么？如果取到最后一张牌的人输，先取者的必胜策略，又是什么？