离散数学(7.4欧拉图与汉密尔顿图)

1、7.4 欧拉图与汉密尔顿图 7.4.1 欧拉图欧拉图 7.4.2汉密尔顿图汉密尔顿图 7.4.1 欧拉图 历史上的哥尼斯堡七桥问题是著名历史上的哥尼斯堡七桥问题是著名的图论问题。的图论问题。 问题是这样的：问题是这样的： 18世纪的东普鲁士世纪的东普鲁士有个哥尼斯堡城，有个哥尼斯堡城， 在横贯全城的普雷格在横贯全城的普雷格尔河两岸和两个岛之间架设了尔河两岸和两个岛之间架设了7座桥，座桥， 它它们把河的两岸和两个岛连接起来（如图们把河的两岸和两个岛连接起来（如图7.4.1）。）。 每逢假日，每逢假日， 城中居民进行环城游玩，城中居民进行环城游玩， 人们对此提出了一个人们对此提出了一个“遍游遍游”

2、问题，问题， 即即能否有这样一种走法，能否有这样一种走法， 使得从某地出发使得从某地出发通过且只通过每座桥一次后又回到原地通过且只通过每座桥一次后又回到原地呢？呢？ 我们将图我们将图7.4.1中的哥尼斯堡城中的哥尼斯堡城的的4块陆地部分分别标以块陆地部分分别标以A， B， ， D， 将陆地设想为图的结点，将陆地设想为图的结点， 而把桥画成相而把桥画成相应的连接边，应的连接边， 这样图这样图7.4.1可简化成图可简化成图7.4.2。 于是七桥于是七桥“遍游遍游”问题等价于问题等价于在图在图7.4.2中，中， 从某一结点出发找到一从某一结点出发找到一条回路，条回路， 通过它的每条边一次且仅一次，通

3、过它的每条边一次且仅一次， 并回到原来的结点。并回到原来的结点。 图 7.4.1哥尼斯堡七桥问题示图 图图 7.4.2哥尼斯保七桥问题简化图哥尼斯保七桥问题简化图 定义定义 7.5.1 给定无孤立结点的给定无孤立结点的图图G， 若若存在一条存在一条经过经过G中中每边一次每边一次且仅一次且仅一次的回路，的回路， 则该回路为欧拉回则该回路为欧拉回路。路。 具有欧拉回路的图称为欧拉图。具有欧拉回路的图称为欧拉图。 例如，例如， 给出如图给出如图7.4.3所示的所示的两个图，两个图， 容易看出，容易看出， (a)是欧拉图，是欧拉图， 而而(b)不是欧拉图。不是欧拉图。 图图 7.4.3 定理定理 7.

4、5.1 连通图连通图G是欧拉图是欧拉图的的充要条件充要条件是是G的所有结点的度数都的所有结点的度数都是偶数。是偶数。 证明证明: 必要性：必要性： 设设G是一欧拉是一欧拉图，图， 是是G中的一条欧拉回路。中的一条欧拉回路。 当当通通过过G的任一结点时，的任一结点时， 必通过关联于该必通过关联于该点的两条边。点的两条边。 又因为又因为G中的每条边仅中的每条边仅出现一次，出现一次， 所以所以所通过的每个结点所通过的每个结点的度数必定是偶数。的度数必定是偶数。 图图 7.4.4 图图G 充分性：充分性： 我们可以这样来作我们可以这样来作一个闭迹一个闭迹， 假设它从某结点假设它从某结点A开始，开始，

5、沿着一条边到另一结点，沿着一条边到另一结点， 接着再从这接着再从这个结点，个结点， 沿没有走过的边前进，沿没有走过的边前进， 如此如此继续下去。继续下去。 因为我们总是沿着先前没因为我们总是沿着先前没有走过的新边走，有走过的新边走， 又由于图又由于图G的边数的边数有限，有限， 所以这个过程一定会停止。所以这个过程一定会停止。 但但是，是， 因为每一个结点都与偶数条边关因为每一个结点都与偶数条边关联，联， 而当沿而当沿前进到达结点前进到达结点v 时，时， 若若vA， 走过了与走过了与v关联的奇数条边，关联的奇数条边， 这样在这样在v上总还有一条没有走过的边。上总还有一条没有走过的边。 因此，因此

