第十一讲组合数学之基本图论模块一、基础知识图是由顶点和边构成的。图的子图是这个图的某些点和这些点间的某些边构成的。简单图：图中没有边的两端
点是同一点，且两点之间最多连一条线。完全图：简单图中能连上的边都连上。某点的相邻点：与该边有边相连的点。次数或度数：一个点有多少条
边与之相连。回路：一系列边首尾相连，最后连成一个圈。树：无圈的简单图。偶图：一个图的所有点都可以分成两个集合，所有的边都在它们之间
相连，它们内部没有边。平面图：能把所有边在平面上画出来且不交叉的图。有向图：边是有方向的，可以分起点和终点。如无特别说明，讲义中提
到的都是无向图。有向图的入度为有多少条的终点是它，出度的定义为多少条边的起点是它。例1．一个网球俱乐部的20位成员已经安排了14场
单打比赛，其中每个成员至少参加1场比赛。求证：在这种安排中，必有6场比赛是在12名不同选手之间进行的。解：用20个点表示20位成员
，14条边表示安排的14场比赛，得到一个图G，由题意，每个点的度数大于等于1，由握手定理知道d(1)+d(2)+d(3)+……+d
(20)=2×14=28，现在删去每个点的“d(i)?1”条边，那么去掉的边数不超过28?20=8，所以剩下的边至少有6条，且
剩下的图中每个点的“度”都小于等于1，所以这6场比赛中参赛的选手都不相同，是在12名不同的选手之间进行的。模块2、拉姆塞定理：在
组合数学上，拉姆塞(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
他证明了R(3，3)=6.拉姆塞数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自
然数N就称为一个拉姆塞数，记作R(k，l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1，e2)，使得Kn[e
2]中含有一个k边形，Kn[e1]含有一个l边形，则称满足这个条件的最小的n为一个拉姆塞数。（注意：Ki按照图论的记法表示i阶完全
图）拉姆塞证明，对与给定的正整数数k及l，R(k，l)的答案是唯一和有限的。拉姆塞数亦可推广到多于两个数：对于完全图Kn的每条边都
任意涂上r种颜色之一，分别记为e1，e2，e3，……，er，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形
……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1，l2，l3，……，lr；r)。拉姆塞数的数值或上下界已知的拉姆
塞数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆塞数的难度：“想像有队外星人军队在地球降落，要求取得R(5，5)的值，否则便会毁
灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6，6)的值，我们要尝试毁灭这班外星人了。”显
然易见的公式：1°R(1，s)=1；2°R(2，s)=sR(l1，l2，l3，...，lr；r)=R(l2，l1，l3，...
，lr；r)=R(l3，l1，l2，...，lr；r)（将li的顺序改变并不改变拉姆塞的数值）。拉姆塞定理：如果某一集合（如点集
）中事物的数量足够多，且每对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点集
），其中每对事物间也存在同样的关系（如同色三角形）．这个定理称为拉姆赛定理，告诉我们：如果平面上的点数足够多，且每对点间的线（边）
或染红色或染蓝色，那么必定存在一个包含3个点的子集，他们之间的边同色，即包含一个同色三角形．如平面上有6个点，把它们相互连成一个完
全图，用红、蓝两种颜色给边染色，那么一定存在一个三角形是同色三角形。证明：先选定一个点A，由它出发的连线有5条，这5条线中至少有3
条是同色的（比如是红色的），那么不妨设AB、AC、AD都是红色的，对于B、C、D三个点之间的连线，如果有一条是红色的，例如BC是红
色，则△ABC是红色三角形；如果B、C、D之间没有红色的线，那么△BCD是蓝色三角形。即K6=3或例2．17位学者，每一位都给其
余的人写一封信，信的内容是讨论三个问题中的一个，而且两个人相互通信讨论是同一个问题，证明：至少有三位学者，他们之间通信所讨论的是同
一个问题。证明：作完全图，它的17个点分别表示17位科学家.设他们讨论的题目为，两位科学家讨论连红线，讨论连蓝线，讨论连黄线.于是
只须证明这个中有一同色三角形.任取一点，自引出的边共16条，因而一定有条边同色，不妨设为红色.构成的完全图中，如果有一条边也是红
色，则为红色三角形；如果这个中没有红色边，只有蓝色和黄色，由拉姆赛定理知一定存同色三角形（蓝色或黄色）.例3．设n个新生中，任意
3个人中有2个人相互认识，任意4个人中有2个人互不认识，试求n的最大值是。解：所求n的最大值为8，当n=8时，如图所示的例子满足
要求，?其中A1、A2、……、A8表示8个新生，其中每两人之间的连线表示他们认识。设n个学生满足题设要求，我们来证明n≤8，为此，
我们先来证明如下两种情况不可能出现：?（1）若某人A至少认识6个人，这6个人设为A1、A2、……、A6，由Ramsey定理，这6个
人中存在3个互不相识（这与已知3个人中有2个相识矛盾）；或存在3个人相互认识，这时A与这3个人共4人两两相识，与已知矛盾。（2）若
某人A至多认识n?5人，则剩下至少4个人均与A不相识，从而与这4个人两两相识，矛盾。?其次，当n≥10时，（1）与（2）必有一种情
况出现，故此时n不满足要求；?当n=9时，要使（1）与（2）均不出现，则此时每个人恰好认识其他5个人，于是这时9个人产生的朋友对（
相互认识的对子）的数目为，不是整数，矛盾！?由上可知，满足要求的n≤8，所以n的最大值为8.模块三、特殊的图例4．有n个甲班学生
和n个乙班学生参加舞会，每个甲班学生都认识m个乙班学生，同样，每个乙班的学生都认识m个甲班的学生，证明可以适当安排使得甲班学生和乙
班学生可以组合成n对，每对的两个人都互相认识。证明：当m=1时，a1认识乙班中的1个学生b1，a2认识乙班中的1个学生b2，所以组
合成n对，每两个人都相互认识；若m=2，则a1认识乙班中的2个学生b1，b2，让a1与b1组合，然后b2认识除a1以外的a2，可以
让a2与b2组合，剩下的每个人同样都认识另一个班的2名学生，照上面的方法，可以让a3与b3组合，a4与b4组合，所以两个班可以组
成n对，每对的两个人相互认识；……，用数学归纳法证明：假设m=k时成立，即每个甲班学生都认识k个乙班学生，同样，每个乙班的学生都认
识k个甲班的学生，可以适当安排使得甲班学生和乙班学生可以组合成n对，每对的两个人都互相认识。当m=k+1时，从a1开始，a1认识k
+1个乙班学生，如b1，b2，……，bk+1，让a1与b1组合，剩下的n?1个甲班的每个学生都至少认识k个乙班的学生，同样剩下的n
?1个乙班的每个学生都至少认识k个甲班的学生，他们可以配对组合，所以原题的结论成立。例5．连通图说的是图中任意两点必有一些边将它们
连起来，若一个图中的边中有一些能首尾相连成为一个环，就称这个图中含有圈，无圈连通图称为树。若一个点最少经过a条边就能到另一个点，则
称它们的距离是a，一个图中任意两点间的距离的最大值称为这个图的直径，一个图中一个点到它最远点的距离叫它的离径。对于图中所有点来说，
离径最小的点称为中心。证明：每个树都有至多两个中心。证明：用数学归纳法证明。当n=2时，即只有2个点形成的树，显然命题是成立的。假
设当n=k时，该树至多有两个中心，则当n=k+1时，我们将其中最外面的叶子去掉一个(比如该叶子叫Y)，得到的是一个n=k的树，这个
树至多有两个中心，不妨设A、B为中心，下面计算Y到A或B的离径，如果Y到A的离径小，则A为中心，如果Y到B的离径小，则B为中心；如
果Y到A、B的离径相等，则A、B都是中心；即n=k+1时，命题成立，由①、②知，原命题成立。例6．证明平面连通图满足：V+F?E=
2。其中V是顶点数，F是将平面分割成的区域数（最外面的直到无限远也算一块），E是边数。（平面图是指在平面上能画出来的图，图中任意两
边不相交）证明：最简单的平面连通图是三角形，对一个△ABC，V=3，F=2，E=3，所以V+F?E=2。对于四边形ABCD，我们连
一条对角线将它分成两个三角形，V=3+1=4，F=2+1=3，E=3+2=5，所以V+F?E=2。图形顶点V平面区域F边数EV+F
?E三角形3232四边形4352五边形5472六边形6592……对于一个平面上的联通平面图，如果是一个n边形，则可以画出n?3条
对角线，使得每一个区域都是三角形，从三角形开始，每次在一条边的外面画上两条边，即E增加2，点增加1个，即V增加1，平面区域增加1，
所以此时V+F?E仍然等于2。证明二：（1）归纳基础：一条边，欧拉公式成立；（2）归纳步骤：假设m?1条边，欧拉公式成立；考察
m条边的连通平面图：（1）若有度数为1的顶点，则删去该顶点及其关联边，便得到连通平面图G’，G’满足欧拉公式，再将删去的点和边
加回G’得到G也满足欧拉公式；（2）若没有度数为1的顶点，则删去有界面边界上的任一边，便得到连通平面图G’，G’满足欧拉公式，
再将删去的边加回G’得到G也满足欧拉公式。例7．有三个工厂和三个矿山，每个工厂都要和矿山之间建一条铁路，证明这9条铁路线必然交叉。
也就是它们不能被画在平面上，这个图不是平面图。证明：每个工厂要修3条铁路，一共有9条铁路，即V=6，E=9，如果都不相交，则F=2
+E?V=2+9?6=5，又这六个点都引出三条线，且平面区域中不存在三条边形成的面，即每个面都是由四条边组成，即4×F=2E，与F
=5，E=9矛盾。所以9条铁路线必然交叉。例8．平面上N条直线将平面分成不同的区域，则这些区域只需要用两种颜色染色即可分开。证明：
当n=1时，成立，假设n=k时成立，再画第k+1条线，则这条线经过的区域都被分成了两部分，按图中看，从右面算起，它经过的第
1个区域原来是红色的则把这两部分中一部分保持原来的颜色，另一部分改成另一种颜色；同样第2个区域照此办理，……，直到把所有的区域涂完
为止。即靠这条线的一边全部都改变颜色即可。随堂练习1．某城市的每一条道路均连接着两个十字路口，且都限定为单向行车线。市政当局
为设置加油站网点开展一次设计竞赛，要求自每个十字路口均可按规定方向行车到加油站之一，但由任何一个加油站都不能按规定方向驶抵另外的任
何一个加油站。求证：在所有的应征方案中，都设计了相同数目的加油站。解：由已知，每条路上都不能有3个十字路口，于是这个图是一个多边形
并延长各边得到的平面图形。如一共有n条单行线，显然加油站不能在多边形的边上。不然的话，从该加油站就可以行使到前面一个十字路口，再
行驶到另一个加油站；又加油站不能设置在单行线未行进到十字路口的那一段，这样的话，该加油站对每一个十字路口都失去了意义；所以，加油站
应该设置在每条单行线的延长线的地方，所以应该设置n个加油站。2．9个科学家在一个国际会议上相遇，发现他们中的任意三人中都至少有两个
人可以用同一种语言对话，如果每个科学家至多可以说三种语言，证明至少有三个科学家可以用同一种语言对话。证明：假设没有三人能讲同一种语
言，即每种语言最多只两人能讲．用A1，A2，…，A9表示这九人．因为A1最多说三种语言，所以A1至多与三个人通话，即至少与五个人语
言不通，设为A5，A6，A7，A8，A9．同理A5至少与A6，A7，A8，A9中一人语言不通，设为A9，于是A1，A5，A9彼此语
言都不通．而这与已知矛盾．所以一定有三个科学家可以用同一种语言对话。证明2：假设A和B会说语言1，且A会说语言2和语言3，B会说
语言4和语言5。由于三人中至少有两人会说同一语言，所以另外7个人都与A或B会说同一种语言。根据抽屉原理，这7人中至少有两人会说同一
种语言，假设为语言3，则有至少有三人会说同一种语言。3．某次会议n个代表出席，已知对于任意四个代表都有1人和其余三个握过手，证明任
意四个代表中至少有1个和其余n?1个都握过手。证明：用顶点表示代表，如果两名代表握过手，用线连接起来，且相应两顶点相邻，这样得到一
个简单图G，已知条件是：G中任意四个顶点中必有一个点与其他三个点相邻，欲证图G中任意四个点中必有一点与其他所有顶点都相邻。假设G中
有4个顶点，V1、V2、V3、V4，其中每个顶点与图G中其他顶点不都相邻，则一定能找到这样四个点V1’、V2’、V3’、V4’，它
们依次与V1、V2、V3、V4不相邻，由已知条件可以设V1与V2、V3、V4，都相邻，因此V1’≠V2、V3、V4，且V2’≠V1
，如果且V2’≠V1’，则顶点V1、V2、V1’、V2’中没有一个顶点与其他三个顶点都相邻，矛盾；如果V1’=V2’≠V3’，则顶
点V2、V3、V2’、V3’中没有一个顶点与其他三个顶点都相邻，矛盾；如果V1’=V2’=V3’，则顶点V1、V2、V3、V1’中
没有一个顶点与其他三个顶点都相邻，矛盾；因此G中任意四个点中必有一点与其他n?1个点相邻。4．甲、乙两个班各有n个学生，甲班的人都
和一些（不是所有）乙班学生跳过舞，每个乙班学生都和至少1个甲班学生跳过舞，证明一定能找到两个甲班学生a、b和两个乙班学生x、y，使
得a和x，b和y跳过舞，但a和y，b和x之间没有跳过舞。证明：画图如下：在A中取一点a，使得d(a)最大，即a与B中跳过舞的人数最
多，因为d(a)与b相邻的点有d(b)?1个，而且d(b)?1≤d(a)?1舞，b与x没有跳过舞。5．怎样用最少数量的航空线路连接50个城市，才能使从一个城市到另一个城市的旅行都至多需要乘两次（换乘一次）飞
机？解：做成一个树，若只有一个中心A，则其他49个城市与A都有航线，即49条航线即可；若中心有两个A和B，则它们之间建一条航线，其
他48个城市或与A有航线，或者与B有航线，一共有48+1=49条航线。而树不会有3个中心，所以航线共有49条。6．证明：不存在7条
棱的凸多面体。证明：因为每个多面体的面最少有3条边，每相邻两个面的两条边重合为一条棱，那么以多面体的顶点为顶点，以多面体的棱为边组
成的平面图G中，面数E≤，又E≥4，所以E=4，F=7，由欧拉公式V+E?F=2，所以V=5，即有5个顶点，但是当E=4时，唯一的
多面体是四面体，它只有4个顶点，矛盾。所以比存在7条棱的凸多面体。7．证明有5个顶点的完全图不是平面图。证明：一个完全图有5个顶点
，连线则有（条），即V=5，E=10，由欧拉定理得F=2+E?V=7，即有7个面。每个面至少由3条边组成，每条边在不同的的面中出现
2次，3×7=21>10×2，矛盾。所以有5个顶点的完全图不是平面图。8．一个延伸到无限远的地图可以看做一个平面图，每一块地都由一些边圈起来，这些边也是也是与它相邻的地的边，将那些和至少三块地相邻的点取作平面图上的点，证明对一个地图来说，当每个点都是偶数点时，这个地图可以被二染色。证明1：归纳基础：当p=1时，G是2-面可着色的。?归纳步骤：假设回路为p?1的地图G是2?面可着色的。对于由p条回路构成的地图G，由于G的每个顶点都是偶顶点，在G中删去一条回路，得到图G’，G’的每个顶点的度数也是偶数。根据归纳假设，G’是2?面可着色的。再把删去的回路加回到G’中得到G，并且使这条回路外的所有面的颜色保持不变，而回路所围的各面已着两种颜色，将这两种颜色对换，得到G是2?面可着色的。证明2：在图中选择偶数最大的点A，用两种颜色涂色，恰好可以完成，由A点出发到下一个点B，由于B也是偶数点，沿由B到A方向的区域保留原来的颜色，另一面则改变原来的颜色，即1改为2，2改为1，仍然满足二染色。……，依次类推，这个图可以被二染色。 |
|
