图论回路问题.pdf

回路问题图论欧拉图 （欧拉图 （E图）图）这里主要讨论图的遍历问题这里主要讨论图的遍历问题,一个是遍历过程中要求经过 的所有边都不同一个是遍历过程中要求经过 的所有边都不同;一个是遍历过程中要求经过的所有结点 都不同一个是遍历过程中要求经过的所有结点 都不同. 欧拉在欧拉在1736年发表了第一篇关于图论的论文年发表了第一篇关于图论的论文, 就是就 七 桥问题就是就 七 桥问题.ABCDA? ?B? ?C???? De1e5e7e6 e3e4e2定义定义:在无孤立结点的图G中,若存在一条回路,它 经过图中每条边一次且仅一次,称此回路为:在无孤立结点的图G中,若存在一条回路,它 经过图中每条边一次且仅一次,称此回路为 欧拉回路欧拉回路.称此图为.称此图为欧拉图欧拉图,或E图,或E图有欧拉回路:有欧拉回路: v v1 1v v2 2v v3 3v v4 4v v5 5v v2 2v v4 4v v6 6v v5 5v v3 3v v1 1如何判定一个图中是否有如何判定一个图中是否有 欧拉路,或有欧拉回路? 欧拉路,或有欧拉回路? v1???? v5v4? ?v2???? v3? ? v6a????bc????d1????43????2定理8.1 —个连通无间图G＝(T,G)具有欧拉回路的 充要条件是它的每一个结点的次数均为偶数。

证： 必要性 设G具有欧拉回路，用C表示这个回路，故G的所 有结点都在这个回路上，对任一结点，回路 C至少穿过它一次， (到达该结点和离开出结点称 为穿过结点一次)否则这个结点将是孤点，与题设 矛盾，而每穿过结点一次都将使结点的次数增加 2、因边是不重复的，故给点的次数一定是2的整 数倍，即为偶数Vv∈•充分性 设图G的每一结点次数均为偶数 (1)图的每一结点次数都是最小的偶数2，由于图是连通，因而只能有一个 回路，图是一个多边形，显然这个回路就是欧拉回路 (2)图的某些结点(或者所有结点)的次数是大于2的偶数，不妨用图(a)来描 述，则图至少有一个基本回路．例如图中的bdeb用c表示这个基本回 路，从 图G中去掉基本回路C得到子图G1，如图(b)所示，则G1各结点的 次数仍然都是偶数，如果G1已是一个基本回路(即每个结点的次数都是 2)，则命题得证这是因为图是连通酌，C1与C2必然有公共结点(但无 公共边)，从这个公共结点出发绕行C1一圈再绕行G1一圈即可回到原 点，显然这样绕行经过了所有的边一次而不重复，因而是欧拉回路E子图一个图不是E图，但它的子图可以是E 图，称为E子图如图表示图G及它的两个E 子图G1和G2定理8.2 若G1和G2是图G的E子图，则 G1⊕G2 也是G的E子图。

