数学竞赛：图论讲义
大连市第二十四中学 邰海峰
重要的概念与定理
完全图 每两个顶点之间均有边相连的简单图称为完全图,有n个顶点的完全图(n阶完全图)记为Kn.
顶点的度 图G中与顶点v相关联的边数(环按2条边计算)称为顶点v的度(或次数),记为
d(v).?(G)与?(G)分别表示图G的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为
偶数的顶点称为偶顶点.
树 没有圈的连通图称为树,用T表示,其中度为1的顶点称为树叶(或悬挂点).n阶树常表示为Tn.
k部图 若图G的顶点集V可以分解为k个两两不相交的非空子集的并,即
k V?i?1Vi,ViVj??(i?j)
并且同一子集Vi(i?1,2,,k)内任何两个顶点没有边相连,则称这样的图为k部图,记作
G?(V1,V2,,Vk;E). 2部图又叫做偶图,记为G?(X,Y;E).
,Vk;E)中,Vi?mi(i?1,2,完全k部图 在一个k部图G?(V1,V2,,k),若对任意
vi?Vi,vj?Vj,(i?j,i,j?1,2,,k)均有边连接vi和vj,则称图G为完全k部图,记为
Km1,m2,,mk.
欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹. 欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图.
哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图.
平面图 若一个图G可画在平面上,即可作一个与G同构的图G?,使G?的顶点与边在同一平面内,且任意两边仅在端点相交,则图G称为平面图.
一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面.
竞赛图 有向完全简单图称为竞赛图.有n个顶点的竞赛图记作Kn. 有向路 在有向图D?(V,U)中,一个由不同的弧组成的序列u1,u2,,un,其中ui的起点为
vi,终点为vi?1(i?1,2,,n),称这个序列为从v1到vn?1的有向路(简称路),n为这个路的长,v1为
路的起点,vn?1为路的终点.若v1?vn?1,则称这个路为回路.
定理1 设G是n阶图,则G中n个顶点的度之和为边数的2倍. 定理2 对于任意图G,奇顶点的个数一定是偶数.
?n2?定理3(Turan定理) 有n个顶点且不含三角形的图G的最大边数为??.
?4?定理4 图G为偶图,当且仅当G中不含长度为奇数的圈. 定理5 若树T的顶点数…2,则T中至少有两个树叶.
定理6 若数T有n个顶点,则T的边数e?n?1.
定理7 设T是有n个顶点、e条边的图,则下列命题等价:
⑴ 图T是树; ⑵ 图T无圈,且e?n?1; ⑶ 图T连通,且e?n?1. 定理8 n阶连通图中以树的边数最少,且n阶连通图必有一个子图是树.
定理9(一笔画定理) 有限图G是一条链或圈(可以一笔画成)的充要条件是G是连通的,且奇顶点的个数为0或2. 当且仅当奇顶点个数为0时,连通图G是一个圈.
定理10 在偶图G?(V1,V2;E)中,若V1?V2,则G一定无哈密顿圈.若V1与V2的差大于1,则G一定无哈密顿链.
定理11 设G是n(n…3)阶简单图,且对每一对顶点v,v?有d(v)?d(v?)…n?1,则图G有哈密顿链.
定理12 设G是n(n…3)阶简单图,且对每一对不相邻的顶点v,v?有d(v)?d(v?)…n,则图
G有哈密顿圈.
定理13 设G是n(n…3)阶简单图,若每个顶点的度d(v)…,则图G有哈密顿圈. 定理14 若图G有哈密顿圈,从G中去掉若干个点v1,v2,则图G?的连通分支不超过k个.
定理15(欧拉公式) 若一个连通的平面图G有v个顶点、e条边、f个面,则v?f?e?2. 定理16 一个连通的平面简单图有v个顶点、e条边,则e?3v?6,对于连通的偶图,则有e?2v?4.
定理17 一个图是平面图当且仅当它不包含同胚于K5或K3,3的子图. 定理18 设n阶竞赛图Kn的顶点为v1,v2,n2,vk及与它们关联的边得到图G?,
,vn,则?d(vi)??d?(vi)??i?1i?1nnn(n?1),且2?[di?1n?(vi)]??[d?(vi)]2.
2i?1n定理19 竞赛图中出度最大的点称为“优点”,“优点”到其余各点都有长度不超过2的链. 定理20 竞赛图Kn中存在一条长为n?1的哈密顿路.
定理21 竞赛图Kn(n…3)中有一个回路是三角形的充要条件是有两个顶点v,v?满足
?). d?(v)?d?(v
定理22(Ramsey定理) 任意2色完全图K6中必存在同色三角形.
例题选讲
例1 某天晚上21个人之间通了电话,有人发现这21人共通话102次,且每两人至多通话一次.他还发现,存在m个人,第1个人与第2个人通了话,第2个人与第3个人通了话,……, 第m?1个人与第m个人通了话,第m个人又与第1个人通了话,他不肯透露m的具体值,只说m是奇数.求证: 21个人中必存在3人,他们两两通了话.
证：用21个点表示21个人,若两人通电话则对应两点连一条边,构成图G.由已知,G中存在一个长度为m的奇圈.要证: G中存在三角形.
设图G中长度最短的奇圈为C,长度为2k?1. 若k?1,则C为三角形. 若(1剟i,jk…2,设
C为
v1v2v2k?1v1,则
vi与
vj之间无边
2k?1,j?j??1(mod2k?1)),否则,若vi与vj相邻,则圈v1v2vivjv2k?1v1与圈
vivi?1vjvi长度之和为2k?3,故其中必然有一个长度小于2k?1的奇圈,与C最短矛盾.
假设除v1,v2,,v2k?1外的21?(2k?1)?20?2k个点无三角形,由Turan定理,它们至多连
?(20?2k)2??(10?k)2条边. 又其中任意一点不与C的相邻两点相邻(否则存在三角形),了??4??所以它至多与C中k个点相邻.
故总边数为2k?1?k(20?2k)?(10?k)
?100?2k?1?k?102?(k?1)?102?(2?1)?101(
2222k…2).
与图G共有102条边矛盾. 故图G中存在三角形,即存在三个人两两通话.
例2 45个校友聚会,在这些人中,任意两个熟人数目相同的校友互不认识.问在参加校友聚会的所有人中,熟人最多的人的数目最多是多少?
解: 用45个点表示45个人,若两人认识,则对应两点间连一条边,得图G?(V,E).设共有m个人熟人最多,每人有t个熟人,这些人对应的点构成集合X,其余的人对应点构成集合Y,显然XY?V,XY??.
由题意知,X中任何两点不相邻,且d(vi)?t,(i?1,2,,m),G中各顶点的度的最大值
?(G)?t.下面证明:m?22.
若m…23,则X中至少有23个点,每点的度为t,且任意两点不相邻,则从X中发出的另一
端是Y中点的边共有23t条,而Y?22.所以,Y中至少有一个点的度大于t,与?(G)?t矛盾.
当m?22时,构造完全偶图G?K22,23,满足题意. 故熟人最多的人数最多为22人. 例3 在17名科学家中，每人都和其它人通信．在他们的通信中只讨论三个题目．而且任意两名科学家通信时，只讨论一个题目．证明，其中至少有三名科学家，他们相互通信时，讨论的是同一个题目．
证: 用顶点代表科学家,两人相互通信则连上一条边.若两人在通信中讨论第i(i?1,2,3)个题目,则在此边上染上第i种颜色. 在这个三色完全图K17中,任取一个顶点, 从它出发的16条边中，至少有染上某一种颜色(设为第i种颜色)的边的数目不小于6．从其中取出6条第i种颜色的边,如果这些边的另一端点所构成的子图K6中含第i色边，这就构成第i色三角形. 否则,K6就是两色完全图,由Ramsey定理知，其中必有单色三角形．这就是说，有三位科学家在通信中讨论的是同一题目．证毕．
例4 设n个新生中,任意3个人中有2个人互相认识,任意4个人中有2个人互不认识,求n的最大值.
解: 所求n最大值为8.n?8时,如右图,其中A1,A2,,A8表示8名学生, A1 A2 A3
两点相邻当且仅当两人认识.
A8 下面设n个学生满足题设要求,证明n?8.为此,先证明如下两种情况 不可能出现.
⑴若某人A至少认识6个人,记为B1,B2,A7 ,B6.由Ramsey定理知,
A4
这6个人中或存在3个人互不认识(与已知任意3个人中有2个人互相认识 A6 A5 矛盾),或存在3个人互相认识,这时,A与这3个人共4个人两两互相认识, 与已知矛盾.
⑵若某人A至多认识n?5个人,则剩下至少4个人均与A互不认识,从而,这4个人两两认识,与已知矛盾.
10时,⑴与⑵必有一种情况出现,故此时n不满足要求. 当n…当n?9时,要使⑴与⑵都不出现,则此时每个人恰好认识其他5个人,于是,这9个人产生的“朋友对”的数目为
9?5?N,矛盾. 2由上述讨论知,n?8.
综上,n的最大值为8.
例5 设n(n?3)是整数, 在一次会议上有n位数学家,每一对数学家只能用会议规定的n种办公语言之一进行交流,对于任意3种不同的办公语言,都存在3位数学家用这3种语言互相交流.求所有可能的n,并证明你的结论.
证:当n位奇数时,结论成立.
原命题等价于将完全图Kn的边染以n种颜色之一,使得对于任意3种颜色,都存在3个顶点,它们相互所连的边为这3种颜色.由于n种颜色有Cn种选取方法,而顶点也有Cn种选取方法,这就意味着每3个顶点相连的边一定被染为确定的3种颜色,不能染为其他情况的颜色,反之亦然.
特别地,对于每一个三角形其3条边为3种不同颜色.
固定颜色S,恰好有Cn?1个三角形,其有一条边为颜色S,而颜色为S的边可以与其他n?22Cnn?1?1?个顶点构成n?2个三角形.于是,有条边被染为颜色S.所以,n不能为偶数. n?22233当n为奇数时,将n个顶点分别记为顶点1,2,,n,n种颜色记为S1,S2,,Sn,连结顶点i,j的边染为颜色St,其中t?i?j(modn).则对于任意3种颜色St1,St2,St3,有同余方程组
?i?j?t1(modn)??j?k?t2(modn). 利用消元法,可得在?1,2,?k?i?t(modn)3?,n?内有唯一的解(i,j,k),且i,j,k互不
相同. 所以,对于任意3种颜色,存在唯一的三角形,其3条边的颜色为这3种颜色.
例6 一个元素都是0或1的方阵称为二进制方阵. 若二进制方阵其主对角线（左上角到右下角的对角线）以上（不包括主对角线）的元素都相同，而且主对角线以下（不包括主对角线）的元素也相同，则称它为一个“好方阵”. 给定正整数m. 证明：存在一个正整数M，使得对任意正整数n?M和给定的n?n二进制方阵An,可选出整数1剟i1?i2??in?mn，从An中删除第
i1,i2,,in?m行和第i1,i2,,in?m列后所得到的二进制方阵Bm是“好方阵”.
证:记An中第i行，第j列的元素为ai,j，Kn表示n阶完全图. 我们对Kn的边按如下方式染色：对于连接顶点i,j(1剟i?jn)的边
⑴ 若ai,j?aj,i?0，则染红色； ⑵ 若ai,j?0,aj,i?1，则染绿色； ⑶ 若ai,j?1,aj,i?0，则染蓝色； ⑷ 若ai,j?aj,i?1，则染白色.