《离散数学课件》3带权、欧拉、哈密顿

1、1/81 上节课内容上节课内容(一一) 通路、简单通路、初等通路通路、简单通路、初等通路(二二)回路、回路、 简单回路、初等回路简单回路、初等回路(三三) 连通图连通图 单侧连通、强连通单侧连通、强连通 点割集、边割集点割集、边割集(四四) 图的矩阵表示图的矩阵表示 关联矩阵（有向、无向（无环）关联矩阵（有向、无向（无环） 邻接矩阵（有向、无向）邻接矩阵（有向、无向） 可达矩阵（有向）可达矩阵（有向） 2/819.3 带权图与带权图中的最短通路带权图与带权图中的最短通路(一一) 带权图带权图(二二) 最短通路问题最短通路问题(三三) 狄克斯瑞狄克斯瑞(Dijkstra)算法算法3/81例例假设

2、有分布在不同建筑物中的假设有分布在不同建筑物中的5台计算机台计算机C1, C2, C3, C4, C5。计算机连接的可能方案以及每种连接方式的。计算机连接的可能方案以及每种连接方式的成本（单位：元）如右图所示。成本（单位：元）如右图所示。C1 100 C2C3C4C5120370200成本最低的安装方案成本最低的安装方案C1 100 C2900C3C4C51204002004503704/81带权图带权图一个带权图规定为一个带权图规定为 一个有序三元组一个有序三元组(V，E，f )，或，或 一个有序三元组一个有序三元组(V，E，g)，或，或 一个有序四元组一个有序四元组(V，E，f，g)，其中

3、，其中，V是顶点集，是顶点集，E是边集，是边集， f是定义在是定义在V上的函数，上的函数，g是定义在是定义在E上的函数，上的函数，f和和g我们可以称为我们可以称为权函数权函数。对于每一个顶点或边对于每一个顶点或边x，f(x)和和g(x)可以是一个可以是一个数字数字、符符号号或是或是某种量某种量。5/81带权图中的最短通路带权图中的最短通路设设G=(V,E,W)是一个带权图，是一个带权图，其其W是边集是边集E 到到R+=x Rx0 的一个函数。的一个函数。通常称通常称 W(e)为边为边e的的长度长度，图图G中一个通路的长度定义为通路中所经过的边的中一个通路的长度定义为通路中所经过的边的长度之和。

4、长度之和。设设 v0,z V， 要求从要求从 v0到到z的最短通路的长。的最短通路的长。6/81Dijkstra算法的基本思想算法的基本思想先把先把V分成两个子集，分成两个子集，一个设为一个设为T, T=v Vv0到到v的最短通路的长已经求出的最短通路的长已经求出，另一个是另一个是P=VT。显然显然T，因为至少，因为至少v0 T。要不断地扩大要不断地扩大T，直到，直到z T。T PVTv0z7/81定理对于任意的对于任意的x P，设，设LT(x)表示从表示从v0仅经过仅经过T中的顶点中的顶点到到x的最短通路的长。若不存在这样的通路，置的最短通路的长。若不存在这样的通路，置LT(x)=。称称LT

5、(x)为为 x关于关于T的指标。令的指标。令 LT(t1)=minLT(x) x P则则 LT(t1)是从是从v0到到t1的最短通路的长。的最短通路的长。T PVTv0t1注：LT(x)即为教材上的l(t)x8/81Dijkstra算法算法设起点是设起点是v0，终点是，终点是z。具体程序如下：。具体程序如下：开始，设开始，设 T=v0，P=VT，对，对P中的每一个顶点中的每一个顶点x,令令 LT(x)=W(v0,x)。设设t1是是P中关于中关于T有最小指标的顶点有最小指标的顶点, 即即 LT(t1)=minLT(x) x P。若若t1=z，则终止。，则终止。 否则，设否则，设 T=T t1，P