6、， 必定返回停止在必定返回停止在A（见图（见图7.4.4）。）。 如果如果走遍了走遍了G的所有边，的所有边， 那么我们就得到所希望的一条欧拉那么我们就得到所希望的一条欧拉回路。回路。 如果不是这样，如果不是这样， 那么在那么在上上将有某一结点将有某一结点B， 与它关联的一些与它关联的一些边尚未被边尚未被走过（因走过（因G连通）。连通）。 但是，但是， 实际上，实际上， 因为因为走过了与走过了与B关联的偶关联的偶数条边，数条边， 因此不属于因此不属于的与的与B关联的关联的边也是偶数条。边也是偶数条。 对于其他有未走过对于其他有未走过边所关联的所有结点来说，边所关联的所有结点来说， 上面的上面的讨

7、论同样正确。讨论同样正确。 于是若设于是若设G1是是G的包含点的包含点B的一个连通分支，的一个连通分支， 则则G1的结点全是偶数度结点。的结点全是偶数度结点。 运用上面的讨论，运用上面的讨论， 我们在我们在G1中中得到一个从得到一个从B点出发的一条闭迹点出发的一条闭迹1。 这样我们就得到了一条更大的闭迹，这样我们就得到了一条更大的闭迹， 它是从它是从A点出发沿点出发沿前进到达前进到达B， 然后然后沿闭迹沿闭迹1回到回到B， 最后再沿最后再沿由由B走到走到A。 如果我们仍然没有走遍整个图，如果我们仍然没有走遍整个图， 那么我们再次把闭迹扩大，那么我们再次把闭迹扩大， 以此类推，以此类推， 直到最

8、后得到一个欧拉回路。直到最后得到一个欧拉回路。 由于在七桥问题的图由于在七桥问题的图7.4.2中，中， 有个点是奇数度结点，有个点是奇数度结点， 故不存在欧故不存在欧拉回路，拉回路， 七桥问题无解。七桥问题无解。 在图在图7.2.3中，中， (a)图的每个结点图的每个结点的度数都为，的度数都为， 所以它是欧拉图；所以它是欧拉图；(b)图不是欧拉图。图不是欧拉图。 但我们继续考察但我们继续考察(b)图图可 以 发 现 ，可 以 发 现 ， 该 图 中 有 一 条 路该 图 中 有 一 条 路v2v3v4v5v2v1v5， 它经过它经过(b)图中的每条图中的每条边一次且仅一次，边一次且仅一次， 我

9、们把这样的路称为我们把这样的路称为欧拉路欧拉路(非欧拉回路非欧拉回路)。 定义定义7.5.2 通过图通过图G的每条边一的每条边一次且仅一次的路称为图次且仅一次的路称为图G的欧拉路。的欧拉路。 对对于欧拉路有下面的判定方法。于欧拉路有下面的判定方法。 定理定理7.5.2 连通图连通图G具有一条连具有一条连接结点接结点vi和和vj的欧拉路当且仅当的欧拉路当且仅当vi和和vj是是G中中仅有仅有的的奇数度结点奇数度结点。 证明证明: 将边将边(vi， vj)加于图加于图G上，上， 令其所得的图为令其所得的图为G（可能是多重图）。（可能是多重图）。 由定理由定理7.5 .1知：知： G有连接结点有连接结

10、点vi和和vj的欧拉路，的欧拉路， iff G有一条欧拉回路，有一条欧拉回路， iff G的所有结点均为偶度结点，的所有结点均为偶度结点， iff G的所有结点除的所有结点除vi和和vj外均为外均为偶度结点，偶度结点， iff vi和和vj是是G中仅有的奇度结点。中仅有的奇度结点。 我国民间很早就流传一种我国民间很早就流传一种“一笔一笔画画”游戏。游戏。 由定理由定理7.5 .1和定理和定理7.5.2知，知， 有两种情况可以一笔画。有两种情况可以一笔画。 1) 如果图中所有结点是偶数度结如果图中所有结点是偶数度结点，点， 则可以任选一点作为始点一笔画完；则可以任选一点作为始点一笔画完； 2)

