发布时间 : 星期日 文章数学竞赛中的图论问题更新完毕开始阅读76bdddd2b9f3f90f76c61bc1
就越大，任意两个顶点之间的通路相连接的可能性就越大，因此图G越有可能是连通的.当然，这仅仅是一种直观的想象.事实上，图G的连通性和它的顶点的度之间确实存在密切的联系.
2.2.2 连通图的判断定理
定理2设G是n阶简单图.如果图G中顶点的最小度则图G是连通的.
例7 有2n部电话交换台，每部电话交换台都至少和n部电话交换台有直接线路连接.证明，其中任意两部电话交换台都可以进场一次通话（允许通过别的交换台）.（“希望杯”邀请赛试题）
证明：用顶点表示交换台，其集合记作V.对于u，v∈V，当且仅当u和v表示的两部交换台有直通线连接时令u和v相邻，得到的是2n阶简单图.
由于每部交换机都至少和n部交换台连接直通线路，所以图G中每个顶点的度至少是n.即图G的顶点的最小度
.由定理2，图G是连通的.
满足
，
于是由定义，对图G中任意两个顶点u和v，总有一条以u为起点且以v为终点的通路x0x1···xk，其中x0=u，xk=v，由于连接顶点xi+1和xi（i=1，2，···，k）的边即是交换台xi+1和xi的直通线路，所以只要接线人员按照直通线路x0x1，x1x2，···，xk-1xk的顺序接线，则交换台u和v就可以实现一次通话.
例8 圆周上有13个点，能否用自然数1，2，3，···，13给这些点编号，使得任意两个相邻的点的号码之差的绝对值至少是3，最多是5？（1986年匈牙利数学竞赛试题）
解 答案是“不能”.现在用反证法证明之.
假设存在一种编号方法，使得任意两个相邻的点的号码之差的绝对值至少是3，最多是5，把圆周上13个点视为13个顶点，其集合记作V.对于顶点u和v，当且仅当u和v所表示的两个点相邻时令顶点u和v相邻，得到的是一个长为13的圈C13.很明显，C13是连通的.用顶点所表示的点的编号表示顶点.将顶点集合V分划为两个子集X={1，2，3，11，12，13}和Y={4，5，6，7，8，9，10}.
由于C13是一个圈，所以每个顶点的度都是2，又集合X中任意两个顶点都
8
不相邻，所以X的顶点和Y的顶点之间恰连有12条边，而C13恰有13条边.因此Y的顶点之间必有一条边.Y中的顶点4在X中只和顶点1相邻，由于顶点4的度为2，所以顶点4必和Y中另一个顶点相邻.同理.Y中顶点10必和Y中另一个顶点相邻.但是顶点4和10不相邻.这表明，Y中顶点之间至少连有两条边，矛盾.因此不存在合乎条件的编号方式.
2.2.3 欧拉回路和欧拉迹的概念
在熟悉了图的连通概念之后，现在再来谈谈欧拉关于哥尼斯堡七桥问题的研究.首先，把哥尼斯堡管辖只下的四个城区A，B，C，D视为4个顶点，连接城区的没做桥都视为边，得到的是4阶图G（图（6））.于是问题化为：从图G中每个顶点出发，能否存在一条通路，经过每条边恰好一次，然后回到原来的顶点.换句话说，图G中是否含有图G所有的边的回路.
D
A C
B
图（6）
一般来说，n阶图G中含有所有边的回路叫做欧拉回路.具有欧拉回路的图G叫做欧拉图.则问题进一步转化为：图（6）中的四阶图是否是欧拉图.
欧拉图和所谓的一笔画问题有着密切的联系.所谓一笔画问题就是，纸面上给定的一个图G,能否从图G的一个顶点出发，笔不离开纸，而且连续地沿着每条边恰好一次，然后回到原来的顶点，从而画出整个图G？很显然，如果图G是欧拉图，则可以一笔画出整个图G，否则就不能.图（6）不是欧拉图，则不能一笔画出整个图G.
2.2.4欧拉回路和欧拉迹的判断定理
定理3 设G是连通图，则G为欧拉图的充分必要条件是，图G中的每个顶点的度是偶数.
9
有了定理3，哥尼斯堡七桥问题的答案就是显而易见的.从图（6）可以看出，其中的图G是连通的，而且图G中每个顶点都不是偶顶点，因此，由定理3，图G不是欧拉图，也就是说，哥尼斯堡七桥问题的答案是：不可能.
既然哥尼斯堡七桥问题不能得到肯定的答案，那么是否可以退而求其次呢？即考虑如下的问题：能否从哥尼斯堡某个城区出发，经每座桥恰好一次，然后达到另一个城区？
那么这个问题就相当于是对于给定一个图G，对其中某个顶点u，是否存在以u为端点的一条迹，使得图G中每条边恰好在其中出现一次.如果这样的迹存在，则称它为图G的一条欧拉迹.欧拉迹和欧拉回路的差别在于，欧拉回路是一条闭通路.
定理4 设u和v是连通图G的两个不同顶点，则图G具有一条连接顶点u和v的欧拉迹的充分必有条件是，u和v是奇顶点，其他所有顶点都是欧拉点.
综合定理3和定理4，可得到以下的推论.
推论 有限图G 可以一笔画成的充要条件是G是连通的,且奇顶点的个数为0或2. 当且仅当奇顶点个数为0时,连通图G是一个圈.
由推论可以看出，所谓的退而求其次形式的哥尼斯堡七桥问题的答案也是否定的，因为图（6）中的图G中不含有偶顶点.
2.2.5应用举例
例9一天，小明做完作业正在休息，收音机中播放着轻松、悦耳的音乐.他拿了支笔，信手在纸上写了“中”、“日”、“田”几个字.突然，他脑子里闪出一个念头，这几个字都能一笔写出来吗？他试着写了写，“中”和“日”可以一笔写成（没有重复的笔划），但写到“田”字，试来试去也没有成功.这是怎么回事呢？（小学奥林匹配竞赛试题） a c b g a b a c d b c f d d e h f g e h i e 图（7）
f 图（9）
10
图（8） 解 把“中”这个字的每一个重合的地方看作顶点，如图（7）所示，分别把各个顶点记作a、b、c、d、e、f、g、h.由图可知，各个顶点的度依次为2、4、2、2、4、2、1、1，则可以知道它其中的6个顶点的度为偶数，另外两个为奇数，即奇顶点的个数为2，由推论可知，“中”字可以一笔画成，且起点和终点分别为g和h（或h和g），则可按图（10）所示方法一笔画成（方法不唯一）,即从g b c f e d a b e h.
a d 图（10） e h f d e h f d e h f g b c a g b c a b c g 同样的，把“日”的每一个重合的地方看作顶点，如图（8）所示，分别把各个顶点记作a、b、c、d、e、f.由图所知，各个顶点的度依次为2、2、3、3、2、2，则可以知道它的各个顶点中有两个奇顶点和四个偶顶点，由推论可知，“日”可以一笔画出，且起点和终点分别为c和d（或d和c），则可按图（11）所示方法一笔画出（方法不唯一）,即c a b d c e f d.
a c b d a c b d c a b d e
f e 图（11）
f e f 把“田”这个字的每一个重合的地方看做顶点，如图（9）所示，分别把各个顶点记作a、b、c、d、e、f、g、h、i.由图所知，各个顶点的度依次为2、3、2、3、4、3、2、3、2，则可以知道它的各个顶点中有四个奇顶点和五个偶顶点，由图论可知，“田”不能一笔画出.
11