2-6数学竞赛中的图论问题（P ．221）一、基本思想引例欧拉7桥问题把所考察的对象作为顶点（v ），把对象之间是否具有我们所关心的某种关系作为了连线的的条件（e ），这样，就可以把一个具体问题抽象为图的研究．在解数学竞赛题中的好处：（1）把抽象的问题转化为直观的问题；（2）把复杂的逻辑关系转化为简明的数量关系．二、基本内容有图、顶点、边、简单图、完全图、连通图、树、二分图、竞赛图等14个定义，12条定理：定义１ 设集合{}12(),,,p V G v v v =≠∅ ，{}12(),,,q E G e e e = 是()V G 中某些元素对的无序集合，则称()()(),G V G E G 为图，又称()V G 为图G 的顶点集合，其元素叫做顶点；称()E G 图G 的边集合，其元素叫做边．若(),u v V G ∈，边e 是无序顶点对(),u v ，则记e uv vu ==，且称u 与v 是边e 的端点，e 与顶点,u v 关联，也说顶点u 与v 邻接（或相邻）．有公共端点的边12,e e 称为邻边，也说12,e e 邻接．例如顶点：()V G =｛小王，小李，小张，小赵，小陈，小刘｝， 边：1e =｛小王，小李｝，2e =｛小李，小赵｝，3e =｛小陈，小刘｝ ， 12,e e 相邻.定义2 图G 中所含顶点的数目称为图的阶数，记为V （也用G 来表示）；又用E 表示图G 的边数（也用G 来表示）．通常用(),G p q 表示p 个顶点，q 条边的图G ；若,p q 都是有限数的图称为有限图，否则称为无限图．如果对于图(),G V E 与()''',G V E ，有'',V V E E ⊆⊆，则称'G 是G 的子图．定义 3 两顶点间至多连一条边且每边的两个端点相异的图称为简单图；图中任何两个顶点都邻接的简单图称为完全图，p 阶完全图记为.p K定理1 p K 的边数为()12p p E -=． 定义４ 图G 中与顶点u 关联的边数称为顶点u 的度，记为()d u ．如果u 的度数是奇数，则称u 为奇顶点；如果u 的度数是偶数，则称u 为偶顶点．定理２ 任何一个图的总度数等于边数的2倍，()2u Vd u E ∈=∑．推论 任何图中奇顶点的个数是偶数．定义５ 图G 中点边交错的非空有限序列011231k k k u e u e u u e u - 叫做以0,k u u 为端点的途径．若途径中所有的i e 都不相同，则叫做0k u u -链；若链中所有的i u 都不相同则叫做0k u u -通路，k 称为通路的长；若0,k u u 重合，则叫做回路或圈．k 为奇（偶）数的回路称为奇（偶）回路．定义６ 经过图G 中每条边的链称为欧拉链，两端重合的欧拉链称为欧拉环游图（欧拉回路），有欧拉环游的图称为欧拉图（简称E 图）直观的说，欧拉图就是从一个顶点出发而每边通过一次又能回到出发顶点的图（一笔画）．定理3 连通图G 为欧拉图的充要条件是G 中没有奇顶点． 推论 如果连通图G 有2k 个奇顶点，那么图G 可以用k 笔画成．定义７ 包含图G 每一个顶点的通路称为哈密尔顿通路，有哈密尔顿通路的图称为哈密尔顿图．定理4 设G 是一个p 阶简单图()3p ≥，若G 中任意两个顶点,u v 的度数满足()()d u d vp +≥，则G 是哈密尔顿图． 定义８ 连通而无回路的图称为树，树上度数为1的顶点称为叶（悬挂点）．定理5 如果树T 的顶点数不小于2，那么树T 上至少有两个叶．定理6 设图G有p个顶点，q条边，则下列说法彼此等价：（1）G是树；（2）G的任意两个顶点间有且仅有一条通路；（3）G连通，且1=-；q p（4）G无回路，且1=-；q p（5）G无回路，但连接任何两个非邻接顶点,u v所得新图，有且仅有一个回路；（6）G连通，但舍弃任何一条边后便不连通．定义9 图()G V E的顶点集V若能分成两个非空子集12,V V，,使得任何边e的一个端点属于V，另一个端点属于2V，则G为1二分图．定理7 图G为二分图的充要条件是G不含奇回路．定义10 设图()G V E为简单图，M是E的一个非空子集，,若M中任何两边都不相邻，则称M为图G的一个匹配（又称对集）．若M边之端点包括G中一切顶点，则称M为G的一个完备匹配．M中每一边的两个端点称为相配．定义11 在图的边上用箭头标注出方向就得到一个有向图，称为定向．完全图的一个定向称为竞赛图．定理8 每个竞赛图都有单向哈密尔顿通路．定义12 若一个图G可以画在平面上，使得任何两条边都不在非顶点处相交，则称图G为平面图．图的边所包围的一个区域，其内部既不包含图的顶点，也不包含图的边，这样的区域为图G 的一个面．为了方便，把平面图G 的外部无限区域也作为一个面，称为外部面，其他面则称为图G 的内部面．定理9 设G 是一个简单连通平面图，()(),V G p E G q==，面数为f （包括外部面），则2p q f -+=． 定理10 一个连通的平面简单图G ，若有v 个顶点()3,v e ≥条边，则36e v ≤-．定义13 用红蓝两种颜色对完全图p K 的边任意染色，使每条边都染上某一种颜色，若总会出现红色边m K 或蓝色边n K 时，则记p 的最小值为(),r m n ，称(),r m n 为关于,m n 的拉姆赛数．定理11 ()()()()()3,36,3,49,3,514,3,618,3,723,r r r r r ===== ()3,936,r =()4,418.r =定义14 用n 种颜色对完全图p K 的边任意染色，使每条边都染上某一种颜色，若总会出现同色三角时，则记p 的最小值为()3,3,,3n r个，简记为n r ，称n r 为拉塞姆数． 定理12 设12,,,n S S S 是集合{}1,2,,n r 的任意分划，则存在一个,1n i i r ≤≤，使i S 中有方程x y z +=的根．三、主要方法不是图论知识的直接套用，而是图论基本思想的常识应用．构造法、反证法数学归纳法抽屉原理染色方法极端原理四、例题选讲例1-1 有5个课外活动小组，每2个小组里有一个相同的同学，每个同学恰好在两个小组里出现，问这5个小组里共有多少个同学？解 把小组对应为点，“每2个小组里有一个相同的同学”就连一条线，每两点都有连线；又由于“每个同学恰好在两个小组里出现”，故每两点都连且只连一条线，得5阶完全图，图中变的条数就是同学个数，得10个同学.例1-2 有n 个药箱，每两个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问共有多少种药？解 把药箱对应为点，“两个药箱里有1种相同的药”就连一条线，每两点都有连线；又由于“每种药恰好在两个药箱里出现”，故每两点都连且只连一条线，得（n 阶完全图）2n N C ．例2 证明：在任何一群人中，与奇数个人互相握手（互相认识）的人有偶数个．证明 记这群人为n 个点，“互相握手”就在对应的两点连一条线，共有e 条，每个人认识的人数为点的“度数”，记为12,,,n d d d ，则122n d d d e +++= ，2i i d d e +=∑∑奇偶，2i i de d =-∑∑奇偶为偶数 id ∑奇是偶数个奇数之和．例3-1 (1947，匈牙，例2-4-1）证明：在任意6个人中，总可以找到3个人互相认识，或互相不认识，并且这种情况至少出现2个．例3-2 （1976，波兰）平面上有6个点，任何3点都是一个不等边三角形的顶点，则这些三角形有一个的最短边又是另一个三角形的最长边．提要：把每个三角形的最短边染成红色，存在红色三角形，红色三角形的最长边为所求．例4 在边二染色的K 5中没有单色三角形的充要条件是它可分解为一红一蓝两个圈，每个圈恰由5条边组成．证明 充分性是显然的．考虑必要性，在K 5中每点恰引出4条线段，如果从其中某点A 1能引出三条同色线段A 1A 1，A 1A 3，A 1A 4，记为同红，则考虑△A 2A 3A 4，若当中有红边i j A A （24i j ≤≤≤），则存在红色三角形1i j A A A 是同蓝色三角形，均无与单色三角形矛盾．所以，从每点引出的四条线段中恰有两条红色两条蓝色，整个图中恰有5条红边、5条蓝边． 现只看红边，它们组成一个每点度数都是2的偶图，可以构成一个或几个圈，但是每个圈至少有3条边，故5条红边只能构成一个圈，同理5条蓝边也构成一个圈． 例 5 求最小正整数n ，使在任何n 个无理数中，总有3个数，其中每两数之和都仍为无理数．解 取4个无理数，显然不满足要求，故5n ≥． 设,,,,a b c d e 是5个无理数，视它们为5个点，若两数之和为有理数，则在相应两点间连一条红边，否则连一条蓝边．这就得到一个二染色5k ．只须证图中有蓝色三角形，分两步：（1）无红色三角形．若不然，顶点所对应的3个数中，两两之和均为有理数，不妨设,,a b b c c a +++都是有理数，有1[()()()]2a ab bc c a =+-+++ 但无理数≠有理数，故5k 中无红色三角形．（2）有同色三角形，若不然，由上例知，5k 中有一个红圈，顶点所对应的5个数中，两两之和均为有理数，设,,,,a b b c c d d e e a +++++为有理数，则1[()()()()()]2a ab bc cd de e a =+-+++-+++ 但无理数≠有理数，故5k 中无5条边组成的红圈，从而有同色三角形．这时，同色三角形必为蓝色三角形，其顶点所对应的3个无理数，两两之和仍为无理数．综上所述，最小的正整数5n =.例6-1 某足球邀请赛有,,,A B C D 4个城市参加，每市派出红黄两支球队，根据比赛规则，每两之间球队至多赛一场，并且同一城市的两支球队之间不进行比赛.比赛若干天后进行统计，发现除A 市红队外，其他各队比赛过的场次各不相同.问A 市黄队赛过多少场.（找黄队，求c 场次）解 因为“同一城市的两支球队之间不进行比赛”，所以每一个球队最多赛6场；有因为“除A 市红队外，其他各队比赛过的场次各不相同”，所以，其他各队赛过的场次分别为0，1，2，3，4，5，6共7种情况.用12345678,,,,,,,A A A A A A A A 表示8支球队，两队之间进行了比赛就连1条边，其中1234567,,,,,,A A A A A A A 分别赛了6，5，4，3，2，2，1，0场.由于1A 赛了6场，应有6条引线，记为121314151617,,,,,A A A A A A A A A A A A ，由于1A 与8A 没有引线，故1A ，8A 属于同一城市.同理， 27,A A 属于同一城市， 36,A A 属于同一城市，45,A A 属于同一城市.45,A A 属于同一城市且都赛过3场，由于“除A 市红队外，其他各队比赛过的场次各不相同”，所以45,A A 就是A 市的两支球队，得A 市黄队赛过3场.例6-2 李明夫妇最近参加了一次集会，同时出席的还有三对夫妻．一见面，大家互相握手，当然夫妻之间不握手，也没有人与同一个人握两次从手．握手完毕后，李明统计了包括妻子在内的7个人握手的次数，发现恰好数字发互不相同．请问．李明的妻子握了几次手?例6-3 （P.225例2-115）作业：1 习题2-6第12．习题2-6第11题（P．235）。
