高中数学联赛组合专题.docVIP

课程简介：全国高中数学联赛是中国高中数学学科的最高等级的数学竞赛，其地位远高于各省自行组织的数学竞赛。在这项竞赛中取得优异成绩的全国约90名学生有资格参加由中国数学会主办的“中国数学奥林匹克（CMO）暨全国中学生数学冬令营”。优胜者可以自动获得各重点大学的保送资格。各省赛区一等奖前6名可参加中国数学奥林匹克，获得进入国家集训队的机会。中小学教育网重磅推出“全国高中数学联赛”辅导课程，无论是有意向参加竞赛的初学者，还是已入围二试的竞赛选手，都有适合的课程提供。本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学教师李秋生等名师主讲，轻松突破你的数学极限！ 课程招生简章：/webhtml/project/liansaigz.shtml 选课中心地址：/selectcourse/commonCourse.shtm?courseeduid=170037#_170037_ 第二章　组合专题 ?　　一、重要的概念与定理　　1、完全图：每两个顶点之间均有边相连的简单图称为完全图,有个顶点的完全图（阶完全图）记为.　　2、顶点的度：图中与顶点相关联的边数（环按2条边计算）称为顶点的度（或次数）,记为.与分别表示图的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点.　　3、树：没有圈的连通图称为树,用表示,其中度为1的顶点称为树叶（或悬挂点）.阶树常表示为.　　4、部图：若图的顶点集可以分解为个两两不相交的非空子集的并,即　　　　并且同一子集内任何两个顶点没有边相连,则称这样的图为部图,记作. 2部图又叫做偶图,记为.　　5、完全部图：在一个部图中, ,若对任意均有边连接和,则称图为完全部图,记为.　　6、欧拉迹：包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹.　　欧拉图：包含欧拉迹的图为欧拉图. 欧拉图必是连通图.　　哈密顿链（圈）：经过图上各顶点一次并且仅仅一次的链（圈）称为哈密顿链（圈）.包含哈密顿圈的图称为哈密顿图.　　7、平面图：若一个图可画在平面上,即可作一个与同构的图,使的顶点与边在同一平面内,且任意两边仅在端点相交,则图称为平面图.　　一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面.　　8、竞赛图：有向完全简单图称为竞赛图.有个顶点的竞赛图记作.　　9、有向路：在有向图中,一个由不同的弧组成的序列,其中的起点为,终点为,称这个序列为从到的有向路（简称路）,为这个路的长,为路的起点,为路的终点.若,则称这个路为回路. 　　定理1 设是阶图,则中个顶点的度之和为边数的2倍.　　定理2 对于任意图,奇顶点的个数一定是偶数.　　定理3（Turan定理） 有个顶点且不含三角形的图的最大边数为.　　定理4 图为偶图,当且仅当中不含长度为奇数的圈.　　定理5 若树的顶点数,则中至少有两个树叶.　　定理6 若数有个顶点,则的边数.　　定理7 设是有个顶点、条边的图,则下列命题等价:　　⑴ 图是树; ⑵ 图无圈,且; ⑶ 图连通,且.　　定理8 阶连通图中以树的边数最少,且阶连通图必有一个子图是树.　　定理9（一笔画定理） 有限图是一条链或圈（可以一笔画成）的充要条件是是连通的,且奇顶点的个数为0或2. 当且仅当奇顶点个数为0时,连通图是一个圈.　　定理10 在偶图中,若,则一定无哈密顿圈.若与的差大于1,则一定无哈密顿链.　　定理11 设是阶简单图,且对每一对顶点有,则图有哈密顿链.　　定理12 设是阶简单图,且对每一对不相邻的顶点有,则图有哈密顿圈.　　定理13 设是阶简单图,若每个顶点的度,则图有哈密顿圈.　　定理14 若图有哈密顿圈,从中去掉若干个点及与它们关联的边得到图,则图的连通分支不超过个.　　定理15（欧拉公式） 若一个连通的平面图有个顶点、条边、个面,则.　　定理16 一个连通的平面简单图有个顶点、条边,则,对于连通的偶图,则有 .　　定理17 一个图是平面图当且仅当它不包含同胚于或的子图.　　定理18 设阶竞赛图的顶点为,则,且.　　定理19 竞赛图中出度最大的点称为“优点”,“优点”到其余各点都有长度不超过2的链.　　定理20 竞赛图中存在一条长为的哈密顿路.　　定理21 竞赛图中有一个回路是三角形的充要条件是有两个顶点 满足 .　　定理22（Ramsey定理） 任意2色完全图中必存在同色三角形. 　　二、例题选讲　　例1 、某天晚上21个人之间通了电话,有人发现这21人共通话102次,且每两人至多通话一次.他还发现,存在个人,第1个人与第2个人通了话,第2个人与第3个人通了话,……, 第个人与第个人通了话,第个人又与第1个人通了