6、=P t1。 对于对于P中的每一个顶点中的每一个顶点 ，计算它关于，计算它关于T的指标：的指标： LT(x)=minLT(x), LT(t1)+W(t1,x)。 把把T代为代为T,把把P代为代为P,把把LT(x)代为代为LT(x)， 重复步骤重复步骤(2)。9/81例例 求图求图9.9中从中从a到到z的最短通路的长的最短通路的长acebdz147123265T=a,b 3 8 6 T=a,b,c 8 4 a b c d e zT=a 1 4 LT(x)T=a,b,c,e 7 10 T=a,b,c,e,d 9 acebdz141232最短通路的长度为最短通路的长度为9，最短通路的路径为，最短通路

7、的路径为(a,b,c,e,d,z)。10/81例例(在各顶点上标记了最短通路及长度在各顶点上标记了最短通路及长度)4(a)1(a)1471232653(a,b)6(a,b)1(a)8(a,b)1471232653(a,b)4(a,b,c)1(a)8(a,b)1471232653(a,b)4(a,b,c)1(a)7(a,b,c,e)9(a,b,c,e,d)1471232653(a,b)4(a,b,c)1(a)7(a,b,c,e)10147123265acebd81例例 求顶点求顶点a至顶点至顶点f最短通路的长最短通路的长fbgedca856230137173291726

8、5793230813wLa b c d e f g 13 8 30 32 La b c d e f g 13 8 13 19 22 20 La b c d e f g 13 8 13 19 21 20La b c d e f g 13 8 13 19 21 20La b c d e f g 13 8 13 30 32La b c d e f g 13 8 13 30 22 20一些特殊的图一些特殊的图 9.4 欧拉图欧拉图9.5 哈密顿图哈密顿图9.6二部图二部图9.7平面图平面图 1213/779.4 欧拉图欧拉图(一一) 欧拉通路欧拉回路欧拉通路欧拉回路(二二) 欧拉图欧拉图(三三) 欧拉

9、定理欧拉定理(1836年年)(四四) 欧拉图的示例欧拉图的示例14/77哥德尼斯堡七桥问题哥德尼斯堡七桥问题十八世纪初，在当时德国哥德尼斯堡（现加里十八世纪初，在当时德国哥德尼斯堡（现加里林格勒）城的普雷格尔河上有林格勒）城的普雷格尔河上有7座桥。当地人经座桥。当地人经常在桥上散步，有人提出，从岛和河岸的某一常在桥上散步，有人提出，从岛和河岸的某一处出发是否能找到一条通过每一座桥一次且仅处出发是否能找到一条通过每一座桥一次且仅一次的通路。一次的通路。(a)(b)15/77欧拉(Leonhard Euler，17071783)瑞士数学家及自然科学家。在瑞士数学家及自然科学家。在1707年年4月月

10、15日出生於瑞士的巴塞尔，日出生於瑞士的巴塞尔，1783年年9月月18日於俄国的彼得堡去逝日於俄国的彼得堡去逝。 欧拉出生於牧师家庭，欧拉出生於牧师家庭，13岁时入岁时入读巴塞尔大学，读巴塞尔大学，15岁大学毕业，岁大学毕业，16岁获得硕士学位。岁获得硕士学位。在数学领域内，在数学领域内，18世纪可正确地称世纪可正确地称为欧拉世纪。欧拉是为欧拉世纪。欧拉是18世纪数学界世纪数学界的中心人物。他是继的中心人物。他是继牛顿牛顿（Newton）之后最重要的数学家之一。）之后最重要的数学家之一。在他的数学研究成果中，包含了数论、代数、无穷级数、在他的数学研究成果中，包含了数论、代数、无穷级数、函数概念

