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

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,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,有向图关联矩阵(性质),每列和为零: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=1aij=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,连通矩阵,只考虑有无，不考虑有多少条设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到vj的边数,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,可达矩阵: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)称以 V1V2为顶点集，以 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=G2-G1=,这就是在图的定义中给出空图的概念的原因.2.当G1与 G2边不重时,G1G2=,G1-G2=G1,G1G2=G1G2.3.两个图的环和可以并、交、差给出:G1G2=(G1G2)-(G1G2).,26,第十四章基本要求,1.理解与图的定义有关的诸多概念，以及它们之间的相互关系.2.深刻理解握手定理及其推论的内容，并能熟练地应用它们.3.深刻理解简单图、完全图、正则图、子图、补图、二部图等概念及它们的性质和相互关系，并熟练地应用这些性质和关系.4.深刻理解通路与回路的定义及其分类，掌握通路和回路的不同表示方法.5.理解无向图的连通性、连通分支等概念.,27,第十四章基本要求,6.深刻理解无向图的点连通度、边连通度等概念及其之间的 关系，并能熟练地求出给定的较为简单的点连通度和边连 通度.7.理解有向图连通性的概念及其分类,掌握判断有向连通图 类型的方法.8.掌握图的矩阵表示，熟练掌握用有向图的邻接矩阵求及 各次幂求图中通路与回路数的方法.9.会求有向图的可达矩阵.,欧拉图与哈密顿图,1、欧拉图2、哈密尔顿图3、最短路问题与货郎担问题.,28,欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图其实，欧拉图是一笔画出的边不重复的回路.,30,欧拉图的定义,定义15.1（1）欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路.（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,无向欧拉图的判别法,充分性.由于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还原（即将删除的边重新加上），并从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)，若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 中恰有两个奇度顶点,其中一个的入度比出度大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 的不同的连通分支中，这说明在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)为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,31、若D为有向欧拉图，则D一定为强连通图。其逆命题成立吗？,