离散数学(第十五章)

第十五章欧拉图与哈密顿图主要(zhǔyào)内容欧拉图哈密顿图带权图与货郎担问题1共三十七页第十五章欧拉图与哈密顿图预备(yùbèi)知识无向图G=<V,E>d(v),d+(v),d

(v)奇度顶点与偶度顶点连通，通路，回路2共三十七页瑞士数学家，最多产的数学家≥1100书籍论文全集≥75卷13个孩子最后17年失明

ADBCQuestion:如何将左边(zuǒbian)图所示的七桥问题转换为点和边来描述?一个游人怎样才能不重复地一次走遍七座桥，最后又回到出发点呢？

LinktothevideoLeonhardEuler:1707~1783历史背景3共三十七页下面哪些(nǎxiē)图形可以一笔画，哪些(nǎxiē)图形不能一笔画？试一试：(1)(2)(3)(4)(5)(6)4共三十七页（2）（2）（2）（2）（3）（3）（4）（4）（2）（2）（3）（2）（3）（2）（3）（4）（3）（1）（1）（1）（3）（4）（2）（2）（2）偶点（1）（3）（2）（2）奇点5共三十七页●中途(zhōngtú)点特征：笔沿着(yánzhe)某条边进去后，必定沿另一条边出去，于是知道与中途点为端点的边必定是成对出现的，这样中途点必定是偶点。进去出来进去出来如果起点和终点重合，则与他们相连的边是偶数条，所以也是偶点起点和终点不重合，与他们相连的边奇数条，则是都是奇点“一笔画”图形特征：一个图形可以“一笔画”则奇点的个数是0个或2个6共三十七页欧拉图定义(dìngyì)定义15.1(1)欧拉通路——经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路——经过图中每条边一次且仅一次行遍所有顶点的回路(huílù).(3)欧拉图——具有欧拉回路的图.(4)半欧拉图——具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.7共三十七页上图中，(1),(4)为欧拉图，(2),(5)为半欧拉图，(3),(6)既不是欧拉图，也不是半欧拉图.在(3),(6)中各至少加几条边才能(cáinéng)成为欧拉图？欧拉图实例(shílì)8共三十七页无向(wúxiànɡ)欧拉图的判别法定理15.1无向图G是欧拉图当且仅当G连通且无奇度数顶点(dǐngdiǎn).证若G为平凡图无问题.下设G为n阶m条边的无向图.必要性设C为G中一条欧拉回路.(1)G连通显然.(2)

vi

V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点.由vi的任意性，结论为真.充分性对边数m做归纳法（第二数学归纳法）.(1)m=1时，G为一个环，则G为欧拉图.(2)设m

k（k

1）时结论为真，m=k+1时如下证明：9共三十七页PLAY从以上(yǐshàng)证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3.10共三十七页欧拉图的判别(pànbié)法定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个(liǎnɡɡè)奇度顶点.证必要性简单.充分性（利用定理15.1）设u,v为G中的两个奇度顶点，令G

=G

(u,v)则G

连通且无奇度顶点，由定理15.1知G

为欧拉图，因而存在欧拉回路C，令

=C

(u,v)则

为G中欧拉通路.11共三十七页下图是某展览厅的平面图，它由五个展室组成，任两展室之间都有门相通，整个展览厅还有一个进口和一个出口，问游人(yóurén)能否一次不重复地穿过所有的门，并且从入口进，从出口出？AFDCBE练习(liànxí)112共三十七页下图是一个公园的平面图.要使游客走遍每条路而不重复(chóngfù)，问出入口应设在哪里？ABCCDEFGHIJK练习(liànxí)213共三十七页有向欧拉图的判别(pànbié)法定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似(lèisì)于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5

G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.14共三十七页查阅有关(yǒuguān)欧拉图应用研究的文献书面总结:研究动机研究框架关键的发现结论作业(zuòyè)15共三十七页15.2哈密顿图历史背景：哈密顿周游世界问题(wèntí)与哈密顿图

(1)(2)16共三十七页17共三十七页哈密顿图与半哈密顿图定义15.2

(1)哈密顿通路——经过图中所有顶点一次仅一次的通路.(2)哈密顿回路——经过图中所有顶点一次仅一次的回路.(3)哈密顿图——具有哈密顿回路的图.(4)半哈密顿图——具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行(píngxíng)边不影响哈密顿性.哈密顿图的实质是能将图中的所有顶点排在同一个圈上18共三十七页实例(shílì)在上图中，(1),(2)是哈密顿图;(3)是半哈密顿图;(4)既不是(bùshi)哈密顿图，也不是(bùshi)半哈密顿图，为什么？19共三十七页无向(wúxiànɡ)哈密顿图的一个必要条件定理(dìnglǐ)15.6设无向图G=<V,E>是哈密顿图，对于任意V1

V且V1

，均有p(G

V1)

|V1|证设C为G中一条哈密顿回路(1)p(C

V1)

|V1|(2)p(G

V1)

p(C

V1)

|V1|（因为C

G）推论设无向图G=<V,E>是半哈密顿图，对于任意的V1

V且V1

均有

p(G

V1)

|V1|+1证令

uv为G中哈密顿通路，令G

=G

(u,v)，则G

为哈密顿图.于是

p(G

V1)=p(G

V1

(u,v))

