1、第二章 道路与回路 2.1道路与回路,定义2.1.1有向图G=(V,E)中,若边序列P=(ei1, ei2, , eiq),其中eik=(vl, vj) 满足vl是eik-1的终点, vj 是eik+1的始点，就称P是G的一条有向道路.如果eiq的终点也是ei1的始点，则称P是G的一条有向回路,道路与回路,如果P中的边没有重复出现，则分别称为简单有向道路和简单有向回路 进而, 如果P中结点也不重复出现, 又分别称它们是初级有向道路和初级有向回路, 简称为路和回路 显然,初级有向道路(回路)一定是简单有向道路(回路),有向道路,(e1, e2, e5, e1) 有向道路，不是简单有向道路 (e1
2、, e2, e5, e4) 简单有向道路，不是初级有向道路(A) (e1, e2, e3) 初级有向道路 (e1, e2, e5) 初级有向回路,道路与回路,定义2.1.2无向图G=(V, E)中，若点边交替序列P=(vi1, ei1, vi2, ei2, , eiq-1, viq)满足vik, vik+1是eik的两个端点, 则称P是G中的一条链或道路. 如果viq=vi1, 则称P是G中的一个圈或回路 如果P中没有重复出现的边, 称之为简单道路或简单回路, 若其中结点也不重复, 又称之为初级道路或初级回路,例,V1到v4的初级道路,v1,e1,v2,e6,v5,e4,v4,e7,v2,V1
3、到v2的简单道路,道路与回路,定义2.1.31. 设G是无向图, 若G的任意两结点之间都存在道路, 就称G是连通图, 否则称为非连通图2. 如果G是有向图, 不考虑其边的方向, 即视为无向图, 若它是连通的, 则称G是连通图3. 若连通子图H不是G的任何连通子图的真子图, 则称H是G的极大连通子图或称连通支显然G的每个连通支都是它的导出子图,连通图,连通图,A,B,C,D,非连通图 两个连通分支B, A, C, D,道路与回路,定义2.1.4设C是简单图G中含结点数大于3的一个初级回路，如果结点vi和vj在C中不相邻，而边(vi,vj)E(G)，则称(vi,vj)是C的一条弦。,道路与回路,证
4、明：若对简单图G中每一个vkV(G)，都有d(vk)3，则G中必含带弦的回路。 证明：在G中构造一条极长的初级道路P=(v0, ei1, v1, ei2, , vl-1, eil, vl)。由于P是极长的初级道路，所以v0和vl的邻接点都在该道路P上。由已知条件，d(vk)3，不妨设(v0)=v1, vij, vik, , 其中1jk，这时(v0, v1, , vik, v0)是一条初级回路，而(v0, vij)就是该回路中的一条弦。,带弦回路,1. 构造极长初级道路 (v0, v1), (v0, v1, v2), (v0, v1, v2, v3), (v0, v1, v2, v3, v4)
5、2. (v0)=v1,v2,v3,v4 3. (v0,v1,v2,v3,v0)即为所求的初级回路，而(v0,v2)就是该回路的一条弦,极长初级道路,极长初级道路: 在无向简单图G=中, E,设1=v0v1vl为G中一条初级道路,若路径的两个端点v0和vl不与初级道路本身以外的任何结点相邻, 这样的初级道路称为极长初级道路(有向图中, 初级道路起点的前驱, 终点的后继, 都在初级道路本身上),扩大初级道路法,扩大初级道路法: 任何一条初级道路, 如果不是极长初级道路, 则至少有一个端点与初级道路本身以外的结点相邻, 则将该结点及其相关联的边扩到新的初级道路中来, 得到更新的初级道路。继续上述过程
6、, 直到变成极长初级道路为止,道路与回路,定义2.1.5设G=(V,E)是无向图，如果V(G)可以划分为子集X和Y，使得对所有的e=(u,v)E(G), 都有u和v分属于X和Y，则称G是二分图(偶图)。完全二分图 完全二分图K3,3,道路与回路,证明：如果二分图G中存在回路，则它们都是由偶数条边组成的。证明：设C是二分图G的任一条回路，不妨设v0X 是C的始点，由于G是二分图，所以沿回路C必须经过偶数条边才能达到某结点viX，因而只有经过偶数条边才能回到v0。,道路与回路,证明：设G是简单图，当m(n-1)(n-2)/2时，G是连通图。 证明：假定G是非连通图，则它至少含有2个连通分支。设分别
7、是G1=(V1,E1), G2=(V2,E2)。其中|V1(G1)|=n1, |V2(G2)|=n2, n1+n2=n, |E1(G1)|+|E2(G2)|=m。由于G是简单图，因此,道路与回路,由于1n1n-1, 1n2n-1 所以 与已知条件矛盾，故G是连通图。,2.3 欧拉道路与回路,1736年瑞士著名数学家欧拉(Leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”成功地回答了，图中是否存在经过每条边一次且仅一次的回路 人们普遍认为欧拉是图论的创始人 1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著有限图与无限图理论，这是图论发展史上的重要的里程碑，
8、它标志着图论将进入突飞猛进发展的新阶段,哥尼斯堡七桥问题,哥尼斯堡城（现在俄罗斯）在18世纪属东普鲁士，它位于普雷格尔（Pregel）河畔，河中有两个岛，通过七座桥彼此相联，如下图：,当时城中居民热衷于这样一个问题：游人从四块陆地中任一块出发，按什么样的线路方能做到每座桥通过一次且仅一次而最后返回原地。,1736年，瑞士数学家列昂哈德. 欧拉(Leonhard Euler) 仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象的图形来描述，其中的四块陆地分别用四个点表示，而陆地之间有桥相连者则用连结两个点的边表示。,欧拉得出结论：哥尼斯堡桥问题是 无解的，即一个人不可能一次走遍 两岛
9、、两旁陆地和七座桥。,一笔画,欧拉道路与回路,定义2.3.1无向连通图G=(V, E)中的一条经过所有边的简单回路(道路)称为G的欧拉回路(道路) 定理2.3.1无向连通图G存在欧拉回路的充要条件是G中各结点的度都是偶数,欧拉道路与回路,定理2.3.1的证明： 必要性：若G中有欧拉回路C，则C过每条边一次且仅一次对任一结点v来说，如果C经过ei进入v，则一定通过另一条边ej从v离开. 因此结点v的度是偶数 充分性：由于G是有穷图，因此可以断定，从G的任一结点v0出发一定存在G的一条简单回路C. 这是因为各结点的度都是偶数，所以这条简单道路不可能停留在v0以外的某个点，而不能再向前延伸以致构成回
10、路C,定理2.3.1充分性证明,如果E(G)=C, 则C就是欧拉回路，充分性得证。 否则在G中删去C的各边，得到G1=G-C。 G1可能是非连通图，但是每个结点的度保持为偶数。这时，G1中一定存在某个度非零的结点vi, 同时vi也是C中的结点。否则C的结点与G1的结点之间无边相连，与G是连通图矛盾。 同理，从vi出发，G1中vi所在连通分支内存在一条简单回路C1。显然，CC1仍然是G的一条简单回路，但它包括的边数比C多。 继续以上构造方法，最终有简单回路C= CC1Ck ，它包含了G的全部边，即C是G的一条欧拉回路,构造欧拉回路,C=(e1,e6,e8,e7,e2) C=(e3,e5,e4)C
11、C=(e1,e3,e5,e4,e6,e8,e7,e2)=E(G),v2,v4,v5,v3,v1,v2,v4,v5,e2,v1,e1,e6,e5,e7,e8,e4,e3,e5,e4,e3,v3,欧拉道路与回路,推论2.3.1若无向连通图G中只有2个度为奇的结点,则G存在欧拉道路.证明：设vi和vj是两个度为奇数的结点. 作G=G+(vi, vj), 则G中各点的度都是偶数. 由定理2.3.1, G有欧拉回路, 它含边(vi, vj), 删去该边, 得到一条从vi到vj的简单道路, 它恰好经过了G的所有边, 亦即是一条欧拉道路,欧拉道路与回路,结论：七桥问题既不存在欧拉回路也不存在欧拉道路。 推论
12、2.3.2若有向连通图G中各结点的正、负度相等, 则G存在有向欧拉道路.其证明与定理2.3.1的证明相仿,欧拉道路与回路,例2.3.3 设连通图G=(V,E)有k个度为奇数的结点，那么E(G)可以划分成k/2条简单道路。 证明：由性质1.1.2，k是偶数。在这k个结点间增添k/2条边，使每个结点都与其中一条边关联，得到G，那么G中各结点的度都为偶数。由定理2.3.1，G包含一个欧拉回路C。而新添的k/2条边在C上都不相邻。所以删去这些边后，我们就得到由E(G)划分成的k/2条简单道路。,举例,欧拉回路(1,2,3,4,5,6,7,8,9) 2(=4/2)条简单道路(3,4)和(6,7,8,9,
13、1),一笔画,某图形是否可以一笔画出 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点 其他情况的图都不能一笔画出, 但是奇点数除以二便可算出此图需几笔画成,编码盘,一个编码盘分成16个相等的扇面，每个扇面分别由绝缘体和导体组成，可表示0和1两种状态，其中a,b,c,d四个位置的扇面组成一组二进制输出，如下图所示。试问这16个二进制数的序列应如何排列，才恰好能组成0000到1111的16组二进制输出，同时旋转一周后又返回到0000状态？,a2
14、,a1,a4,a3,a16,a5,a,b,c,d,编码盘,解答：如果从状态a1a2a3a4(ai=0或1)逆时针方向旋转一个扇面，那么新的输出是a2a3a4a5，其中有三位数字不变。因此可以用8个结点表示从000到111这8个二进制数，这样从结点(ai-1aiai+1)可以到达结点(aiai+10)或(aiai+11)，其输出分别是(ai-1aiai+10)和(ai-1aiai+11)，这样可以得到下图。,编码盘,编码盘,解答：该图是有向连通图，共有16条边，且每结点的正、负度相等。有推论2.3.2，它存在有向欧拉回路。其中任一条都是原问题的解，比如(0000 1010 0110 1111)就
15、是一个方案。0000, 0001, 0010, 0101,1010, 0100, 1001, 0011, 0110, 1101, 1011, 0111, 1111, 1110, 1100, 1000.,作业一,P35 1; 2; 3; 6,2.4 哈密顿道路与回路,19世纪英国数学家哈密顿提出的问题： 一个凸12面体，把20个顶点比作世界上20个城市，30条棱表示这些城市间的交通路线。 问：能否周游世界，即从某个城市出发，经过每城一次且只一次最后返回出发地。,哈密顿道路与回路,答案：,哈密顿道路与回路,定义2.4.1无向图的一条过全部结点的初级回路(道路)称为G的哈密顿回路(道路),简记为H为
16、回路(道路) 哈密顿回路是初级回路，是特殊的简单回路，因此它与欧拉回路不同。当然在特殊情况下，G的哈密顿回路恰好也是其欧拉回路 鉴于H回路是初级回路，所以如果G中含有重边或自环，删去它们后得到的简单图G，那么G和G关于H回路（道路）的存在性是等价的。因此，判定H回路存在性问题一般是针对简单图的,充分条件和必要条件,满足充分条件，判断是(是哈密顿图) 不满足必要条件，判断否(不是哈密顿图)不满足充分条件，不能判断否(不是哈密顿图) 满足必要条件，不能判断是(是哈密顿图),引理*：设P=(v1, v2, , vl)是图G中一条极长的初级道路(即v1和vl的邻点都在P上)而且d(v1)+d(vl)l
17、，则G中一定存在经过结点v1, v2, , vl的初级回路。 证明：反证法。若边(v1,vp)E(G), 就不能有(vl, vp-1)E(G)，不然删除(vp, vp-1)，就形成了一条过这l个结点的初级回路。于是，设d(v1)=k，则d(vl)l-k-1(其中减去1表示不能与自身相邻)。因此d(v1)+d(vl)l-1 。与已知矛盾。所以存在经过结点v1, v2, , vl的初级回路C。,哈密顿道路与回路-引理*,哈密顿道路与回路-引理*,哈密顿道路与回路-充分性定理1,定理2.4.1如果简单图G的任意两结点vi, vj之间恒有 d(vi)+d(vj)n-1则G中存在哈密顿道路 证明: 先证
18、G是连通图。若G非连通，则至少分为2个连通支H1, H2，其结点数分别为n1, n2。从中各任取一个结点vi, vj，则d(vi)n1-1， d(vj)n2-1。故d(vi)+d(vj)n-1。矛盾。,以下证G存在H道路。设P=(vi1, vi2, , vil)是G中一条极长的初级道路，即vi1和vil的邻点都在P上。此时， 若l=n, P即为一条H道路 若ln，则可以证明G中一定存在经过结点vi1, vi2, , vil的初级回路。(CLAIM)否则，若边(vi1,vip)E(G), 就不能有(vil, vip-1)E(G)，不然删除(vip, vip-1)，就形成了一条过这l个结点的初级回
19、路。于是，设d(vi1)=k，则d(vil)l-k-1(其中减去1表示不能与自身相邻)。因此d(vi1)+d(vil) l-1 n-1。与已知矛盾。所以存在经过结点vi1, vi2, , vil的初级回路C。,哈密顿道路与回路-充分性定理1,哈密顿道路与回路-充分性定理1,由于G连通，所以存在C之外的结点vt与C中某点(viq)相邻。删去(viq-1, viq)，则P=(vt, viq, , vip-1, vil, , vip, vi1, , viq-1)是G中一条比P更长的初级道路。以P的两个端点vt和viq-1继续扩充，可得到一条新的极长的初级道路。重复上述过程，因为G是有穷图，所以最终得
20、到的初级道路一定包含了G的全部结点，即是H道路。,哈密顿道路与回路-充分性定理1,哈密顿道路与回路-充分性定理1,推论2.4.1若简单图G的任意两结点vi和vj之间恒有 d(vi)+d(vj)n则G中存在哈密顿回路 证明：由定理2.4.1，G有H道路。设其两端点是v1和vn，若G不存在H回路，根据引理*证明，一定有：若d(v1)=k, 则d(vn)n-k-1，那么d(v1)+d(vn)n-1n，与已知矛盾。 推论2.4.2若简单图中每个结点的度都大于等于n/2，则G有H回路 证明：由推论2.4.1可得。,哈密顿道路与回路,定义2.4.2若vi和vj是简单图G的不相邻结点，且满足d(vi)+d(
21、vj)n, 则令G=G+(vi, vj). 对G重复上述过程，直至不再有这样的结点对为止最终得到的图为G的闭合图，记作C(G).,G,C(G),哈密顿道路与回路,引理2.4.1简单图G的闭合图C(G)是唯一的。 证明：设C1(G)和C2(G)是G的两个闭合图，L1=e1, e2, , er, L2=a1, a2, ,as分别是C1(G)和C2(G)中新加入边的集合，可以证明L1=L2, 即C1(G)=C2(G)。如若不然，不失一般性，设ei+1=(u,v)L1是构造C1(G)时第一条不属于L2的边，亦即ei+1L2 。令H=Ge1, e2, , ei,这时H是C1(G)也是C2(G)的子图。由
22、于构造C1(G)时要加入ei+1，显然H中满足d(u)+d(v)n，但是(u,v)C2(G)，与C2(G)是G的闭合图矛盾。,哈密顿道路与回路,引理2.4.2设G是简单图, vi,vj是不相邻结点，且满足d(vi)+d(vj)n. 则G存在H回路的充要条件是G+(vi, vj)有H回路 证明：必要性显然。现证充分性。假定G不存在H回路，则G+(vi,vj)的H回路一定经过边(vi,vj)，删去(vi,vj)，即G中存在一条以vi,vj为端点的H道路，这时又有d(vi)+d(vj)n，与已知矛盾。,哈密顿道路与回路-充分性定理2,定理2.4.2简单图G存在哈密顿回路的充要条件是其闭合图存在哈密顿
23、回路 证明：设C(G)=GL1, L1=e1, e2, , et, 由引理2.4.1和引理2.4.2， G有H回路G+e1有H回路 GL1有H回路 由于C(G)是唯一的，故定理得证。 推论2.4.3设G(n3)是简单图, 若C(G)是完全图, G有H回路 说明:d(vi)+d(vj)=(n-1)+(n-1)=n+(n-2),哈密顿道路与回路,举例：设n(3)个人中，任两个人合在一起都认识其余n-2个人。证明这n个人可以排成一队，使相邻者都互相认识。 证明：每个人用一个结点表示，相互认识则用边连接相应的结点，于是得到简单图G。若G中有H道路，则问题得证。由已知条件，对任意两点vi, vjV(G)
24、，都有d(vi)+d(vj)n-2。此时， (1)若vi和vj相识，即(vi,vj)E(G), 则d(vi)+d(vj)n (2) 若vi和vj不相识，必存在vkV(G)，满足(vi,vk), (vj,vk) E(G)。否则，设(vi,vk)E(G)，就出现vk, vj合在一起不认识vi，与已知矛盾。因此也有d(vi)+d(vj)n-1 综上由定理2.4.1，G中存在H道路。,哈密顿道路与回路-必要性定理,必要性定理：若G是H-图，则对于V的每个非空真子集S，均有W(G-S)|S|，其中W(G-S)是G-S中连通分支数。 证明：设C是G的H-回路，则对于V的每个非空真子集S均有W(C-S)|S
25、|。而C-S是G-S的生成子图，故W(G-S)W(C-S),因此W(G-S)|S|。 以K4为例。,哈密尔顿图,例 判定下面三个图是否是哈密尔顿图.,a,a,哈密尔顿图,在G1中，令S=a,b,c,d,e，则W(G1-S)=6，由必要性定理知, G不是哈密尔顿图。 在G2中令S=a,b,c，则W(G2-S)=4，所以G2也不是哈密尔顿图。 G3称为彼得森图。可以证明它不是哈密尔顿图, 但对它的任意顶点子集S, 有W(G3-S)|S|。这说明必要性定理中的条件, 只是哈密尔顿图的一个必要条件，而不是充分条件 与彼得森图同构的图也一定不是哈密尔顿图,哈密尔顿图,对于一个H-图，如果可以用A, B交替标记所有的顶点，则有|A|=|B|(即A,B个数相同) 对于一个图如果无法用A, B交替标记顶点，也无法判断是否是H-图。例如：,A,B,B,判断哈密尔顿图,如果一个图不满足充分条件，但是又满足必要条件，如何判定其是否是哈密尔顿图？ 对于一个点，若有两条连接线都在H-图中，则其它的边不在H-图中,作业二,P35 8,
