20220902第十五章欧拉图与哈密顿图

漳州师范学院计算机科学与工程系第十五章欧拉图与哈密顿图第十五章欧拉图与哈密顿图欧拉图哈密顿图最短路问题与货郎担问题知识点：欧拉图、汉密尔顿图、Fleury算法、Dijkstra

算法、货郎担问题。教学要求：深刻理解和掌握欧拉图与汉密尔顿图的性质。教学重点：欧拉图与汉密尔顿图的性质。学时:2§15.1欧拉图两个与可行遍问题有关的问题一个要求行遍图的每条边恰好一次,这就是欧拉回路问题,对应的图称为欧拉图一个要求行遍图的每个顶点恰好一次,这就是哈密顿圈问题,对应的图称为哈密顿图

ABCD哥尼斯堡七桥问题周游世界问题®§15.1欧拉图定义15.1通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路.通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路.具有欧拉回路的图称为欧拉图具有欧拉通路而无欧拉回路的图称为半欧拉图规定平凡图是欧拉图定理15.1无向图G是欧拉图当且仅当G是连通图且没有奇度顶点定理15.2无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点®§15.1欧拉图定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度定理15.4有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点,其中一个顶点的入度比出度大1,另一个顶点出度比入度大1,而其余顶点入度等于出度定理15.5G是非平凡的欧拉图当且仅当G是连通的且是若干个边不重的圈的并彼德森图K3,3K5®§15.1欧拉图Fleury(弗罗莱)算法⑴任取v0∈V(G),令P0=v0,i=0⑵设Pi=v0e1v1e2…eivi

,

如果E(G)-{e1,

e2,

…,ei}中没有与vi关联的边,则计算停止。否则按下述条件从E(G)-{e1,

e2,

…,ei}中任取一条边ei+1(a)ei+1和vi相关联;(b)除非没有别的边可选择,

否则ei+1不是Gi=G–{e1,e2,…,ei}中的割边(桥)

设ei+1=(vi,vi+1),把ei+1vi加入Pi得到Pi+1⑶令i=i+1,返回(2)®§15.1欧拉图例

应用Fleury算法求图G的一个欧拉回路v6v5v4v3v2v1e7e5e4e3e2e1e6e8Gv6v5v4v3v2v1e7e5e4e3e2e1e8G1v6v5v4v3v2v1e5e4e3e1e8e2G2v6v5v4v3v2v1e5e4e3e1e2G3v6v5v4v3v2v1e4e3e1e2G4v6v5v4v3v2v1e4e1e2G5v6v5v4v3v2v1e1e2G6v6v5v4v3v2v1e1G7W0=v0W1=v0e6v5W2=v0e6v5e7v6W3=v0e6v5e7v6e8v1W4=v0e6v5e7v6e8v1e5v3W5=v0e6v5e7v6e8v1e5v3e3v4W6=v0e6v5e7v6e8v1e5v3e3v4e4v3W8=v0e6v5e7v6e8v1e5v3e3v4e4v3e2v2e1v1W7=v0e6v5e7v6e8v1e5v3e3v4e4v3e2v2®§15.2哈密顿图定义15.2通过图(无向图或有向图)中所有顶点一次且仅一次的通路称为哈密顿通路.通过图(无向图或有向图)中所有边一次且仅一次的回路称为哈密顿回路(哈密顿圈).具有哈密顿回路的图称为哈密顿图具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图规定平凡图是哈密顿图彼德森图K3,3K5®§15.2哈密顿图定理15.6设无向图G=<V,E>是哈密顿图,则对于任意

V1⊂V且V1≠

,均有p(G-V1)≤|V1|推论设无向图G=<V,E>是半哈密顿图,则对于任意

V1⊂V且V1≠

,均有p(G-V1)≤|V1|+1可用来判别图G不是哈密顿图,但是这个方法并不总是有效

删去三个黑点后得到的图具有四个连通分支，所以原图不是哈密顿图右图不是哈密顿图,但任意删去V的非空真子集S,都有

p(G–S)

|S|所以用定理15.6判别一个图不是哈密顿图并不总是有效®§15.2哈密顿图定理

