5欧拉图与汉密尔顿图.ppt

《5欧拉图与汉密尔顿图.ppt》由会员分享，可在线阅读，更多相关《5欧拉图与汉密尔顿图.ppt（47页珍藏版）》请在三一文库上搜索。

1、1,图的矩阵表示,1. 关联矩阵M(D), M(G) 2. 邻接矩阵A(D), 邻接矩阵A(G) 3. 用A的幂求不同长度通路(回路)总数 4. 可达矩阵P(D), 连通矩阵P(G),2,无向图关联矩阵,设G=是无向图,V=v1,v2,vn, E=e1,e2,em 关联矩阵(incidence matrix): M(G)=mijnm,(每个顶点确定一行,每条边确定一列), mij = vi与ej的关联次数 2, vi与ej关联，且ej是环 mij = 1, vi与ej关联，且ej不是环 0, vi不与ej关联,3,无向图关联矩阵(例),v1,v2,v4,v3,e1,e2,e3,e4,e6,e5

2、,4,无向图关联矩阵(性质),每列和为2: ni=1mij=2 ( ni=1mj=1mij=2m ) 每行和为d(v): d(vi)=mj=1mij 孤立点:全0行 平行边: 相同两列 环：对应列中只有一个2其余是0,5,有向图关联矩阵,设D=是无环有向图, V=v1,v2,vn, E=e1,e2,em 关联矩阵(incidence matrix): M(D)=mijnm , (每个顶点确定一行,每条边确定一列) 1, vi是ej的起点 mij = 0, vi与ej不关联 -1, vi是ej的终点,6,有向图关联矩阵(例),v1,v2,v4,v3,e1,e2,e3,e5,e4,e6,7,有向图

3、关联矩阵(性质),每列和为零: ni=1mij=0 每行绝对值和为d(v): d(vi)=mj=1mij, 其中1的个数为d+(v), -1的个数为d-(v) 握手定理: ni=1mj=1mij=0 平行边: 相同两列,8,无向图邻接矩阵,设G=是无向简单图,V=v1,v2,vn 邻接矩阵(adjacence matrix): A(G)=aijnn, aii=0, 1, vi与vj相邻,ij aij = 0, vi与vj不相邻,v1,v2,v4,v3,9,无向图邻接矩阵(性质),A(G)对称: aij= aji 每行(列)和为顶点度: ni=1aij=d(vj) 握手定理: ni=1nj=1a

4、ij=ni=1d(vj)=2m,v2,v3,10,邻接矩阵与通路数,设A(D)=A=aijnn, Ar=Ar-1A (r2), Ar=aij (r)nn, 定理1: aij (r) =从vi到vj长度为r的通路总数ni=1nj=1aij (r) =长度为r的通路总数 ni=1aii (r) =长度为r的回路总数. #,整数乘和整数加,11,用邻接矩阵求通路数(例),12,邻接矩阵与通路数,设Ar=Ar-1A,(r2), Ar=aij(r)nn, 推论1: aii (2) =d(vi). # 推论2: G连通距离d(vi,vj)=minr|aij(r)0，ij. #,13,连通矩阵,只考虑有无，

5、不考虑有多少条 设G=是无向简单图, V=v1,v2,vn, 连通矩阵: P(G)=pijnn, 1, 若vi与vj连通 pij = 0, 若vi与vj不连通,14,连通矩阵(性质),主对角线元素都是1: viV, vi与vi连通 连通图: 所有元素都是1 伪对角阵: 对角块是连通分支的连通矩阵 设Br=A+A2+Ar= bij(r)nn, 则ij, pij=1 bij(n-1) 0,15,连通矩阵(例),v1,v4,v3,v2,v6,v5,16,有向图邻接矩阵,设D=是有向图,V=v1,v2,vn 邻接矩阵(adjacence matrix): A(D)=aijnn, aij = 从vi到v

6、j的边数,v1,v2,v4,v3,17,有向图邻接矩阵(性质),每行和为出度: nj=1aij=d+(vi) 每列和为入度: ni=1aij=d-(vj) 握手定理: ni=1nj=1aij=ni=1d-(vj)=m 环个数: ni=1aii,18,邻接矩阵与通路数,设A(D)=A=aijnn, Ar=Ar-1A (r2), Ar=aij(r)nn, 定理2: aij(r)=从vi到vj长度为r的通路总数 ni=1nj=1aij(r)=长度为r的通路总数 ni=1aii (r) =长度为r的回路总数,19,用邻接矩阵求通路数(例),20,可达矩阵,设D=是有向图,V=v1,v2,vn, 可达矩

7、阵: P(D)=pijnn, 1, 从vi可达vj pij = 0, 从vi不可达vj,21,可达矩阵(性质),主对角线元素都是1: viV, 从vi可达vi 强连通图: 所有元素都是1 伪对角阵: 对角块是强连通分支的可达矩阵 ij, pij=1 bij (n-1) 0,22,图的运算,定义14.27 设图G1=, G2=,若 V1V2= ， 则称G1与G2 是不交的. 若 E1E2= ，则称 E1与E2 是不重的. 由定义知，不交的图必然是边不交的，但反之 不真。,23,图的运算,定义14.28 设图G1=, G2=为不含孤立点的 两个图（它们同为无向图或同为有向图). (1)称以 V1V

