离散课件 15欧拉图与哈密顿图

第十五章

欧拉图与哈密顿图15.1欧拉图15.2哈密顿图15.3最短路问题与旅行商问题定义1.

通过无向(有向)图中所有边恰好一次的通路(回路)称为欧拉通路(回路).定义2.

具有欧拉回路的图称为欧拉图.定义3.

具有欧拉通路而无欧拉回路的图称为半欧拉图.15.1欧拉图此图无欧拉通路,也无欧拉回路.前者是半欧拉图,后者是欧拉图.例1.

判断下列图形是否为欧拉图或半欧拉图.定理1.

无向图G是欧拉图当且仅当G是连通图且无奇度顶点.定理2.

无向图G是半欧拉图当且仅当G是连通图且恰有两个奇度顶点.注:两个奇度顶点即为欧拉通路的端点.例2.

判断下列图形是否为欧拉图或半欧拉图.欧拉图半欧拉图都不是例3.

(蚂蚁比赛问题)甲、乙蚂蚁分别位于下图中的结点a,b处,并设图中边长度是相等的.甲、乙进行比赛:从它们所在的顶点出发,走过图中所有边最后到达顶点c处.如果它们速度相同,问谁先到达目的地?乙定理3.

有向图D是欧拉图当且仅当D是强连通图且每个顶点入度与出度相等.定理4.

有向图D是半欧拉图当且仅当D是单向连通图且除了两个顶点外,其余顶点入度与出度相等;这两个特殊顶点:一个顶点的入度比出度大1,一个顶点的出度比入度大1.例4.

判断下列有向图是否欧拉图或半欧拉图.都不是半欧拉图欧拉图一笔画问题:从某点出发,不间断地画完整个图.即在图中找出欧拉通路（回路）.Fleury算法:(1)任取v0∊V(G),(2)设Pi=v0e1v1e2eivi,若E(G)-{e1,e2,ei}中没有与vi关联的边,则计算停止;否则在vi关联的边中优先选择非桥的边添加.(3)令i=i+1,返回(2).基本思想：能不走桥就不走桥15.2哈密顿图定义1.

经过无向(有向)图中所有顶点恰好一次的路(圈)称为哈密顿路(圈).定义2.

具有哈密顿圈的图称为哈密顿图.定义3.

具有哈密顿路但不具有哈密顿圈的图称为半哈密顿图.例1.

判断下列图形是否哈密顿图或半哈密顿图.半哈密顿图哈密顿图都不是例2.

举行一个国际会议,有A,B,C,D,E,F,G七人,已知：A会讲英语；B会讲英语和汉语；C会讲英语、意大利语和俄语；D会讲日语和汉语；E会讲德语和意大利语；F会讲法语、日语和俄语；G会讲法语和德语.试问应如何安排这七人座位使得每个人都能和他身边的人交谈？解：用点代表人，两人能交谈则连边.问题转化为在图中找一条哈密顿回路.ABDFGECA即可.哈密顿图的判定定理1(必要条件):设无向图G=<V,E>是哈密顿图,V1是V的任意非空子集,则p(G-V1)≤V1.推论:设无向图G=<V,E>是半哈密顿图,V1是V的任意非空子集,则p(G-V1)≤V1+1.在Peterson图中,虽然对任意顶点集V1,都满足p(G-V1)|V1|,但它不是哈密顿图.定理2(充分条件):设G＝<V,E>是无向简单图.若对任意两个不相邻顶点u,vV,均有d(u)+d(v)|V|-1,则G中存在哈密顿路；若对任意两个不相邻顶点u,vV,均有d(u)+d(v)|V|,则G是哈密顿图.推论:

n阶无向简单图G中,n>2,(G)n/2,则G是哈密顿图.图中任意两个顶点的度数之和为4,顶点数为6,即有4<6,但它是哈密顿图.定理3.

n(n2)阶竞赛图都有哈密顿路.例2.

某地有5个风景点，若每个风景点均有2条道路与其他风景点相通.问游人可否经过每个风景点恰好一次而游完这5处？思路：利用定理2，图中存在哈密顿路，故可以.15.3最短路问题与旅行商问题最短路问题:给出一个连接各城镇的铁路网络,在这个网络的两个指定城镇之间确定一条最短路线.图论问题:G=<V,E,W>是n阶无向(有向)图,其中W是从E到R+的函数(即直接相连的城镇之间的铁路距离).求出赋权图上两个指定点之间具有最小权的路.1445642537v0v1v2v3v4v5例1.

对下面有向图求顶点v0到其余顶点的最短路.迭代次数v0v1v2v3v4v5记录00v014.01.0v224.07.28.2v138.16.18.2v448.18.2v358.2v5最短路权041868生长点v0v0v0v1v1v2旅行商问题:一个商人希望去访问n个城市中的每一个,开始和结束于城市v1.任意两个城市间都有一条直接通路,我们记城市vi到城市vj的距离为W(i,j).设计一个算法,找出商人能走的最短路径.图论问题:G=<V,E,W>是n阶无向完全图,其中W是从E到R+的函数,对V中任意三点vi,vj,vk满足W(vi,vj)+W(vj,vk)≥W(vi,vk)求出赋权图上的最短哈密顿圈.旅行商问题至今无有效算法,但已找到近似算法.最邻近算法为旅行商问题找到近似解.最邻近算法:(1)选任意点作为始点,找出一个与始点最近的点,形成一条边的初始路径.(