例2.2.3用DFS方法找图2.6巾0，到4的一条道路。 解：数据输入依然采用正向表。，的第-个直接后继是2：进栈；2的第一个后继 是，2进栈。3的后继是：，但已标记，故退栈，的另一个后继是6,2进栈；%的第 1个后继是已标记结点，第2个后继是，%进找y的后继是4。至此，已搜索到1到 ,的-·条道路。整个搜索过程用图2.7形象地表示。其计算复杂性也是O(m)。 2.3欧拉道路与回路 1736年瑞七著名数学家（拉I.eonhard Euler)发表了图论的第一篇论文“哥尼斯堡 七桥向题”。这个问题是这样的：哥尼斯堡城被Pregel河分成了4部分，它们之问有？座 桥。如图2.8所示。当时人有提出了个问题，能否从城市的某处出发，过每座桥一次且 仅一次最后可到原处。欧拉的文章漂亮地解决了这个问题。他把4块陆地设想为4个结 点，分别用A,B、C、D表示，而将桥商成相应的边，如图2.9。于是问题转化为在该图中是 否存在经过每条边一次且仪一次的回路.欧拉的论文给出了解决这类问题的准则，并对七 桥问题给出了否定的结论。 1 图2.5 图2.9 定义2.3.1无向连通图(G=(V,E)中的一条经过所有边的简单回路（道路）称为G 的欧拉问路（道路）。 定理2.3.1无向连通图G存在欧拉回路的充要条件是G中各结点的度都是偶数。 证明：必要性，若G中有欧拉回路C,则C过每一条边一次且仪一次，对任一结点v来 说，如果C经由，进入o,则一定通过另一条边e,从离开。因此结点v的度是偶数。 充分性。由于(G是有穷图，因此可以断定，从G的任一结点出发一定存在G的一 条简单回路C。'这是因为各结点的度都是偶数，所以这条简单道路不可能停留在以外 的某个结点，而不能再向前伸延以至构成问路C。 如果E(G)=(C,则C就是欧拉问路，充分性得证，否则在G中删去C的各边，得到G: 一G一C。G1可能是非述通图，但每个结点的度保持为偶数。这时，G中一定存在某个度非 零的结点·同时，也是C中的结点。否则C的结点与(G的结点之间无边相连，与G是 连通图矛盾。同样理由，从：出发，G,中所在的连通支内存在一条简单回路(C,,显然C UC:仍然是G的一条简单回路，但它包括的边数比C多。继续以上构造方法，最终有简单 回路C=CUC,U…UC,它包含了G的全部边，即（是G的-一条欧拉回路。 以上采用了构造性证明的方法，即证明过程本身就给出了问题求解的步骤。 例2.3.1试找出图2.10的-条欧拉回路。 16
解：从任一点，比如1开始，可构造简 单回路C'=(e:,e6eg,e2)。G1=G-C中 的2,5度非零且是C中的结点，从v开 始G1中有简单回路C,=(e3er)。内此 CUC:=(e,e3,es,c4,eeg,e,e)包含了G 的所有边，即是G的一条欧拉回路。 推论2.3.1若无向连通图(G中只有 2个度为奇的结点，则(；存在欧拉道路。 证明：设和v,是两个度为奇数的结 点。作(，”二G十().则Gg巾各点的度 图2.10 都是偶数。由定理2.3.1（有欧拉可路， 它包含边()，删上该边，得到·条从出到，的简单道路，它恰好经过了G的所有边， 亦即是一条欧拉道路， 推论2.3.2若有向问连通图G中各结点的止，负度相等，则G存在有向欧拉问路。 其证明与定理2.3.1的证明相仿、 例2.3.2七桥问题中既不存在欧拉回路也不存在欧拉道路。 例2.3.3设连通图G=(V,E)有k个度为奇数的结点，证明E(G)可以划分成k/2 条简单道路。 证明：由性质1.1,2，是偶数。在这是个结点两两之间各加上-一条边，共增加/2条 边，得到（矿，G中各结点的度都为偶数。由定理2.3.1，（中有欧拉回路C,这/2条边都 在C上且不相邻接。删去这些边，则得到k/2条简单道路，它们包含了G的所有边。亦即 E(G)划分成了k/2条简单道路。 0000 X(000) 0001 1001 (001) (100) 0100 0010 不010) 0101 1010 1100 0011 (101) 1011 1101 0110 (01) (110) d 0111 1110 (111) 1111 图2.11 头12 例2.3.4一个编码盘分成16个相等的扇面，每个扇面分别由绝缘体和导体组或、 。17·
表示0和1两种状态，其中4,6，(，d四个位置的扇面组成~组二进制输出，如图2.11 所示。试问这16个二进制数的序列应如何排列，才恰好能组成0000到1111的16组四位 一进制输出，同时旋转-周后又返回到0000状态？ 解：我们发现如果从状态a1aaa,(a,=0或1)逆时针方向旋转一个扇面，那么新的输 出是a2a:4a5,其中有三位数字不变。因此以用8个结点表示从000到111这8个二进 制数。这样从结点(a-1a:a,-)可以到达结点(a,a、10)或（⑧，a+i1),其输出分别为(a:-a, a,-0)和(a:1a,a,+11),这样i可以得到图2.12。它是有向连通图，共有16条边，且每结点 的正、负度相等。由推论2.3.2，它存任有向欧拉回路。其中任一条都是原问题的解，比如 (0000101001101111)就是一种方案。 2.4 哈密顿道路与回路 十九世纪英国数学家哈密顿(Willian Hamilton)给出了关于一个凸12面体的数学游 戏，他把12面体的20个顶点比作世界上20个城市，30条棱 表小示这些城市之间的交通线路。如图2.13所示。哈密顿提出 能否周游此界，即从某个城市出发，经过每城一次且只一次最 后返回出发地，答案是显然的，比如图中的粗线边就表示了其 中一种方案。 对于任何连通图都可以提出类似问题。 定义2.4.1无向图的一条过全部结点的初级回路（道 路)称为G的哈密顿回路（道路），简记为H回路（道路）。 哈密顿回路是初级回路，而不是简单回路，因此它与欧拉 图2.13 问路的概念不同。当然在特殊情况下，G的一条哈密顿回路恰好也是其欧拉回路。鉴于H 回路是初级回路，所以如果G中含有重边或自环，别去它们之后得到简单图G,那么G和 G关于H回路（道路）的存在性是等价的。因此，判定H回路存在性问题一般都是针对简 单图。 例2.4.1完全图K.(n≥3)中存在H▣路。 例2.4.2图2.10的G中不存在H回路，但存在H道路。 有若干存在哈密顿回路（道路）的充分性定理。 定理2.4.1如果简单图G的任意两结点8，，之间恒有d(o,)十d(v,)≥n一1，则G 中存在哈密顿道路。 证明：先证G是连通图。若G非连通，则至少分为2个连通支H,H2,其结点数分别 为n1n2。从中各任取一个结点，，则d()≤n:-1,d(x,)≤n2一1。故d()十d()< n“1。矛盾。 以下证G存在H道路。设P一(u:,心2，)是(G中一条极长的初级道路，即和 ,的邻点都在P上。此时若l=n,P即为一条I1道路。若1<n,则可以证明G中一定存 在经过结点2，，的初级回路。否则，若边(，)∈E(G),就不能有(p)∈ E(G),不然删掉(。。！)，就形成了一条过这1个结点的初级回路。于是，设d()=, ·18·
则d(u)≤l一k一1，其中减去1表示不能与自身相邻.因此d(,)+d()<n一1。与已知 矛盾。所以存在经过2…，的初缴回路(C。 出丁C连通，所以存在C之外的结点：与C中的某点(，)相邻。删去(，-：，)，则 P=(,…,。-1,…,,-)是G中一条比P更长的初级道路。以P的两个端点u 和，-，继续扩充，可得到·条新的极长的初级道路。重复上述过程.因为(G是有穷图，所 以最终得到的初缴道路一定包含了C的全部结点，即是H道路。 图2.14 图2.15 推论2.4.1若简单图(G的任意两结点和，之间恒有d(,)十d(v)≥n,则G中 存在哈密顿回路。 证明：由定理2.4.1，G有H道路。设其两端点是v1和n,若(G不存在H回路，一定 有d(1)十d(℃.)≤n-1<n,产生矛盾， 推论24.2若简单图G每个结点的度都大于等于受，则G有H回路。 利用推论2.4.1即可得出结论。 以下介绍一个更强的H回路的存在性定理。 引理2.4.1设G是简单图，04，U,是不相邻结点，且满足d()十d(,)≥n。则G存 在H回路的充要条件是G+(:,)有H回路。 证明：必要性显然。现证充分性。假定(G不存在H回路，则G十(：，v;)的H回路一定 经过边(，0，)，删去(，v,),即G中存在一条以心，为端点的H道路，这时又有d()亠 d(v,)<n。与已知矛盾。 定义2.4.2若.和，是简单图(G的不相 邻结点，且满足d(u.)十d(v,)≥n,则令GC=C+ (:,℃)，对G重复上述过程，直至不再有这样的 结点对为止。最终得到的图称为G的闭合图，记 作C(G)。 例2.4.3图2.16(a)的闭合图是(b)。 理2.4.2简单图G的闭合图C(G)是唯 (a) (b) -的。 图2.16 证明：设C1(G)和C2(G)是G的两个闭合图， L1=ie1,e2…,e,},Ig={a1a2…,a,}分别是C(G)和C2(G)中新加入边的集合，可以证 明L=L2,即C(G)=C2(G),如若不然，不失-般性，设g+:=(u,)∈L:是构造C,(G)时 ·19·
第一条不属丁I的边，亦即e,-1在(2()。令H=(GUA,P…,,这时H是C:(G)也是 C,(G)的子图。由构造((G)时要加入e,s,成然1中满足d(u)十d()≥n,但(，v)年 C2(G),与((G)是G的闭合图矛盾。 定理2.4.2简单图G存在哈密顿回路的充要条什是其闭合图存在哈密顿间路。 证明：设C(G)=GUL1,L={e,2,…,e:.由引理2.4.1和2.4.2，G有H回路台 (;十，有H回同路一→…GU,行H回路。出C(G)唯一，故定理得证。 推论2.4,1和2.4.2都是定理2.4.2的自然结果， 推论2.4.3设G(n3)是简单图，若C(G)是完全图，则G有I1问路。 例2.4.4图2.16(a)有11回路。 例2.4.5设n(≥3)个人中，任两个人合在起都认识其余一2个人。证明这n个 人可以排成一队，使柑邻者都互相认识。 证明：每个人用一个结点表小术，相互认识则用边连接相应的结点，于是得到简单图(G。 若G中有Il道路，则问向题得证，由已知条件，对征意两点，，∈V(G),都有d()+d(,) 产n一2。此时若，与v,相识.即(，，)∈E(G).则d()二d(,)≥；若不相识，必存在 ∈V(G),满足(Ue),(;)∈E(G)。古则，设()年E(G),就出现，，合在起 不认识u,与原设矛盾。因此也有d(u,)+d(w)≥1一1。综上由定理2.4.1，G中存在H道 路。 例2.4.6证明图2.17中没有H间路。 证明：H回路是经过每个结点一次的初级回路、经观察， 如果给某个结点标以A,它的邻接点标以B,B的邻接点再标 以A,则可顺利标完G的全部结点。若G中有H凹路，该回 路一定是沿ABAB…AB走完全部结点，即标A与标B的结 点数相同，出于|V(G)'是奇数，因此G中没有H回路。 例2.4.7地图不存在相交的边界。如果一个驰图中有 2.17 H回路，则可以用4种不同颜色对它们的域进行着色，使相 邻的域染不同的颜色。 证明：我们用一个示意图加以直观的说明。设1（粗线 边)是G中的·个哈密顿回路，则H将G的域划分成回路内 外两部分。每部分的域用2种颜色可以染色，满足州邻域染 不同颜色。不然，一定存在二个以上的域互相邻接的情形。此 时必出现这样的结点。这与H是哈密顿回路相悖。因此结 论正确。 般情况下，给定一个图G,判定它是否存在H回路，需 图2.洛 要使用搜索法。首先去掉重边和白环，然后采用[DFS等算法 是以实现的。但是在最环情况下'其计算复杂度与n!成正比，它是属于NP(Nondeter- ministic Polynomial)完全问题。 ·20·