证： 令对中的任一结点设中与关联的边有 条记作而中与关联的边有条 记作 设但 与不在有相同的边, 因此此结点在中的次数为因为 G1和G2都是 E 图故和都是偶数则为偶数 推论设Gi(i=1,2,..,n)是E图，则G1⊕G2⊕… ⊕ Gn也是E图21'GGG⊕=reee22221,...,,stteee2)2(2) 1(2,...,,++tteeeeee2122122111,...,,===reee11211,...,,rtteee1)2( 1) 1( 1,...,,++tsrv2)deg(−+=1Gv1Gv2Gvrs'Grs)deg(v定理8.3 若P1和P2是同一对结点之间的两条简单路 径，则 P1⊕P2是E图 证： 设P1和P2是结点vi和vj之间的两条简单路径，我们 在vi与vj之间连一条边e, 显然P1∪{e} 是E 图，同理P2∪{e} , 也是E图，由定理8.2的推 论知 ( P1∪{e}) ⊕(P2∪{e}) 是E图 推论：若是同一干结点之间的简 单路径，则是E图 证：由本定理知，都是E图，又 由定理8.2的推论可知，它们的环和亦是E图)2,...,2,1(kipi=kPPPP2321....⊕⊕⊕⊕)(),...,(),(2124321kkpppppp⊕⊕⊕−Hamilton是英国数学家,在1959年,他提出Hamilton回路.H图Hamilton是英国数学家,在1959年,他提出Hamilton回路.H图 起源于一种游戏,这个游戏就是所谓周游世界问题.起源于一种游戏,这个游戏就是所谓周游世界问题. 当时哈密尔顿用一个正十二面体的20个顶点代表20个城，当时哈密尔顿用一个正十二面体的20个顶点代表20个城， 这个正十二面体同构于一个平面图如图所示。

要求从一个顶这个正十二面体同构于一个平面图如图所示要求从一个顶 点出发，沿着十二面体的棱经过每个顶点一次且仅一次最后点出发，沿着十二面体的棱经过每个顶点一次且仅一次最后 回到原点这个游戏曾经风靡一时，回到原点这个游戏曾经风靡一时， 它有若干个解，田中顶点用数字序它有若干个解，田中顶点用数字序 列表示的一条路径，就是其中的一列表示的一条路径，就是其中的一 个解即 l，2，3，4，5，6，7，8，9，l，2，3，4，5，6，7，8，9， 10，11，12，13，14，15，16，10，11，12，13，14，15，16， 17，18，19，20，117，18，19，20，1汉密尔顿图汉密尔顿图(H图图) (Hamilton图图)Hamilton是英国数学家,在1959年,他提出Hamilton回路.Hamilton是英国数学家,在1959年,他提出Hamilton回路. H图起源于一种游戏,这个游戏就是所谓周游世界问题.H图起源于一种游戏,这个游戏就是所谓周游世界问题. 例如,某个城市的街道如图所示:例如,某个城市的街道如图所示: 该城市的所有交叉路口都有形象各该城市的所有交叉路口都有形象各 异的精美的雕塑,吸引着许多游客,异的精美的雕塑,吸引着许多游客, 人人都想找到这样的路径:游遍各人人都想找到这样的路径:游遍各 个景点再回到出发点----H回路.个景点再回到出发点----H回路. 1.定义1.定义:设G=是个无向有限图,:设G=是个无向有限图, 汉密尔顿路汉密尔顿路:通过G中每个结点恰好一次的路.:通过G中每个结点恰好一次的路. 汉密尔顿回路(H回路)汉密尔顿回路(H回路):通过G中每个结点恰好一次的回路.:通过G中每个结点恰好一次的回路. 汉密尔顿图(H图):汉密尔顿图(H图):具有汉密尔顿回路(H回路)的图.具有汉密尔顿回路(H回路)的图.汉密尔顿图汉密尔顿图(H图图) (Hamilton图图)定理8.10定理8.10:(:(必要条件必要条件) 若图G=有H回路,则对V的任) 若图G=有H回路,则对V的任 何非空子有限集S, 均有W(G-S)≤|S|, 其中W(G-S)是从G何非空子有限集S, 均有W(G-S)≤|S|, 其中W(G-S)是从G 中删去S中所有结点及与这些结点关联的边所得到的子图中删去S中所有结点及与这些结点关联的边所得到的子图 的连通分支数.的连通分支数. 证：设C是图G的一条及回路，G5是V的任一非空子集。

对S 用归纳法证明证：设C是图G的一条及回路，G5是V的任一非空子集对S 用归纳法证明 如果S只有一个结点如果S只有一个结点，设为v1，特此结点从C中除去，显 然C，设为v1，特此结点从C中除去，显 然C—v1是一条连通的路径，子图(G一S)也是连通图， 即W(G-S)=|S|=1，式(*)成立v1是一条连通的路径，子图(G一S)也是连通图， 即W(G-S)=|S|=1，式(*)成立 如果S有两个结点如果S有两个结点，设为v1和v2．则去掉v1和v2之后，，设为v1和v2．则去掉v1和v2之后， C一S可能有两种情况：C一S可能有两种情况： (1)(1)v1与v2是邻接的v1与v2是邻接的，则C一S仍然是一条连通的路径， 子图(G一S)也是连通图，|S|=2 ,W(G-S)=1，式(*)成立则C一S仍然是一条连通的路径， 子图(G一S)也是连通图，|S|=2 ,W(G-S)=1，式(*)成立 (2)(2)v1与v2不邻接v1与v2不邻接，去掉v1和v2之后C被分成两段路径， 此时(G-S)可能仍然连通，最多被分成两个连通分支， 即W(G一S)有有H回路回路,则对则对V的任的任 何非空子有限集何非空子有限集S, 均有均有W(G-S)≤≤|S|, 其中其中W(G-S)是从是从G 中删去中删去S中所有结点及与这些结点关联的边所得到的子图中所有结点及与这些结点关联的边所得到的子图 的连通分支数的连通分支数. 证明证明:设设C是图是图G的一条的一条H回路回路, 它包含了它包含了G的所有结点的所有结点, 即即C 是是G的生成子图的生成子图.则对于则对于V的任何非空子集的任何非空子集S,C-S 也是也是G- S 的生成子图的生成子图, W(G-S)≤≤W(C-S), W(C-S) )≤≤|S|,故故 W(G-S)≤≤|S|. 用此定理可以判断一个图不是用此定理可以判断一个图不是H图图. 如右图如右图G, 取取 S={c} 不满足不满足 W(G-S)≤≤|S|. c????eb? ?a????d3.用用“最邻近法最邻近法”求求H回路回路 如果已经确定图如果已经确定图G有有H回路回路. a). 任选一个初始结点任选一个初始结点u,找一个最邻近找一个最邻近(或权最小或权最小)的结点的结点x. b). 设设x是新加入到这条路的结点是新加入到这条路的结点, 再从不在此路上的结点 中找到一个与再从不在此路上的结点 中找到一个与 x邻近邻近(或权最小或权最小)的结点的结点,加到此路中加到此路中. c).重复重复b), 直到直到G中所有结点都在此路上中所有结点都在此路上. d).最后再回到起点最后再回到起点, 构成回路构成回路. 就是就是H回路回路. 例如例如右图 初始结点为右图 初始结点为a, 逐渐选邻近结点逐渐选邻近结点c,e,d,b,a. 得得H回路回路acedba. 此回路的总权为此回路的总权为:20 但是对带权图来说但是对带权图来说,此方法求的此方法求的H回路不一定是最短的回路不一定是最短的. 例如例如,实际上此图最短的实际上此图最短的H回路是回路是 acebda总权为总权为17? ?ab????ec????d123 45678910本节重点掌握本节重点掌握: 欧拉路及欧拉回路的判定欧拉路及欧拉回路的判定, 能求欧拉路 和欧拉回路能求欧拉路 和欧拉回路. H路及路及H回路的判定回路的判定, 能求能求H路和路和H回路回路. 以及欧拉图和汉密尔顿图的应用以及欧拉图和汉密尔顿图的应用.作业作业 P311 (1) (2) (6)3.有欧拉路与有欧拉回路的判定有欧拉路与有欧拉回路的判定: 定理定理8-5.1:无向图无向图G具有欧拉路具有欧拉路,当且仅当当且仅当G是连通的是连通的,且有且有 零个或两个奇数度的结点零个或两个奇数度的结点. *证明证明:必要性必要性, 设设G有欧拉路有欧拉路.(见教材见教材P302) 充分性充分性,(证明的过程就是一个构造欧拉路的过程证明的过程就是一个构造欧拉路的过程) 如果如果G有两个奇数度结点有两个奇数度结点:就从一个奇数度结点出发就从一个奇数度结点出发,每每 当到达一个偶数度结点当到达一个偶数度结点,必然可以再经过另一条边离开此必然可以再经过另一条边离开此 结点结点,如此重复下去如此重复下去,经过所有边后到达另一个奇数度结点经过所有边后到达另一个奇数度结点 如果如果G无奇数度结点无奇数度结点,则可以从任何一个结点出发则可以从任何一个结点出发,去构去构 造一条欧拉路造一条欧拉路.推论推论:无向图无向图G具有欧拉回路具有欧拉回路, 当且仅当当且仅当G是连通的是连通的,且所有结点的度都是偶数且所有结点的度都是偶数.a????bc????d1????24????3从此推论得知从此推论得知,七桥问题的图不是欧拉图七桥问题的图不是欧拉图. 4.求欧拉回路的算法求欧拉回路的算法:A? ?B? ?C???? De1e5e7e6 e3。