11、如果图中只有两个奇度结点，如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点则可以选择其中一个奇度结点作为始点也可一笔画完。也可一笔画完。 【例【例7.4.1】图图7.4.5(a)是一幢房子是一幢房子的平面图形，的平面图形， 前门进入一个客厅，前门进入一个客厅， 由客厅通向由客厅通向4个房间。个房间。 如果要求每如果要求每扇门只能进出一次，扇门只能进出一次， 现在你由前门现在你由前门进去，进去， 能否通过所有的门走遍所有能否通过所有的门走遍所有的房间和客厅，的房间和客厅， 然后从后门走出。然后从后门走出。 图图 7.4.5 解解: 将将4个房间和一个客厅及前个房间和一个客厅及前门外

12、和后门外作为结点，门外和后门外作为结点， 若两结点有若两结点有边相连就表示该两结点所表示的位置边相连就表示该两结点所表示的位置有一扇门相通。有一扇门相通。 由此得图由此得图7.4.5(b)。 由于图中有由于图中有4个结点是奇度结点，个结点是奇度结点， 故由故由定理定理7.5.2知本题无解。知本题无解。 类似于无向图的结论，类似于无向图的结论， 对有向对有向图有以下结果。图有以下结果。 定理定理7.5.3 一个连通有向图具有一个连通有向图具有（有向）欧拉回路的充要条件是图中每（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。个结点的入度等于出度。 一个连通有向一个连通有向图具有有向欧拉路的

13、充要条件是图具有有向欧拉路的充要条件是最多最多除除两个两个结点外的每个结点的入度等于出度，结点外的每个结点的入度等于出度， 但在这两个结点中，但在这两个结点中， 一个结点的入度比一个结点的入度比出度大出度大1， 另一个结点的入度比出度少另一个结点的入度比出度少1。 下面举一个有趣的例子是计算机下面举一个有趣的例子是计算机鼓轮的设计。鼓轮的设计。 【例【例7.4.1】设一个旋转鼓的表面被分设一个旋转鼓的表面被分成成24个部分，个部分， 如图如图7 - 26所示。所示。 其中每其中每一部分分别由导体或绝缘体构成，一部分分别由导体或绝缘体构成， 图中图中阴影部分表示导体，阴影部分表示导体， 空白部分

14、表示绝缘空白部分表示绝缘体，体， 绝缘体部分给出信号绝缘体部分给出信号0，导体部分，导体部分给出信号给出信号1。 根据鼓轮转动后所处的位根据鼓轮转动后所处的位置，置， 4个触头个触头a， b， c， d将获得一定将获得一定的信息。的信息。 图中所示的信息为图中所示的信息为1101， 若将若将鼓轮沿顺时针方向旋转一格，鼓轮沿顺时针方向旋转一格， 则则4个触个触头头a， b， c， d获得获得1010 。试问鼓轮上。试问鼓轮上16个部分怎样安排导体及绝缘体，个部分怎样安排导体及绝缘体， 才能才能使鼓轮每旋转一格后，使鼓轮每旋转一格后， 4 个触头得到的个触头得到的每组信息（共每组信息（共16组）均

15、不相同？这个问组）均不相同？这个问题也即为：题也即为： 把把16个二进制数字排成一个个二进制数字排成一个环形，环形， 使得使得4个依次相连的数字所组成个依次相连的数字所组成的的16个个4位二进制数均不相同。位二进制数均不相同。 图图 7.4.6 解解: 问题的答案是肯定的。问题的答案是肯定的。 下面下面谈一下解决这个问题的思路。谈一下解决这个问题的思路。 设设i 0， 1 （i16）。）。 每旋转一格，每旋转一格， 信号从信号从1234转到转到2345， 前者的右前者的右 3 位决定了后者的位决定了后者的左左 3 位。位。 于是，于是， 我们的想法是将这我们的想法是将这16个个二进制数字的环形