8、2为顶点集，以 E1E2 为边集的图为G1与 G2 的并图,记作 G1G2 ,即G1G2 =.,24,图的运算,(2)称以E1- E2为边集,以 E1- E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的差图,记作 G1- G2. (3)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的交图,记作 G1G2. (4)称以E1E2为边集,以 E1E2中边关联的顶点组成的集合为顶点集的图为 G1与 G2的交图,记作 G1G2.,25,图的运算,在定义14.28中应注意以下几点： 1.若G1= G2,则G1G2= G1G2= G1(G2),而G1-G2=

9、G2-G1 = ,这就是在图的定义中给出空图的概念的原因. 2.当G1与 G2边不重时,G1G2 = , G1-G2= G1,G1G2 = G1G2. 3.两个图的环和可以并、交、差给出: G1G2=(G1G2)-(G1G2) .,26,第十四章基本要求,1.理解与图的定义有关的诸多概念，以及它们之间的相互关系. 2.深刻理解握手定理及其推论的内容，并能熟练地应用它们. 3.深刻理解简单图、完全图、正则图、子图、补图、二部图等概念及它们的性质和相互关系，并熟练地应用这些性质和关系. 4.深刻理解通路与回路的定义及其分类，掌握通路和回路的不同表示方法. 5.理解无向图的连通性、连通分支等概念.,

10、27,第十四章基本要求,6.深刻理解无向图的点连通度、边连通度等概念及其之间的 关系，并能熟练地求出给定的较为简单的点连通度和边连 通度. 7. 理解有向图连通性的概念及其分类,掌握判断有向连通图 类型的方法. 8. 掌握图的矩阵表示，熟练掌握用有向图的邻接矩阵求及 各次幂求图中通路与回路数的方法. 9. 会求有向图的可达矩阵.,欧拉图与哈密顿图,1、欧拉图 2、哈密尔顿图 3、最短路问题与货郎担问题 .,28,欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图 其实，欧拉图是一笔画出的边不重复的回路. .,30,欧拉图的定义,定义15.1 （1）欧拉通路经过图中每条边一次且仅一次 行遍所有顶点的通路

11、. （2）欧拉回路经过图中每条边一次且仅一次 行遍所有顶点的回路. （3）欧拉图具有欧拉回路的图. （4）半欧拉图具有欧拉通路而无欧拉回路的图.,31,欧拉图的几点说明,规定平凡图为欧拉图. 欧拉通路是生成的简单通路，欧拉回路是生成的 简单回路. 环不影响图的欧拉性.,32,33,定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶 证 若G为平凡图无问题. 下设G为n阶m条边的无向图 必要性 设C为G中一条欧拉回路. （1）G连通显然. （2）viV(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi的任意性，结论为真.,无向欧拉图的判别法,34,无向欧拉图的判别法,充分性.

12、由于G为非平凡的连通图可知, G中边数m1. 对m作归纳法. (1)m1时,由G的连通性及无奇度顶点可知,G只能是 一个环,因而G为欧拉图. (2)设mk(k1)时结论成立,要证明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都是欧拉图，因而都存在欧拉回路C i，i1,2,s。最后将C

13、还原（即将删除的边重新加上），并从C上的某顶点vr开始行遍，每遇到v*ji，就行遍G i中的欧拉回路C i，i1,2,s，最后回到vr，得回路vrv*j1v*j1v*j2v*j2v*jsv*jsvr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路.故G为欧拉图。,PLAY,36,37,无向半欧拉图的判别法,定理15.2 无向图G是半欧拉图当且仅当G连通且恰有 两个奇度顶点. 证 必要性。设G是m条边的n阶无向图，因为G为 半欧拉图,因而G中存在欧拉通路（但不存在欧拉回路） 设=vi0ej1vi1vim-1ejmvim为G中一条欧拉通路，vi0 vim . vV(G)

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

15、大1,另一个的出度比入度大1,而 其余顶点的入度都等于出度.,40,欧拉图的判别法,定理15.5 G是非平凡的欧拉图当且仅当G是连通的 且为若干个边不重的圈之并.,41,例15.1 设G是非平凡的欧拉图，证明： (G)2. (2)对于G中任意两个不同顶点u,v，都存在简单回路C含u和v。 证 (1) 由定理15.5可知, eE(G),存在圈C, e在C中,因而p(G-e)=p(G),故e不是桥. 由e的 任意性(G)2,即G是2边-连通图。,(2)u,vV(G)，uv，由G的连通性可知，u,v之间 必存在路径1,设G G-E(1),则在G 中u与v还必连通， 否则，u与v必处于G 的不同的连通

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

17、) 为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,作业：,P305 1,2,3 1、 若D为有向欧拉图，则D一定为强连通图。其逆命题成立吗？,