欧拉图与汉密尔顿.ppt

《欧拉图与汉密尔顿.ppt》由会员分享，可在线阅读，更多相关《欧拉图与汉密尔顿.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1图的矩阵表示图的矩阵表示n1.关关联矩矩阵M(D),M(G)n2.邻接矩接矩阵A(D),邻接矩接矩阵A(G)n3.用用A的的幂求不同求不同长度通路度通路(回路回路)总数数n4.可达矩可达矩阵P(D),连通矩通矩阵P(G)2无向图关联矩阵无向图关联矩阵n设G=是无向是无向图,V=v1,v2,vn,E=e1,e2,emn关关联矩矩阵(incidence matrix):M(G)=mijn m,(每每个个顶点确定一行点确定一行,每条每条边确定一列确定一列),mij=vi与与ej的关的关联次数次数 2,vi与与ej关关联，且，且ej是是环 mij=1,vi与与ej关关联，且，且ej不是不是环 0,v

2、i不与不与ej关关联3无向图关联矩阵无向图关联矩阵(例例)v1v2v4v3e1e2e3e4e6e54无向图关联矩阵无向图关联矩阵(性质性质)n每列和每列和为2:ni=1mij=2(ni=1 mj=1mij=2m)n每行和每行和为d(v):d(vi)=mj=1mij n孤立点孤立点:全全0行行n平行平行边:相同两列相同两列n环：对应列中只有一个列中只有一个2其余是其余是05有向图关联矩阵有向图关联矩阵n设D=是是无无环有向有向图,V=v1,v2,vn,E=e1,e2,emn关关联矩矩阵(incidence matrix):M(D)=mijn m,(每个每个顶点确定一行点确定一行,每条每条边确定一

3、列确定一列)n 1,vi是是ej的起点的起点 mij=0,vi与与ej不关不关联 -1,vi是是ej的的终点点6有向图关联矩阵有向图关联矩阵(例例)v1v2v4v3e1e2e3e5e4e67有向图关联矩阵有向图关联矩阵(性质性质)n每列和每列和为零零:ni=1mij=0 n每行每行绝对值和和为d(v):d(vi)=mj=1mij,其中其中1的个的个数数为d+(v),-1的个数的个数为d-(v)n握手定理握手定理:ni=1 mj=1mij=0n平行平行边:相同两列相同两列8无向图邻接矩阵无向图邻接矩阵n设G=是无向是无向简单图,V=v1,v2,vn n邻接矩接矩阵(adjacence matri

4、x):n A(G)=aijn n,aii=0,1,vi与与vj相相邻,i j aij=0,vi与与vj不相不相邻v1v2v4v39无向图邻接矩阵无向图邻接矩阵(性质性质)nA(G)对称称:aij=ajin每行每行(列列)和和为顶点度点度:ni=1aij=d(vj)n握手定理握手定理:ni=1 nj=1aij=ni=1d(vj)=2mv2v310邻接矩阵与通路数邻接矩阵与通路数n设A(D)=A=aijn n,nAr=Ar-1 A(r 2),Ar=aij(r)n n,n定理定理1:aij(r)=从从vi到到vj长度度为r的通路的通路总数数ni=1 nj=1aij(r)=长度度为r的通路的通路总数数

5、 ni=1aii(r)=长度度为r的回路的回路总数数.#整数乘和整数加11用邻接矩阵求通路数用邻接矩阵求通路数(例例)v1v2v4v312邻接矩阵与通路数邻接矩阵与通路数n设Ar=Ar-1 A,(r 2),Ar=aij(r)n n,n推推论1:aii(2)=d(vi).#n推推论2:G连通通距离距离d(vi,vj)=minr|aij(r)0，i j.#13连通矩阵连通矩阵n只考只考虑有无，不考有无，不考虑有多少条有多少条n设G=是无向是无向简单图,V=v1,v2,vn,n连通矩通矩阵:P(G)=pijn n,1,若若vi与与vj连通通 pij=0,若若vi与与vj不不连通通14连通矩阵连通矩阵