11、、初等函数、单复变函数、微积分学、微分方程、函数概念、初等函数、单复变函数、微积分学、微分方程、变分法、几何学、力学。变分法、几何学、力学。16/77欧拉通路、欧拉回路、欧拉图欧拉通路、欧拉回路、欧拉图定义定义 G=（V，E）是一个图，）是一个图， G中一条通路称为欧拉中一条通路称为欧拉通路通路，若此条通路经过了，若此条通路经过了图中图中每条边一次且仅一次每条边一次且仅一次。 若一条欧拉通路是一个若一条欧拉通路是一个回路回路，则称此回路为欧，则称此回路为欧拉回路。拉回路。 一个图若有欧拉一个图若有欧拉回路回路，则称这个图为，则称这个图为欧拉图欧拉图。 一个图若有欧拉一个图若有欧拉通路通路，而无

12、欧拉回路，则称这，而无欧拉回路，则称这个图为个图为半欧拉图半欧拉图。例例 图中图中, (1), (4)为欧拉图为欧拉图; (2), (5)为半欧拉图为半欧拉图; (3)，(6)既不既不 是欧拉图是欧拉图, 也不是半欧拉图也不是半欧拉图. 在在(3), (6)中各至少加几条边才能成为欧拉图中各至少加几条边才能成为欧拉图?1718/77几点说明：几点说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用.规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路.环不影响图的欧拉性环不影响图的欧拉性. 19欧拉图的判别法欧拉图的判

13、别法 定理定理 无向图无向图G为欧拉图当且仅当为欧拉图当且仅当G连通且连通且无奇度顶点无奇度顶点. 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G连通且连通且恰有两个奇恰有两个奇度顶点度顶点. 定理定理 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D连通且每个顶点的连通且每个顶点的入入度度都都等于出度等于出度. 有向图有向图D具有欧拉通路当且仅当具有欧拉通路当且仅当D连通且连通且恰有两个恰有两个奇度顶点奇度顶点, 其中一个入度比出度大其中一个入度比出度大1, 另一个出度比入另一个出度比入度大度大1, 其余顶点的入度等于出度其余顶点的入度等于出度.20实例实例例例1 哥尼斯堡七桥问题哥尼

