离散数学第十五章的课件

离散数学第十五章的课件1第1页，共28页，2023年，2月20日，星期一15.1

欧拉图历史背景：哥尼斯堡七桥问题与欧拉图18世纪中叶在欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的普雷格尔河，河中有两个小岛，由7座桥相连接。当时人们热衷于一个难题：一个人怎么不重复走完七座桥，最后回到出发地点？这就是所谓的哥尼斯堡七桥问题。很长时间没有人能解决这个难题。2第2页，共28页，2023年，2月20日，星期一15.1

欧拉图历史背景：哥尼斯堡七桥问题与欧拉图1763年，瑞士数学家欧拉发表论文，他用四个点分别表示两个小岛和两岸，用连接两点的线段表示桥。于是，哥尼斯堡七桥问题就是要求在这个图中走一条欧拉回路（即经过图中每条边一次且仅一次行遍所有顶点的回路）。3第3页，共28页，2023年，2月20日，星期一15.1欧拉图定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.4第4页，共28页，2023年，2月20日，星期一上图中，(1),(4)为欧拉图，(2)为半欧拉图，(3),(5),(6)既不是欧拉图，也不是半欧拉图.欧拉图判断实例5第5页，共28页，2023年，2月20日，星期一要求掌握无向欧拉图的判定定理15.1

无向图G是欧拉图当且仅当G连通且无奇度顶点.在以上三个无向图（三个图都是连通图）中，只有图（1）中没有奇度顶点，因此图（1）是欧拉图。而图（2）和图（3）中都存在奇度顶点，因而它们都不是欧拉图。6第6页，共28页，2023年，2月20日，星期一半欧拉图的判别法定理15.2

无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.在以上两个无向图（两个图都是连通图）中，只有（2）中有两个奇度顶点，因此（2）是半欧拉图。而（3）中有4个奇度顶点，因而（3）不是半欧拉图。7第7页，共28页，2023年，2月20日，星期一有向欧拉图的判别法定理15.3

有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.定理15.4

有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.定理15.5

G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的初级回路（圈）之并.8第8页，共28页，2023年，2月20日，星期一求欧拉回路的算法——Fleury算法算法：(1)任取v0V(G)，令P0=v0，i=0.(2)设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+1加入

Pi得到Pi+1.(3)令i=i+1，返回(2).可以证明算法停止时所得简单回路

Pm

=v0e1v1e2…emvm(vm=v0)为G中的一条欧拉回路.能够一笔画出的图——欧拉图。要求掌握使用定理15.1，要会判断一个图是否为欧拉图。要求理解Fleury算法和应用它一笔画出欧拉图。9第9页，共28页，2023年，2月20日，星期一15.2

哈密顿图历史背景：哈密顿周游世界问题与哈密顿图

(1)(2)1859年，爱尔兰数学家哈密顿提出一个周游世界问题：有20个城市，城市之间的交通路线如（2）所示。问能否从某个城市出发沿交通路线经过每个城市一次并且仅一次，最后回到出发点？用现在的语言，就是问这个图中是否有哈密顿回路？哈密顿自己做了肯定的回答。哈密顿回路和哈密顿图即由此得名。10第10页，共28页，2023年，2月20日，星期一15.2

哈密顿图历史背景：哈密顿周游世界问题与哈密顿图

(1)(2)11第11页，共28页，2023年，2月20日，星期一15.2

哈密顿图定义15.2