6、(性质性质)n主主对角角线元素都是元素都是1:vi V,vi与与vi连通通n连通通图:所有元素都是所有元素都是1 n伪对角角阵:对角角块是是连通分支的通分支的连通矩通矩阵n设Br=A+A2+Ar=bij(r)n n,则 i j,pij=1 bij(n-1)015连通矩阵连通矩阵(例例)v1v4v3v2v6v516有向图邻接矩阵有向图邻接矩阵n设D=是有向是有向图,V=v1,v2,vn n邻接矩接矩阵(adjacence matrix):A(D)=aijn n,aij=从从vi到到vj的的边数数v1v2v4v317有向图邻接矩阵有向图邻接矩阵(性质性质)n每行和每行和为出度出度:nj=1aij=

7、d+(vi)n每列和每列和为入度入度:ni=1aij=d-(vj)n握手定理握手定理:ni=1 nj=1aij=ni=1d-(vj)=mn环个数个数:ni=1aiiv1v2v4v318邻接矩阵与通路数邻接矩阵与通路数n设A(D)=A=aijn n,nAr=Ar-1 A(r 2),Ar=aij(r)n n,n定理定理2:aij(r)=从从vi到到vj长度度为r的通路的通路总数数 ni=1 nj=1aij(r)=长度度为r的通路的通路总数数 ni=1aii(r)=长度度为r的回路的回路总数数19用邻接矩阵求通路数用邻接矩阵求通路数(例例)v1v2v4v320可达矩阵可达矩阵n设D=是有向是有向图,

8、V=v1,v2,vn,n可达矩可达矩阵:P(D)=pijn n,1,从从vi可达可达vj pij=0,从从vi不可达不可达vj21可达矩阵可达矩阵(性质性质)n主主对角角线元素都是元素都是1:vi V,从从vi可达可达vin强连通通图:所有元素都是所有元素都是1 n伪对角角阵:对角角块是是强连通分支的可达矩通分支的可达矩阵n i j,pij=1 bij(n-1)022图的运算图的运算n定定义14.2714.27 设图G G1 1=V=,G,G2 2=V=,若若 V V1 1VV2 2=，则称则称G G1 1与与G G2 2 是是不交的不交的.若若 E E1 1EE2 2=，则称，则称 E E1

9、 1与与E E2 2是是不重的不重的.由定由定义知，不交的知，不交的图必然是必然是边不交的，但反之不交的，但反之不真。不真。23图的运算图的运算n定定义14.2814.28 设图G G1 1=V=,G,G2 2=V=为不含孤立点的不含孤立点的两个两个图（它（它们同同为无向无向图或同或同为有向有向图).).(1)(1)称以称以 V V1 1VV2 2为顶点集，以点集，以 E E1 1EE2 2 为边集的图为为边集的图为G G1 1与与 G G2 2 的并图的并图,记作记作 G G1 1GG2 2,即即G G1 1GG2 2=.24图的运算图的运算(2)(2)称以称以E E1 1-E-E2 2为边

10、集集,以以 E E1 1-E-E2 2中中边关关联的的顶点点组成成的集合的集合为顶点集的点集的图为 G G1 1与与 G G2 2的的差差图,记作作 G G1 1-G-G2.2.(3)(3)称以称以E E1 1EE2 2为边集集,以以 E E1 1EE2 2中中边关关联的的顶点点组成成的集合的集合为顶点集的点集的图为 G G1 1与与 G G2 2的的交交图,记作作 G G1 1GG2.2.(4)(4)称以称以E E1 1EE2 2为边集集,以以 E E1 1EE2 2中中边关关联的的顶点点组成成的集合的集合为顶点集的点集的图为 G G1 1与与 G G2 2的的交交图,记作作 G G1 1G