14、斯堡七桥问题例例2 下面两个图都是欧拉图下面两个图都是欧拉图. 从从A点出发点出发, 如何一次成功地走出一条欧拉回路来？如何一次成功地走出一条欧拉回路来？ 弗罗莱弗罗莱 (Fleury)算法算法(21/77例例 判断以下有向图是否有欧拉回路、欧拉通路。判断以下有向图是否有欧拉回路、欧拉通路。 解：解：(1)无欧拉通路，无欧拉通路， (2)有欧拉通路，无欧拉回路，有欧拉通路，无欧拉回路， (3)有欧拉回路。有欧拉回路。 9.5 哈密顿图哈密顿图 哈密顿通路哈密顿通路哈密顿回路哈密顿回路哈密顿图哈密顿图半哈密顿图半哈密顿图 2223/77哈密頓周遊世界問題哈密頓周遊世界問題十九世纪中期威廉十九世纪

15、中期威廉哈密尔顿爵士描述了一个数学游哈密尔顿爵士描述了一个数学游戏：從正十二面體的一個頂點出發，沿著正十二面體戏：從正十二面體的一個頂點出發，沿著正十二面體的棱前進，要把二十個頂點無一遺漏地全部通過，而的棱前進，要把二十個頂點無一遺漏地全部通過，而且每個頂點恰好只通過一次，最後回到出發點。且每個頂點恰好只通過一次，最後回到出發點。24/77威廉威廉哈密尔顿爵士哈密尔顿爵士 Sin William Rowan Hamilton (1805 1865) 英国数学家、物理学家。英国数学家、物理学家。 1863年，美国科学院选定在都柏林年，美国科学院选定在都柏林出生的爱尔兰人出生的爱尔兰人Willia

16、m Rowan Hamilton为它的第一个外籍院士为它的第一个外籍院士，它们认为，它们认为Hamilton是当时最伟是当时最伟大的科学家。大的科学家。爱尔兰政府决定：爱尔兰政府决定：2005年是年是Hamilton Year-哈密顿年。哈密顿年。25/77哈密頓周遊世界問題哈密頓周遊世界問題把正十二面体的一面正五邊形把正十二面体的一面正五邊形ABCDE沿着棱剪开，并沿着棱剪开，并将该五邊形張開，並將它壓平在一個平面上将该五邊形張開，並將它壓平在一個平面上（如右下圖）。（如右下圖）。 ABCDEABCDE26/77哈密頓周遊世界問題哈密頓周遊世界問題可以畫出一個符合要求的路徑（如左下圖中的可以

17、畫出一個符合要求的路徑（如左下圖中的藍線藍線）。將這個路投影於原正十二面體之上（如右下圖），。將這個路投影於原正十二面體之上（如右下圖），那麼就解決了這個問題。那麼就解決了這個問題。 ABCDE27/77哈密尔顿通路、哈密尔顿圈哈密尔顿通路、哈密尔顿圈定义：定义： G=(V,E)是一个图是一个图u 若若G中一条中一条通路通路通过每一个通过每一个顶点顶点一次且一次，一次且一次，称这条通路为称这条通路为哈密尔顿通路哈密尔顿通路。u 若若G中一个中一个圈圈通过每一个通过每一个顶点顶点一次且仅一次，一次且仅一次，称这个圈为称这个圈为哈密尔顿圈哈密尔顿圈。u 若一个图存在哈密尔顿圈，就称为若一个图存在哈

18、密尔顿圈，就称为哈密尔顿图哈密尔顿图。u 具有哈密顿通路而无哈密顿回路的图为具有哈密顿通路而无哈密顿回路的图为半哈密半哈密顿图顿图。到目前为止判定一个图是否是哈密尔顿图的充要条件到目前为止判定一个图是否是哈密尔顿图的充要条件尚不知道，而且这个问题是图论中主要的未解决问题尚不知道，而且这个问题是图论中主要的未解决问题之一。之一。例例 图中图中, (1), (2)是哈密顿图是哈密顿图; (3) 是半哈密顿图是半哈密顿图.(4)既不是哈密顿图既不是哈密顿图, 也不是半哈密顿图。也不是半哈密顿图。2829/77旅行货郎问题旅行货郎问题 (TSP)如果现在有一个图如果现在有一个图G，而这图的每一条弧上都

19、算上一个，而这图的每一条弧上都算上一个数字，要怎样才能找到这图的哈密顿回路具有所有的数字，要怎样才能找到这图的哈密顿回路具有所有的弧上数字的和是最小值的性质，这个问题就是数学上弧上数字的和是最小值的性质，这个问题就是数学上大名鼎鼎的难题：大名鼎鼎的难题：“旅行货郎问题旅行货郎问题”。这问题在这问题在1932年由德国著名数学家年由德国著名数学家KMenger提出，是提出，是许多人废寝忘食研究的对象。许多人废寝忘食研究的对象。我们在日常生活中就会遇到这问题，比方说：你为了我们在日常生活中就会遇到这问题，比方说：你为了商业业务，需要乘飞机飞几个城市，你要怎样安排行商业业务，需要乘飞机飞几个城市，你要

20、怎样安排行程，使到你能走遍你要去的城市，最后又回来原出发程，使到你能走遍你要去的城市，最后又回来原出发地，而又能省钱？地，而又能省钱？30/77Travelling Salesman Problem (TSP)设设G=(V,E,W)是一个带权完全图，是一个带权完全图，|V|=n，W是边集是边集E 到到R+=x Rx0 的一个函数。对于的一个函数。对于V中任意的三个顶中任意的三个顶点点vi,vj,vk，有，有 W(vi,vj)+W(vj,vk) W(vi,vk)。要在要在G中求得一条最短长度的哈密尔顿圈。一个哈密中求得一条最短长度的哈密尔顿圈。一个哈密尔顿圈尔顿圈(e1,e2, ,en-1)的长度定义为的长度定义为 W(e