(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.12第12页，共28页，2023年，2月20日，星期一上图中，(1),(2),(3)三个无向图都有哈密顿回路，都是哈密顿图。在有向图中，(4)有哈密顿回路，是哈密顿图。(5)只有哈密顿通路，没有哈密顿回路，是半哈密顿图，而(6)中既无哈密顿回路，也没有哈密顿通路，因而不是哈密顿图，也不是半哈密顿图.要求掌握哈密顿图的判定13第13页，共28页，2023年，2月20日，星期一无向哈密顿图的一个必要条件定理15.6

设无向图G=<V,E>是哈密顿图，对于任意V1V且V1，均有p(GV1)|V1|推论设无向图G=<V,E>是半哈密顿图，对于任意的V1V且V1均有p(GV1)|V1|+1定理15.6中的条件是哈密顿图的必要条件，但不是充分条件。常利用定理15.6判断某些图不是哈密顿图.14第14页，共28页，2023年，2月20日，星期一哈密顿图和半哈密顿图的几个充分条件定理15.7

设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有

d(vi)+d(vj)

n1(15.1)则G中存在哈密顿通路.推论设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有

d(vi)+d(vj)

n(15.2)则G中存在哈密顿回路，从而G为哈密顿图.定理15.7是半哈密顿图的充分条件，但不是必要条件.长度为n1（n>5）的初级通路构成的图不满足(15.1)的条件，但它显然是半哈密顿图.定理15.7的推论同样不是哈密顿图的必要条件，G为长为n（n>4）的初级回路，不满足(15.2)条件，但它当然是哈密顿图.由定理15.7的推论可知，Kn（n3）均为哈密顿图.15第15页，共28页，2023年，2月20日，星期一哈密顿图和半哈密顿图的几个充分条件定理15.8

设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图（(u,v)是加的新边）.定理15.9

n（n2）阶竞赛图中都有哈密顿通路若D为n（n2）阶竞赛图，则D中具有哈密顿通路。16第16页，共28页，2023年，2月20日，星期一判断某图是否为哈密顿图的方法判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.例3

下图(周游世界问题)是哈密顿图易知a

b

c

d

e

f

g

h

i

j

k

l

m

no

p

q

r

s

t

a为图中的一条哈密顿回路.注意，此图不满足定理15.7推论的条件.17第17页，共28页，2023年，2月20日，星期一2．满足定理15.7推论的条件（15.2）.例4

完全图Kn(n3)中任何两个顶点u,v，均有

d(u)+d(v)=2(n1)

n（n3），所以Kn为哈密顿图.3．破坏定理15.6的条件的图不是哈密顿图.判断某图是否为哈密顿图的方法18第18页，共28页，2023年，2月20日，星期一设GG，称为G的权，并记作W(G)，即定义15.3

给定图G=<V,E>，(G为无向图或有向图)，设W:ER

(R为实数集)，对G中的每一条边e=(vi,vj)(G为有向图时，e=<vi,vj>)，设W(e)=wij，称实数wij为边e上的权，并将wij标注在边e上，称G为带权图，记作G

=

<V,E,W>.当e=(vi,vj)(<vi,vj>)，把W(e)记作W(vi,vj).15.3最短路问题与货郎担问题设P是G中的一条通路，P中所有边的权之和称为P的长度，记作W(P)，即。类似可定义回路C的长度W(C)。19第19页，共28页，2023年，2月20日，星期一最短路问题

设带权图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不可达v

），d(u,v)=+∞。20第20页，共28页，2023年，2月20日，星期一最短路问题最短路问题：给定带权图G=<V,E,W>及顶点u和v，其中每一条边e的权W(e)为非负实数，求从u到v的最短路径。如果uvi1vi2…vikv是从u到v的最短路径，则对每一个l（1≤l≤k

），uvi1vi2…vil是从u到vil的最短路径。根据该性质，E.W.Dijkstra于1959年给出下述最短路径算法。最短路径算法给出从给定的起点s到每一点的最短路径。在计算过程中，赋予每一个顶点v一个标号l(v)=(l1(v),l2(v))。标号分为永久标号和临时标号：在v的永久标号l(v)中，l1(v)表示s到v的最短路径上v的前一个顶点，l2(v)表示从s到v的距离（即从s到v的最短路径的长度）。当l(v)是临时标号时，l1(v)表示当前从s经过永久标号的顶点到v的长度最短的路径上v的前一个顶点；l2(v)表示当前从s经过永久标号的顶点到v的长度最短的路径的长度。21第21页，共28页，2023年，2月20日，星期一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})，i=1，

l(s)是永久标号，其余标号均为临时标号，u=s（l(u):永久标号）2.for与u关联的临时标号的顶点v（l(v):临时标号）3. ifl2(u)+W(u,v)<l2(v)

l(v)=(u,l2(u)+W(u,v))4.计算l2(t)=min{l2(v)|v∈V且有临时标号}，把l(t)改为永久标号5.ifi<n

u=t,i=i+1,goto2

计算结束时，对每一个顶点u，d(s,u)=l2(u)，利用l1(v)从u开始回溯找到s到u的最短路径。22第22页，共28页，2023年，2月20日，星期一货郎担问题

设G=<V,E,W>为一个n阶完全带权图Kn，各边的权W(e)非负且可以为∞.求G中的一条最短的哈密顿回路——这就是货郎担问题的数学模型.

货郎担问题（旅行商问题）：有n个城市，给定城市之间道路的长度（长度可以为∞，对应这两个城市之间无交通线）。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市。问如何走才能使他走的路线最短？这个问题可以用图论方法描述如下：23第23页，共28页，2023年，2月20日，星期一

解C1=a

b

c

d

a,W(C1)=10

C2=a

b

d

c

a,W(C2)=11

C3=a

c

b

d

a,W(C3)=9可见C3是最短的，其权为9.图(2)是所求的最短路线图例6

求图中(1)所示4阶完全带权图K4中最短哈密顿回路及其最短线路图.

(1)(2)货郎担问题实例24第24页，共28页，2023年，2月20日，星期一重点主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题判断哪些图可一笔画出？用Dijkstra标号法求所示带权图中从顶点v1到顶点vi(i=2..7)的最短路径。

求所示带权图中所有哈密顿回路，指出哪条最短并画出其路线图。25第25页，共28页，2023年，2月20日，星期一第十五章习题课

主要内容欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图带权图、货郎担问题基本要求深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.26第26页，共28页，2023年，2月20日，星期一1.设G为n（n2）阶无向欧拉图，证明G中无桥(见例1思考题)方法二：反证法.利用欧拉图无奇度顶点及握手定理的推论.否则，设e=(u,v)为G中桥，则Ge产生两个连通分支G1,G2，不妨