若G是简单图,且n

3,

,则G是哈密顿图定理15.7设G是n阶无向简单图,若对于G中任何两个不相邻的顶点u和v,都有

d(u)+d(v)

n-1,n

3

则G中存在哈密顿通路推论设G是n(n

3)阶无向简单图,若对于G中任何两个不相邻的顶点u和v,都有

d(u)+d(v)

n,n

3

则G中存在哈密顿回路®§15.2哈密顿图彼德森图®§15.2哈密顿图欧拉图与哈密顿图的判别方法全体非空连通图满足定理15.1的条件不满足定理15.1的条件欧拉图非欧拉图全体非空连通图哈密顿图非哈密顿图满足任何必要条件但不满足任何充分条件至少满足一个充分条件至少不满足一个必要条件不能根据已知的充分条件或已知的必要条件判别是否是哈密顿图根据给定的图的特点采用特定的方法1.若能找到哈密顿圈则它是哈密顿图2.(反证法)假设存在一个哈密顿圈,如果导致发生矛盾,则它不是哈密顿图3.暂时无法判别®§15.3最短路问题与货郎担问题定义15.3设图G=<V,E>(无向图或有向图),给定W:ER,对G的每一条边e,称W(e)为边e的权这样的图称为带权图,记作G=<V,E,W>

当e=(u,v)时,把W(e)记作W(u,v)设P是G中一条通路,P中所有边的权之和称为P的长度记作W(P),类似地定义回路的长度W(C)设带权图G=<V,E,W>(无向图或有向图),其中每一条边e的权W(e)为非负实数,∀u,v∈V,当u和v连通(u可达v)时,称从u到v长度最短的路径为从u到v的最短路径称其长度为从u到v的距离,记作d(u,v)

约定d(u,u)=0,当u和v不连通(u不可达u)时d(u,v)=∞®§15.3最短路问题与货郎担问题最短路问题:给定带权图G=<V,E,W>及顶点u和v,其中每一条边e的权W(e)为非负实数,求从u到v的最短路径Dijkstra标号法输入:带权图G=<V,E,W>和s∈V,其中|V|=n,∀e∈E,W(e)≥0输出:s到G中每一点的最短路径及距离

1.令l(s)(s,0),l(v)(s,+∞)(v∈V-{s}),i1,

l(s)是永久标号,其余标号均为临时标号,us2.for与u关联的临时标号的顶点v3.ifl2(u)+W(u,v)<l2(v)then令l(v)(u,l2(u)+W(u,v))4.计算l2(t)=min{l2(v)|v∈V且有临时标号},把l(t)改为永久标号

5.ifi<nthen令ut,ii+1,转2®§15.3最短路问题与货郎担问题例15.6带权图G如图15.10所示,

求从v1到其余各点的最短路径和距离解用Dijkstra标号法求解,计算过程如下表所示v2v1v3v4v53572262v6v72338步骤

v1v2v3v4v5v6v71(v1,0)**(v1,+∞)(v1,+∞)(v1,+∞)(v1,+∞)(v1,+∞)(v1,+∞)2(v1,0)*(v1,3)**(v1,7)(v1,5)(v1,+∞)(v1,+∞)(v1,+∞)3(v1,0)*(v1,3)*(v2,5)**(v1,5)(v2,9)(v1,+∞)(v1,+∞)4(v1,0)*(v1,3)*(v2,5)*(v1,5)**(v3,8)(v1,+∞)(v1,+∞)5(v1,0)*(v1,3)*(v2,5)*(v1,5)*(v3,8)(v4,7)**(v3,13)6(v1,0)*(v1,3)*(v2,5)*(v1,5)*(v3,8)**(v4,7)*(v6,9)7(v1,0)*(v1,3)*(v2,5)*(v1,5)*(v3,8)(v4,7)*(v6,9)**®§15.3最短路问题与货郎担问题货郎担问题(旅行商问题):

有n个城市,给定城市之间道路的长度(长度可以为∞,对应这两个城市之间无交通线).一个旅行商从某个城市出发,要经过每个城市一次且