11、G2.2.25图的运算图的运算在定在定义14.2814.28中中应注意以下几点：注意以下几点：1.1.若若G G1 1=G=G2 2,则G G1 1GG2 2=G=G1 1GG2 2=G=G1 1(G(G2 2),),而而G G1 1-G-G2 2=G=G2 2-G-G1 1=,这就是在图的定义中给出空图的概念的原因这就是在图的定义中给出空图的概念的原因.2.2.当当G G1 1与与 G G2 2边不重不重时,G,G1 1GG2 2=,G G1 1-G-G2 2=G=G1 1,G,G1 1GG2 2=G G1 1GG2.2.3.3.两个两个图的的环和可以并、交、差和可以并、交、差给出出:G G

12、1 1GG2 2=(G=(G1 1GG2 2)-(G)-(G1 1GG2 2).26第十四章基本要求第十四章基本要求1.1.理解与理解与图的定的定义有关的有关的诸多概念，以及它多概念，以及它们之之间的相互关系的相互关系.2.2.深刻理解握手定理及其推论的内容，并能熟练地应用它们深刻理解握手定理及其推论的内容，并能熟练地应用它们.3.3.深刻理解深刻理解简单图、完全、完全图、正、正则图、子、子图、补图、二部、二部图等等概念及它概念及它们的性的性质和相互关系，并熟和相互关系，并熟练地地应用用这些性些性质和关和关系系.4.4.深刻理解通路与回路的定深刻理解通路与回路的定义及其分及其分类，掌握通路和回

13、路的不，掌握通路和回路的不同表示方法同表示方法.5.5.理解无向理解无向图的的连通性、通性、连通分支等概念通分支等概念.27第十四章基本要求第十四章基本要求6.6.深刻深刻理解无向理解无向图的点的点连通度、通度、边连通度等概念及其之通度等概念及其之间的的 关系，并能熟关系，并能熟练地求出地求出给定的定的较为简单的点的点连通度和通度和边连 通度通度.7.7.理解有向图连通性的概念及其分类理解有向图连通性的概念及其分类,掌握判断有向连通图掌握判断有向连通图 类型的方法类型的方法.8.8.掌握掌握图的矩的矩阵表示，熟表示，熟练掌握用有向掌握用有向图的的邻接矩接矩阵求及求及 各次各次幂求求图中通路与回

14、路数的方法中通路与回路数的方法.9.9.会求有向会求有向图的可达矩的可达矩阵.欧拉图与哈密顿图欧拉图与哈密顿图1 1、欧拉图、欧拉图2 2、哈密尔顿图、哈密尔顿图3 3、最短路问题与货郎担问题、最短路问题与货郎担问题.28 欧拉图欧拉图历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图其实，欧拉图是一笔画出的边不重复的回路其实，欧拉图是一笔画出的边不重复的回路.30 欧拉图的定义欧拉图的定义定定义义15.1 （1）欧拉通路）欧拉通路经过图经过图中每条中每条边边一次且一次且仅仅一次一次行遍所有行遍所有顶顶点的通路点的通路.（2）欧拉回路）欧拉回路经过图经过图中每条中每条边边一次

15、且一次且仅仅一次一次行遍所有行遍所有顶顶点的回路点的回路.（3）欧拉）欧拉图图具有欧拉回路的具有欧拉回路的图图.（4）半欧拉）半欧拉图图具有欧拉通路而无欧拉回路的具有欧拉通路而无欧拉回路的图图.31 欧拉图的几点说明欧拉图的几点说明规规定平凡定平凡图为图为欧拉欧拉图图.欧拉通路是生成的欧拉通路是生成的简单简单通路，欧拉回路是生成的通路，欧拉回路是生成的简单简单回路回路.环环不影响不影响图图的欧拉性的欧拉性.3233定理定理15.1 无向无向图图G是欧拉是欧拉图图当且当且仅仅当当G连连通且无通且无奇度数奇度数顶顶 证证 若若G为为平凡平凡图图无无问题问题.下下设设G为为n阶阶m条条边边的的无向无

16、向图图必要性必要性 设设C为为G中一条欧拉回路中一条欧拉回路.（1）G连连通通显显然然.（2）vi V(G)，vi在在C上每出上每出现现一次一次获获2度，所度，所以以vi为为偶度偶度顶顶点点.由由vi的任意性，的任意性，结论为结论为真真.无向欧拉无向欧拉图图的判的判别别法法34 无向欧拉无向欧拉图图的判的判别别法法充分性充分性.由于由于G为非平凡的连通图可知为非平凡的连通图可知,G中边数中边数m1.对对m作归纳法作归纳法.(1)m1时时,由由G的连通性及无奇度顶点可知的连通性及无奇度顶点可知,G只能是只能是 一个环一个环,因而因而G为欧拉图为欧拉图.(2)设设mk(k1)时结论成立时结论成立,

17、要证明要证明mk+1时时,结论也结论也 成立成立.G的连通性及无奇度顶点可知的连通性及无奇度顶点可知,(G)2.无论无论G是否为简单图是否为简单图,都可以用扩大路径法证明都可以用扩大路径法证明G中中 必含圈必含圈.35 设设C为为G中一个圈，删除中一个圈，删除C上的全部边，得上的全部边，得G的生成子的生成子图图G ,设设G 有有s个连通分支个连通分支G 1,G 2,G s,每个连通分支每个连通分支至多有至多有k条且无奇度顶点条且无奇度顶点,并且设并且设G i与与C的公共顶点为的公共顶点为v*ji,i1,2,s,由归纳假设可知由归纳假设可知,G 1,G 2,G s都是欧拉都是欧拉图，因而都存在欧

18、拉回路图，因而都存在欧拉回路C i，i1,2,s。最后将最后将C还还原（原（即将删除的边重新加上即将删除的边重新加上），），并从并从C上的某顶点上的某顶点vr开开始行遍，每遇到始行遍，每遇到v*ji，就行遍就行遍G i中的欧拉回路中的欧拉回路C i，i1,2,s，最后回到最后回到vr，得回路得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr，此回路经过此回路经过G中每条边一次且仅一次并行遍中每条边一次且仅一次并行遍G中所有顶点，因而中所有顶点，因而它是它是G中的欧拉回路中的欧拉回路.故故G为欧拉图。为欧拉图。PLAY3637 无向半欧拉无向半欧拉图图的判的判别别法法定理定理15.2

19、 无向无向图图G是半欧拉是半欧拉图图当且当且仅仅当当G连连通且恰有通且恰有两个奇度两个奇度顶顶点点.证证 必要性必要性。设设G是是m条条边边的的n阶阶无向无向图图，因，因为为G为为半欧拉半欧拉图图,因而因而G中存在欧拉通路（但不存在欧拉回路）中存在欧拉通路（但不存在欧拉回路）设设=vi0ej1vi1vim-1ejmvim为为G中一条欧拉通路，中一条欧拉通路，vi0 vim.vV(G)，若，若v不在不在的端点出的端点出现现，显显然然d(v)为为偶数，偶数，若若v在端点出在端点出现过现过,则则d(v)为为奇数奇数,因因为为只有两个端点且只有两个端点且不同不同,因而因而G中只有两个奇数中只有两个奇数

20、顶顶点点.另外另外,G的的连连通性是通性是显显然的然的.38 无向半欧拉无向半欧拉图图的判的判别别法法充分性充分性（利用定理（利用定理15.1）设设u,v为为G中的两个奇度中的两个奇度顶顶点，令点，令G=G(u,v)则则G 连连通且无奇度通且无奇度顶顶点，由定理点，由定理15.1知知G 为为欧拉欧拉图图，因而存在欧拉回路因而存在欧拉回路C，令令=C(u,v)，则则 为为G中欧拉通路中欧拉通路.39 有向欧拉有向欧拉图图的判的判别别法法 定理定理15.3 15.3 有向有向图图D D 是欧拉是欧拉图图当且当且仅仅当当D D 是是强强连连通的且每个通的且每个顶顶点的入度都等于出度点的入度都等于出度

21、.定理定理15.4 15.4 有向有向图图D D 是半欧拉是半欧拉图图当且当且仅仅当当D D 是是单单向向连连通的通的,且且D D 中恰有两个奇度中恰有两个奇度顶顶点点,其中一个其中一个的入度比出度大的入度比出度大1,1,另一个的出度比入度大另一个的出度比入度大1,1,而而其余其余顶顶点的入度都等于出度点的入度都等于出度.40 欧拉欧拉图图的判的判别别法法 定理定理15.5 15.5 G G是非平凡的欧拉是非平凡的欧拉图图当且当且仅仅当当GG是是连连通的通的且且为为若干个若干个边边不重的圈之并不重的圈之并.41例例15.1 设设G是非平凡的欧拉图，证明：是非平凡的欧拉图，证明：(1)(G)2.

22、(2)对于对于G中任意两个不同顶点中任意两个不同顶点u,v，都存在简单回都存在简单回路路C含含u和和v。证证(1)由定理由定理15.5可知可知,e E(G),存在圈存在圈C,e在在C中中,因而因而p(G-e)=p(G),故故e不是桥不是桥.由由e的的任意性任意性(G)2,即即G是是2 2边边-连通图连通图。(2)u,v V(G)，uv，由由G的的连通性可知，通性可知，u,v之之间 必存在路径必存在路径1,设G G-E(1),则在在G 中中u与与v还必必连通，通，否否则，u与与v必必处于于G 的不同的的不同的连通分支中，通分支中，这说明在明在1上存在上存在G中的中的桥，这与与(1)矛盾。矛盾。于

23、是在于是在G 中存在中存在u到到v的路径的路径2，显然然1与与2边不重，不重，这说明明u,v处于于1 2形成的形成的简单回路上。回路上。43求欧拉图中欧拉回路的算法求欧拉图中欧拉回路的算法Fleury算法算法，能不走桥就不走桥能不走桥就不走桥(1)任取任取v0 V(G)，令令P0v0。(2)设Piv0e1v1e2eivi已已经行遍，按下面方法来从行遍，按下面方法来从 E(G)-e1,e2,ei中中选取取ei+1：(a)ei+1与与vi相关相关联；(b)除非无除非无别的的边可供行遍，否可供行遍，否则ei+1不不应该为 GiG-e1,e2,ei中的中的桥。(3)当当(2)不能再不能再进行行时，算法

24、停止。，算法停止。说明明 可以可以证明，当算法停止明，当算法停止时所得所得简单回路回路Pmv0e1v1e2emvm(vmv0)为G中一条欧拉回路。中一条欧拉回路。Fleury算法示例算法示例例例15.2下图是给定的欧拉图下图是给定的欧拉图G。某人用某人用Fleury算法求算法求G中的中的欧拉回路时，走了简单回路欧拉回路时，走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之之后后(观看他的错误走法观看他的错误走法)，无法行遍了，试分析在哪步他犯，无法行遍了，试分析在哪步他犯了错误了错误?解答 此人行遍v8时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。当他走到v8时，G-e2,e3,e14,e10,e1,e8为下图所示。此时e9为该图中的桥，而e7,e11均不是桥，他不应该走e9，而应该走e7或e11，他没有走，所以犯了错误。注意，此人在行遍中，在v3遇到过桥e3，v1处遇到过桥e8，但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。47作业：作业：nP305 1,2,3n1、若D为有向欧拉图，则D一定为强连通图。其逆命题成立吗？