16、二进制数字的环形1216对应一个欧拉对应一个欧拉有向路，有向路， 使其边依次为使其边依次为1234， 2345， 3456， （图（图7 27）。）。 我们把我们把234对应一个结点，对应一个结点， 它是弧它是弧1234的终点也是弧的终点也是弧2345的始点。的始点。 这样我们的问题就转化为以位二进制数这样我们的问题就转化为以位二进制数为结点作一个有向图，为结点作一个有向图， 再在图中找出欧再在图中找出欧拉回路。拉回路。 图图 7.4.7 欧拉有向路示图欧拉有向路示图 构造一个有个结点的有向图构造一个有个结点的有向图G（图（图7 28）。）。 其结点分别记为位其结点分别记为位二进制数二进制数0

17、00、 001、 010、 011、 100、 101、 110、 111。 从结点从结点123出发可引出两条有向边，出发可引出两条有向边， 其终其终点分别是点分别是23和和23， 记这两条记这两条有向边为有向边为123和和123。 这样这样图图G就有就有16条边。条边。 由于由于G中每点的入度中每点的入度等于出度都等于，等于出度都等于， 故在图中可找到故在图中可找到一条欧拉回路。一条欧拉回路。 例如（仅写出边的序列）例如（仅写出边的序列）e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。 根据邻接边的标号记法，根据邻接边的标号记法， 这这16个二进制数可写成对应的

18、二进制个二进制数可写成对应的二进制序列序列0000100110101111， 把这个把这个序列排成环状，序列排成环状， 与所求的鼓轮相对与所求的鼓轮相对应，应， 如图如图7.4.6所示。所示。 该例可推广到鼓轮有该例可推广到鼓轮有n个触个触点的情况。点的情况。 图图 7.4.8 具有具有 8 个结点的有向图个结点的有向图G 7.4.2 汉密尔顿图汉密尔顿图 与欧拉回路类似的是汉密尔与欧拉回路类似的是汉密尔顿回路问题。顿回路问题。 它是它是1859年汉密尔顿年汉密尔顿首先提出的一个关于首先提出的一个关于12面体的数学面体的数学游戏：游戏： 能否在图能否在图7.4.9中找到一个回中找到一个回路，路

19、， 使它含有图中使它含有图中所有结点所有结点一次且一次且仅一次仅一次？ 若把每个结点看成一座城若把每个结点看成一座城市，市， 连接两个结点的边看成是交通连接两个结点的边看成是交通线，线， 那么这个问题就变成能否找到那么这个问题就变成能否找到一条旅行路线，一条旅行路线， 使得沿着该旅行路使得沿着该旅行路线经过每座城市恰好一次，线经过每座城市恰好一次， 再回到再回到原来的出发地呢？为此，原来的出发地呢？为此， 这个问题这个问题也被称作周游世界问题。也被称作周游世界问题。 图图 7.4.9 12 面体游戏示图面体游戏示图 对图对图7.4.9 ， 图中粗线给出了这图中粗线给出了这样的回路。样的回路。

20、定义定义 7.5.3 给定图给定图G， 若有一条若有一条路通过路通过G中每个结点恰好一次，中每个结点恰好一次， 则这样的则这样的路称为汉密尔顿路；若有一个圈，路称为汉密尔顿路；若有一个圈， 通过通过G个每个结点恰好一次，个每个结点恰好一次， 这样的圈称为汉密这样的圈称为汉密尔顿回路（或汉密尔顿圈）。尔顿回路（或汉密尔顿圈）。 具有汉密尔具有汉密尔顿顿回回路的图称为汉密尔顿图。路的图称为汉密尔顿图。 尽管汉密尔顿回路与欧拉回路问尽管汉密尔顿回路与欧拉回路问题在形式上极为相似，题在形式上极为相似， 但是到目前为止还但是到目前为止还不知道一个图为汉密尔顿图的充要条件，不知道一个图为汉密尔顿图的充要条

21、件， 寻找该充要条件仍是图论中尚未解决的主寻找该充要条件仍是图论中尚未解决的主要问题之一。要问题之一。 下面先给出一个简单而有用下面先给出一个简单而有用的必要条件。的必要条件。 定理定理7.5.4 设图设图GV ,E是汉密尔顿图，是汉密尔顿图， 则对于则对于V的每个非的每个非空子集空子集S， 均有均有 W（GS）|S| 成立，成立， 其中其中W（GS）是图）是图GS的连通分支数。的连通分支数。 证明证明: 设设是是G的汉密尔顿回的汉密尔顿回路，路， S是是V的任一非空子集。的任一非空子集。 在在GS中，中， 最多被分为最多被分为|S|段，段， 所以所以 W （ G S ）|S| 利用本定理可判