|V1|+120共三十七页(1)若G是哈密顿图，则一定满足(mǎnzú)上式；(2)满足上式却不一定是哈密顿图；(3)不满足上式一定不是哈密顿图。21共三十七页定理(dìnglǐ)应用举例利用定理说明(shuōmíng)下图不是哈密顿图。22共三十七页解答(jiědá)取S={v1,v4}，则：|S|=2p(V-S)=3，不满足(mǎnzú)：p(V-S)≤|S|不是哈密顿图23共三十七页几点说明(shuōmíng)由定理15.6立刻可知，Kr,s当s

r+1时不是哈密顿图.易知Kr,r（r

2）时都是哈密顿图，Kr,r+1都是半哈密顿图.常利用定理15.6判断某些(mǒuxiē)图不是哈密顿图.例2设G为n阶无向连通简单图，若G中有割点或桥，则G不是哈密顿图.证设v为割点，则p(G

v)

2>|{v}|=1.K2有桥，它显然不是哈密顿图.除K2外，其他有桥的图（连通的）均有割点.其实，本例对非简单连通图也对.24共三十七页无向(wúxiànɡ)哈密顿图的一个充分条件定理15.7设G是n阶无向简单图，若对于任意(rènyì)不相邻的顶点vi,vj，均有

d(vi)+d(vj)

n

1(

)则G中存在哈密顿通路.推论设G为n(n

3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)

n（

）则G中存在哈密顿回路，从而G为哈密顿图.25共三十七页几点说明(shuōmíng)由定理15.7的推论(tuīlùn)可知，Kn（n

3）均为哈密顿图.(1)满足上式一定是哈密顿图；(2)是哈密顿图不一定满足上式；(3)不是哈密顿图一定不满足上式。完全图Kn(n

3)中任何两个顶点u,v，均有d(u)+d(v)=2(n

1)

n（n

3），所以Kn为哈密顿图.26共三十七页定理(dìnglǐ)应用举例任意(rènyì)两点的度之和为4n=6不满足d(vi)+d(vj)≥n但却是哈密顿图，也有哈密顿路径。是哈密顿图27共三十七页n（n

2）阶竞赛图中存在哈密顿通路(tōnglù)定理15.9若D为n（n

2）阶竞赛图，则D中具有哈密顿通路证明思路：注意，竞赛图的基图是无向完全图.对n（n

2）做归纳.只需观察下面两个图.无向(wúxiànɡ)哈密顿图的充分条件28共三十七页设G

G，称为G

的权，并记作W(G

)，即定义(dìngyì)15.3给定图G=<V,E>，(G为无向图或有向图)，设W:E

R

(R为实数集)，对G中任意边e=(vi,vj)(G为有向图时，e=<vi,vj>)，设W(e)=wij，称实数wij为边e上的权，并将wij标注在边e上，称G为带权图，此时常将带权图G记作<V,E,W>.15.3最短路(duǎnlù)问题与货郎担问题29共三十七页例：一位旅客(lǚkè)要从A城到B城他希望选择一条途中中转次数最少的路线；他希望选择一条途中所花时间最短的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v0

1006030101020

550这些(zhèxiē)问题均是带权图上的最短路径问题。边上的权表示一站边上的权代表距离边的权代表费用30共三十七页货郎担问题(wèntí)设G=<V,E,W>为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为

.求G中的一条最短的哈密顿回路，这就是货郎担问题的数学模型.完全带权图Kn（n

3）中不同的哈密顿回路数(1)Kn中有(n

1)!条不同的哈密顿回路（定义(dìngyì)意义下）(2)完全带权图中有(n

1)!条不同的哈密顿回路(3)用穷举法解货郎担问题算法的复杂度为(n

1)！，当n较大时，计算量惊人地大31共三十七页

解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可见(kějiàn)C3(见图中(2))是最短的，其权为9.例6求图中(1)所示带权图K4中最短哈密顿回路(huílù).

(1)(2)32共三十七页1.设G为n（n

2）阶无向欧拉图，证明(zhèngmíng)G中无桥(见例1思考题)方法二：反证法.利用欧拉图无奇度顶点及握手定理的推论.否则，设e=(u,v)为G中桥，则G

e产生两个(liǎnɡɡè)连通分支G1,G2，不妨设u在G1中，v在G2中.由于从G中删除e时，只改变u,v的度数(各减1)，因而G1与G2中均只含一个奇度顶点，这与握手定理推论矛盾.练习1方法一：直接证明法.命题(*)：设C为任意简单回路，e为C上任意一条边，则C

e连通.证设C为G中一条欧拉回路，任意的e

E(C)，可知C

e是G

e的子图，由()知C

e连通，所以e不为桥.33共三十七页2.证明(zhèngmíng)下图不是哈密顿图.(破坏必要条件)方法(fāngfǎ)一.利用定理15.6，取V1={a,c,e,h,j,l}，则p(G

V1)=7>|V1|=6练习2方法二.G为二部图，互补顶点子集V1={a,c,e,h,j,l},V2={b,d,f,g,i,k,m}，|V1|=6

7=|V2|.方法三.利用可能出现在哈密顿回路上的边至少有n(n为阶数)条——这也是哈密顿图的一个必要条件，记为（

）.此图中，n=13，m=21.由于h,l,j均为4度顶点，a,c,e为3度顶点，且它们关联边互不相同.而在哈密顿回路上，每个顶点准确地关联两条边，于是可能用的边至多有21

(3

2+3

1)=12.这达不到（

）的要求.34共三十七页3．某次国际会议8人参加，已知每