22、别某些图不利用本定理可判别某些图不为汉密尔顿图。为汉密尔顿图。 如在图如在图7.4.10中，中， 若取若取Sv1， v4， 则则GS有有 3 个连通分支，个连通分支， 故该图不是汉密尔顿故该图不是汉密尔顿图。图。 判断汉密尔顿图的充分条件判断汉密尔顿图的充分条件很多，很多， 我们仅介绍其中一个。我们仅介绍其中一个。 图图7.4.10 定理定理 7.5.5 设设GV ,E是有是有n个个结点的简单图，结点的简单图， 1） 如果任两结点如果任两结点u， vV， 均有均有 deg(u)deg(v) n1， 则在则在G中存在一条汉密尔顿路；中存在一条汉密尔顿路； 2） 如果对任两结点如果对任两结点u，

23、vV， 均有均有 deg(u)deg(v) n， 则则G是汉密尔顿图。是汉密尔顿图。 证明证明 略。略。 【例【例7.4.2】某地有个风景点。某地有个风景点。 若每个若每个景点均有两条道路与其他景点相通，景点均有两条道路与其他景点相通， 问是问是否可经过每个景点恰好一次而游完这处？否可经过每个景点恰好一次而游完这处？ 解解 将景点作为结点，将景点作为结点， 道路作为边，道路作为边， 则得到一个有个结点的无向图。则得到一个有个结点的无向图。 由题意，由题意， 对每个结点对每个结点vi， 有有deg(vi)2（i5）。）。 则对任两点则对任两点vi， vj（i， j5）均有）均有 deg(vi)d

24、eg(vj)22451 可知此图一定有一条汉密尔顿路，可知此图一定有一条汉密尔顿路， 本题本题有解。有解。 我们再通过一个例子，我们再通过一个例子， 介绍一个判别汉介绍一个判别汉密尔顿路不存在的标号法。密尔顿路不存在的标号法。 【例【例7.4.3】证明图证明图7 31所示的图没所示的图没有汉密尔顿路。有汉密尔顿路。 证明证明: 任取一结点如任取一结点如v1， 用用A标记，标记， 所有与它相邻的结点标所有与它相邻的结点标B。 继续不断地继续不断地用用A标记所有邻接于标记所有邻接于B的结点，的结点， 用用B标记标记所有邻接于所有邻接于A的结点，的结点， 直到图中所有结直到图中所有结点全部标记完毕。

25、点全部标记完毕。 如果图中有一条汉密尔顿路，如果图中有一条汉密尔顿路， 则必交替通过结点则必交替通过结点A和和B。 因此或者结点因此或者结点A和和B数目一样数目一样， 或者两者或者两者相差相差个。个。图图7.4.11 而本题有个结点标记而本题有个结点标记A， 个结点标记个结点标记B， 它们相差个，它们相差个， 所以该图不存在汉密尔顿路。所以该图不存在汉密尔顿路。 作为汉密尔顿回路的自然推作为汉密尔顿回路的自然推广是著名的广是著名的货郎担货郎担问题。问题。 问题是这问题是这样叙述的：样叙述的： 设有一个货郎，设有一个货郎， 从他所从他所在的城镇出发去在的城镇出发去n个城镇。个城镇。 要要求经过每个城镇恰好一次，求经过每个城镇恰好一次， 然后返然后返回原地，回原地， 问他的旅行路线怎样安排问他的旅行路线怎样安排才最经济？从图论的观点来看，才最经济？从图论的观点来看， 该该问题就是：问题就是： 在一个有权在一个有权完全图完全图中找中找一条一条权最小权最小的汉密尔顿的汉密尔顿回回路。路。 研究这个问题是十分有趣且研究这个问题是十分有趣且有实用价值的。有实用价值的。 但很可惜，但很可