《离散数学》第七章-图论-第3-4节.ppt

除用图形表示图外，还可用矩阵表示图，它的优点除用图形表示图外，还可用矩阵表示图，它的优点：(1)将图的问题变为数学计算问题，从而可借助计算将图的问题变为数学计算问题，从而可借助计算机来研究图，进行相关的计算。机来研究图，进行相关的计算。(2)表示更清楚。表示更清楚。知识点：知识点：p1.邻接矩阵邻接矩阵n邻接矩阵求两点间不同长度的路的条数邻接矩阵求两点间不同长度的路的条数p2.可达性矩阵可达性矩阵p3.完全关联矩阵完全关联矩阵p由于矩阵的行和列有固定的次序，因此在用矩阵表由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合序，则默认为书写集合V时结点的顺序。时结点的顺序。7-3 图的矩阵表示图的矩阵表示1.预备知识预备知识2.预备知识预备知识3.一、图的邻接矩阵一、图的邻接矩阵或者或者i=jadjacent(邻接邻接)v以结点与结点之间的邻接关系确定的矩阵。以结点与结点之间的邻接关系确定的矩阵。v定义定义7-3.1设设简单图简单图G=，其中，其中V=v1,v2,vn，则，则n阶方阵阶方阵A(G)=(aij)n n，称为，称为图图G的的邻接矩阵邻接矩阵。其中第其中第i行行j列的元素。列的元素。4.图的邻接矩阵例图的邻接矩阵例例例7-3.1(1)写出下面无向图的邻接矩阵写出下面无向图的邻接矩阵0110010100110000000100010A(G)=v1v2v3v4v5v1v2v3v4v55.例例7-3.1(2)：写写出出下下面面有有向向图图的的邻邻接矩阵接矩阵 图的邻接矩阵例图的邻接矩阵例v v2 2v v1 1v v3 3v v4 40100001111011000A(G)=6.(1)邻接矩阵的主对角线元素邻接矩阵的主对角线元素aii=0。(2)主对角线以外的元素主对角线以外的元素aijaij=1(ij)，说明图，说明图G是是完全图完全图；aij=0(ij)，说明图，说明图G是是零图零图。(3)无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；而有向图的邻接矩阵不一定对称；而有向图的邻接矩阵不一定对称；因为在因为在无向图无向图中一条无向边应看成方向相反的两条中一条无向边应看成方向相反的两条有向边，因此有向边，因此无向图无向图的邻接矩阵关于的邻接矩阵关于主对角线对称。主对角线对称。图的邻接矩阵图的邻接矩阵说明：说明：A(G)=0100001111011000v v2 2v v1 1v v3 3v v4 40110010100110000000100010A(G)=7.(4)结点的度数结点的度数无向图：无向图：每行每行1的个数的个数=每列每列1的个数的个数=对应结点的度对应结点的度有向图有向图:每行每行1的个数的个数=对应结点的出度对应结点的出度每列每列1的个数的个数=对应结点的入度对应结点的入度图的邻接矩阵说明：图的邻接矩阵说明：v2v1v3v4A(G)=010000111101100001100101000000111000000108.图的邻接矩阵的应用图的邻接矩阵的应用(1)由邻接矩阵可计算出从由邻接矩阵可计算出从vi到到vj的长度为的长度为L的的路的数路的数目，也可计算从目，也可计算从vi出发的长度为出发的长度为L的回路数。的回路数。(2)计算结点计算结点vi与与vj之间的距离。之间的距离。(3)判判断断G是是否否是是连连通通图图，及及G中中任任意意两两个个结结点点是否是否连通。连通。9.图图G的邻接矩的邻接矩阵为阵为pA2中：中：G中从结点中从结点v2到结点到结点v3长度为长度为2路数目为路数目为0。pA3中：中：G中从结点中从结点v2到结点到结点v3长度为长度为3的路数目为的路数目为2。pA2中：中：G中长度为中长度为2的路的路(含含回路回路)总数为总数为8，其中，其中6条为条为回路。回路。pA3中：中：G中长度为中长度为3的路的路(含回路含回路)总数为总数为10，其中，其中0条为回路。条为回路。v4v4v1v1v3v3v2v2v5v5aij(2)=ai1a1j+ai2a2j+ai3a3j+ainanjaij(L+1)=ai1a1j(L)+ai2a2j(L)+ai3a3j(L)+ainanj(L)10.图的邻接矩阵的应用图的邻接矩阵的应用(1)由邻接矩阵可计算出从由邻接矩阵可计算出从vi到到vj的长度为的长度为L的的路的数目，可计算从路的数目，可计算从vi出发的长度为出发的长度为L的回的回路数。路数。定理定理7-3.1设设G是具有结点集是具有结点集v1，v2，vn和邻接矩阵和邻接矩阵A的图，则矩阵的图，则矩阵AL（l=1，2，）的第）的第i行第行第j列的元素列的元素aij(L)=m，表示图，表示图G中从结点中从结点vi到到vj长度为长度为L的路有的路有m条（即路条（即路的数目）。的数目）。aij(2)=ai1a1j+ai2a2j+ai3a3j+ainanjaij(L+1)=ai1a1j(L)+ai2a2j(L)+ai3a3j(L)+ainanj(L)11.定理定理7-3.1 设设G是具有结点集是具有结点集v1，v2，vn和邻接矩阵和邻接矩阵A的图，则矩阵的图，则矩阵AL（l=1，2，）的第）的第i行第行第j列的元列的元素素aij(L)=m，表示图，表示图G中从结点中从结点vi到到vj长度为长度为L的路有的路有m条（即路的数目）。条（即路的数目）。证明：证明：v（从（从vi到到vj的长度为的长度为l的路可看作从的路可看作从vi到到vk的长度为的长度为1的路，再联结的路，再联结vk到到vj的长度为的长度为l-1的路。）的路。）v用数学归纳法：用数学归纳法：v1）当）当l=2时，成立。时，成立。v2）设）设l=p时命题对时命题对l成立，即成立，即aij(p)表示表示图图G中有中有几条几条从结点从结点vi到到vj长度为长度为p的路的路（即路的数目）（即路的数目）12.3)证明证明lp1时定理成立。时定理成立。由由故故而而aik是结点是结点vi到到vk长度为长度为1的路的数目，的路的数目，是结点是结点vk到到vj长度为长度为p的路的数目，的路的数目，所以上式右边的每一项表示从所以上式右边的每一项表示从vi经过一条边到经过一条边到vk，再再由由vk经过一条长度为经过一条长度为p的路到的路到vj的总长度为的总长度为p+1的路的的路的数目，对所有数目，对所有k求和，求和，是所有从是所有从vi到到vj的长度的长度为为p+1的路的数目。所以对的路的数目。所以对l=p+1成立。成立。证毕。证毕。定理定理7-3.1 设设G是具有结点集是具有结点集v1，v2，vn和邻接矩阵和邻接矩阵A的图，则矩阵的图，则矩阵AL（l=1，2，）的第）的第i行第行第j列的元素列的元素aij(L)=m，表示图表示图G中从结点中从结点vi到到vj长度为长度为L的路有的路有m条（即路的数目）。条（即路的数目）。13.v4v4v1v1v3v3v2v2v5v5图的邻接矩阵求不同长度的路图的邻接矩阵求不同长度的路例例v例例7-3.2：求下图中图：求下图中图G的从结点的从结点v2到结点到结点v3长长度为度为2和和3的路数目及所有长度为的路数目及所有长度为2和和3的路数的路数目。目。分析分析利用利用定理定理7-3.1，求图中长度为，求图中长度为m的路数目，的路数目，只需要先写出图的只需要先写出图的邻接矩阵邻接矩阵，然后计算邻接矩，然后计算邻接矩阵的阵的m次方次方即可。即可。14.图图G的邻接矩的邻接矩阵为阵为pG中从结点中从结点v2到结点到结点v3长度长度为为2通路数目为通路数目为0，G中长中长度为度为2的路（含回路）总数的路（含回路）总数为为8，其中，其中6条为回路。条为回路。pG中从结点中从结点v2到结点到结点v3长度长度为为3的通路数目为的通路数目为2，G中中长度为长度为3的路（含回路）总的路（含回路）总数为数为10，其中，其中0条为回路。条为回路。v4v4v1v1v3v3v2v2v5v515.若若中至少有一个不为中至少有一个不为0，则可断定则可断定vi与与vj相连接，求相连接，求中不为中不为0的最小的的最小的L即为即为d。(2)计算结点计算结点vi与与vj之间的距离。之间的距离。图的邻接矩阵的图的邻接矩阵的应用应用如：如：d=1,d=2，d=1,d=v4v4v1v1v3v3v2v2v5v516.(3)判断判断G是否是连通图，及是否是连通图，及G中任意两个结点是否连通。中任意两个结点是否连通。计计算算B=A1+A2+An，bij表表示示从从结结点点vi到到vj有有长长度度分别为分别为1、2、3n的不同长度路的总数。的不同长度路的总数。连通图的判断连通图的判断p若若B的每一个元素都的每一个元素都非非0，则为连通图。，则为连通图。结点间的连通性结点间的连通性p若若bij为为0，那么结点，那么结点vi与与vj不相连接。不相连接。p若若bij不不为为0，vi与与vj有路相连接。有路相连接。图的邻接矩阵的应用图的邻接矩阵的应用17.在许多问题中需要判断在许多问题中需要判断有向图有向图的的一个结点一个结点vi到另一个结点到另一个结点vj是否存是否存在路的问题。在路的问题。v如果利用图如果利用图G的邻接矩阵的邻接矩阵A，则可计算则可计算A，A2，A3，An，当发现其中的当发现其中的某个某个Al的的1，就表明结点，就表明结点vi到到vj可达。可达。二、有向图的可达矩阵二、有向图的可达矩阵（1）可达矩阵的定义）可达矩阵的定义（2）可达矩阵的计算方法）可达矩阵的计算方法（3）可达矩阵的应用）可达矩阵的应用18.可可达达性性矩矩阵阵表表明明了了图图中中任任意意两两个个结结点点间间是是否否至至少少存存在在一一条条路以及在任何结点上是否存在回路。路以及在任何结点上是否存在回路。定定义义7-3.2设设简简单单有有向向图图G=（V，E），其其中中V=v1，v2，vn，n阶阶方方阵阵P=（pij）n n，称称为为图图G的的可可达达性矩阵，其中第性矩阵，其中第i行行j列的元素列的元素=从从vi到到vj没有路没有路至少有一条路至少有一条路和和0vv1pjiij1 1 1 0 01 1 1 0 01 1 1 0 00 0 0 1 10 0 0 1 1v1v1v2v2v3v3v4v4v5v5（一）有向图的可达性矩阵（一）有向图的可达性矩阵19.设设G是是n阶阶简简单单有有向向图图，由由可可达达性性矩矩阵阵的的定定义义知知，当当ij时，时，p如果如果vi到到vj有路，则有路，则pij=1；p如果如果vi到到vj无路，则无路，则pij=0；p又又由由定定理理7-2.1知知，如如果果vi到到vj有有路路，则则必必存存在在长长度度小小于等于于等于n1的路。的路。通通过过对对图图G的的邻邻接接矩矩阵阵A进进行行运运算算可可得得到到G的的可可达达性性矩矩阵阵P。其方法如下：。其方法如下：n1由由A计算计算A2，A3，An。n2计算计算B=A+A2+An。n3将将矩矩阵阵B中中非非零零元元素素改改为为1，所所得得到到的的矩矩阵阵即即为可达性矩阵为可达性矩阵P。（二）图的可达性矩阵计算（二）图的可达性矩阵计算方法（方法（1）20.由邻接矩阵由邻接矩阵A求可达性矩阵求可达性矩阵P的另一方法：的另一方法：p将将邻邻接接矩矩阵阵A看看作作是是布布尔尔矩矩阵阵，矩矩阵阵的的乘乘法法运运算算和和加法运算中，元素之间的加法与乘法采用加法运算中，元素之间的加法与乘法采用布尔运算布尔运算布尔乘：只有布尔乘：只有11=1布尔加：只有布尔加：只有00=0计算过程：计算过程：n1由由A，计算，计算A2，A3，An。n2计算计算P=AA2AnnP便是所要求的可达性矩阵。便是所要求的可达性矩阵。图的可达性矩阵计算方法图的可达性矩阵计算方法（2）无向图的可达性矩阵称为连通矩阵，也是对称的。无向图的可达性矩阵称为连通矩阵，也是对称的。p图的可达性矩阵计算方法图的可达性矩阵计算方法（3）Warshall算法算法21.A(4)=A(2)A(5)=A(3)解：解：v1v1v2v2v3v3v4v4v5v5例例7-3.3 求右图中图求右图中图G中的可达性矩中的可达性矩阵。阵。v分析：先计算图的邻接矩阵分析：先计算图的邻接矩阵A布尔乘法的的布尔乘法的的2、3、4、5次幂，然后做布尔加即可。次幂，然后做布尔加即可。P=AA(2)A(3)A(4)A(5)22.图的可达性矩阵的应用图的可达性矩阵的应用(1)利用可达性矩阵判断有向图的连通性。利用可达性矩阵判断有向图的连通性。强连通强连通单侧连通单侧连通弱连通弱连通(2)求强分图求强分图(3)利用可达性矩阵判断无向图的连通性。利用可达性矩阵判断无向图的连通性。无向图无向图G为为连通图连通图的充要条件是图的可达的充要条件是图的可达性矩阵所有元素均为性矩阵所有元素均为1。23.（2）利用可达性矩阵判断有向）利用可达性矩阵判断有向图的连通性图的连通性v有向图有向图G为为强连通强连通的充要条件是图的可达性矩的充要条件是图的可达性矩阵所有元素均为阵所有元素均为1。v有向图有向图G为为单侧连通单侧连通的充要条件是图的可达性的充要条件是图的可达性矩阵矩阵P及其转置矩阵及其转置矩阵PT所组成的矩阵所组成的矩阵P=PPT，在，在P中除对角线元素外所有元素均为中除对角线元素外所有元素均为1。原因：原因：v设设PT为为Q，即即qij=pji，v若若qijpij=1，则结点，则结点vi与与vj可达，或可达，或vj与与vi可达；可达；v若若qijpij=0，则结点，则结点vi与与vj不可达。不可达。v有向图有向图G为为弱连通弱连通的充要条件是忽略边的方向的充要条件是忽略边的方向得到矩阵得到矩阵B=AAT，求，求B的可达性矩阵的可达性矩阵PB，在，在PB中除对角线元素外所有元素均为中除对角线元素外所有元素均为1。24.利用可达性矩阵判断有向图利用可达性矩阵判断有向图的连通性的连通性强连通图强连通图v1v3v225.利用可达性矩阵判断有向图利用可达性矩阵判断有向图的连通性的连通性v1v3v2单侧连通单侧连通图图26.（3）利用可达性矩阵）利用可达性矩阵P，求强分图，求强分图v方法：方法：设设PT为为P的转置矩阵的转置矩阵,由由PPT求强分图求强分图v原因：原因：因为对因为对PT，PijT=Pjiv若从若从vi到到vj可达，则可达，则Pij=1，v若从若从vj到到vi可达，则可达，则Pji=1，即，即PijT=1，于是当且，于是当且仅当仅当Vi和和Vj相互可达时，相互可达时，PPT的第的第(i,j)项项PijPijT值为值为1。v步骤步骤如下：如下：(1)计算计算可达性矩阵可达性矩阵P；(2)计算计算P的转置矩阵的转置矩阵PT；(3)计算计算PPT；(4)PPT第第i行行元素为元素为1的的在第在第j1,j2,jk列，则结点列，则结点vi,vj1,vj2,vjk在同一个强连通分支中，即在同一个强连通分支中，即vi,vj1,vj2,vjk导出的子图是导出的子图是G的一个强连通分支。的一个强连通分支。27.例例v强分图为强分图为v1,v3,v2,v4,v5PT=0010011111000001111111111由可达性矩阵，求强分图例由可达性矩阵，求强分图例V1V2V3V4V528.可达矩阵的应用可达矩阵的应用v判断是否存在递归调用，判断是否存在递归调用，v设设P=P1,P2,Pn表示程序中的函数集合，表示程序中的函数集合，对应为结点，若一函数对应为结点，若一函数Pi调用调用Pj，则在有，则在有向图中用从向图中用从Pi到到Pj的有向边表示，的有向边表示，v设函数集合设函数集合P=P1,P2,P3,P4,P5v调用关系：调用关系：P1调用调用P2；P2调用调用P4；P3调用调用P1；P4调用调用P5；P5调用调用P2；29.可达矩阵的应用可达矩阵的应用vP2，P4，P5产生递归调产生递归调用用P1P2P3P4P530.v完全关联矩阵完全关联矩阵v表示结点和边的关系表示结点和边的关系无向图的完全关联矩阵无向图的完全关联矩阵有向图的完全关联矩阵有向图的完全关联矩阵四、图的完全关联矩阵四、图的完全关联矩阵（结点和（结点和边关系）边关系）31.定义定义7-3.3给定无向图给定无向图G=，V=v1,v2,vp，E=e1,e2,eq，则矩阵则矩阵M(G)=(mij)p q，其中其中称称M(G)为为G的完全关联矩阵。的完全关联矩阵。=vi不关联不关联ej关联关联01mejviij无向图的完全关联矩阵无向图的完全关联矩阵（结点（结点和边关系）和边关系）32.1 1 0 0 1 11 1 0 0 1 11 1 1 0 0 01 1 1 0 0 00 0 1 1 0 10 0 1 1 0 10 0 0 1 1 00 0 0 1 1 00 0 0 0 0 00 0 0 0 0 0v1v1V2V2V3V3V4V4v5v5M(G)=M(G)=e e1 1 e e2 2 e e3 3 e e4 4 e e5 5 e e6 6e e1 1e e2 2e e3 3e e5 5e e6 6e e4 4v v1 1v v2 2v v4 4v v3 3v v5 5图的完全关联矩阵例图的完全关联矩阵例33.(3)这个结果正是握手定理的内容，即各结点的度数之这个结果正是握手定理的内容，即各结点的度数之和等于边数的和等于边数的2倍。倍。(4)(4)一行中元素全为一行中元素全为0 0，其对应结点是孤立结点。，其对应结点是孤立结点。(5)(5)若两列相同，则相应的两边平行。若两列相同，则相应的两边平行。(2)每行元素的和每行元素的和即即是结点是结点vi的度数的度数deg(vi)(1)图中的一边关联两个点，图中的一边关联两个点，M(G)中每列中只有两个中每列中只有两个1。图的完全关联矩阵性质图的完全关联矩阵性质34.定义定义7-3.3给定给定简单有向图简单有向图G=，V=v1,v2,vp，E=e1,e2,eq，则矩阵则矩阵M(G)=(mij)p q，其中其中称称M(G)为为G的完全关联矩阵。的完全关联矩阵。=vi是是ej的终点的终点是是01mejviij的起点的起点-1vi与与ej不关联不关联有向图的完全关联矩阵有向图的完全关联矩阵35.v1v1V2V2V3V3V4V4v5v5M(G)=M(G)=e e1 1 e e2 2 e e3 3 e e4 4 e e5 5 e e6 6 e e7 71 0 0 0 1 1 11 0 0 0 1 1 1-1 1 0 0 0 0 0-1 1 0 0 0 0 00-1 1 0 0-1 00-1 1 0 0-1 00 0-1 1 0 0-10 0-1 1 0 0-10 0 0-1-1 0 00 0 0-1-1 0 0e e3 3e e1 1e e2 2e e5 5e e4 4e e6 6e e7 7v2v2v1v1v3v3v4v4v5v5有向图的完全关联矩阵例有向图的完全关联矩阵例36.（1）图中的一边关联两个点，）图中的一边关联两个点，M(G)中每列中只有一个中每列中只有一个1和一个和一个-1。（2）每行中）每行中1的个数和的个数和-1的个数分别为相应结点的出度、的个数分别为相应结点的出度、入度。入度。（3）结点）结点vi的度数：的度数：（4）一行中元素全为）一行中元素全为0，其对应结点是孤立结点。，其对应结点是孤立结点。q qk=1k=1|m mik ik|有向图的完全关联矩阵性质有向图的完全关联矩阵性质e e3 3e e1 1e e2 2e e5 5e e4 4e e6 6e e7 7v2v2v1v1v3v3v4v4v5v5v1v1V2V2V3V3V4V4v5v5M(G)=M(G)=e e1 1 e e2 2 e e3 3 e e4 4 e e5 5 e e6 6 e e7 71 0 0 0 1 1 11 0 0 0 1 1 1-1 1 0 0 0 0 0-1 1 0 0 0 0 00-1 1 0 0-1 00-1 1 0 0-1 00 0-1 1 0 0-10 0-1 1 0 0-10 0 0-1-1 0 00 0 0-1-1 0 037.小结小结v掌握邻接矩阵（有向图、无向图）的求法掌握邻接矩阵（有向图、无向图）的求法及性质应用及性质应用v理解利用邻接矩阵求两点间不同长度的路理解利用邻接矩阵求两点间不同长度的路的数目的数目v掌握有向图可达性矩阵的求法掌握有向图可达性矩阵的求法v了解完全关联矩阵的求法及性质了解完全关联矩阵的求法及性质38.7-4 欧拉图和汉密尔顿图欧拉图和汉密尔顿图v具有某种特殊路（回路）的图。具有某种特殊路（回路）的图。知识点：知识点：v欧拉路（回路）定义、七桥问题、一笔画欧拉路（回路）定义、七桥问题、一笔画问题问题v欧拉路（回路）判别定理欧拉路（回路）判别定理v有向图欧拉路（回路）有向图欧拉路（回路）v汉密尔顿路（回路）定义、周游世界问题汉密尔顿路（回路）定义、周游世界问题v汉密尔顿路（回路）必要条件汉密尔顿路（回路）必要条件v汉密尔顿路（回路）充分条件汉密尔顿路（回路）充分条件v图的闭包图的闭包39.欧拉图与汉密尔顿图总结欧拉图与汉密尔顿图总结v欧拉图与汉密尔顿图的判别方法欧拉图与汉密尔顿图的判别方法全体非空连通图全体非空连通图满足定理满足定理7-4.1的条件的条件不满足定理不满足定理7-4.1的条件的条件欧拉图欧拉图非欧拉图非欧拉图全体非空连通图全体非空连通图汉密尔顿图汉密尔顿图非汉密尔顿图非汉密尔顿图满足必要条件但满足必要条件但不满足任何充分不满足任何充分条件条件至少满足一个至少满足一个充分条件充分条件不满足某个必要条件不满足某个必要条件不能根据已知的充分条件或已知的必要条不能根据已知的充分条件或已知的必要条件判别是否是汉密尔顿图。件判别是否是汉密尔顿图。根据给定的图的特点采用特定的方法根据给定的图的特点采用特定的方法1.若能找到汉密尔顿回路，则它是汉密尔若能找到汉密尔顿回路，则它是汉密尔顿图。顿图。2.(反证法反证法)假设存在一个汉密尔顿回路，假设存在一个汉密尔顿回路，如果导致发生矛盾，则它不是汉密尔顿图。如果导致发生矛盾，则它不是汉密尔顿图。3.暂时无法判别。暂时无法判别。40.1.欧拉图欧拉图v（1）七桥问题，一笔画，欧拉）七桥问题，一笔画，欧拉(回回)路，欧路，欧拉图拉图v（2）判定欧拉图的充分必要条件）判定欧拉图的充分必要条件(求欧拉求欧拉回路的算法回路的算法)41.七桥问题七桥问题v1736年瑞士数学家列昂哈德年瑞士数学家列昂哈德欧拉欧拉(leonhardEuler)发表了图论的第一篇论文发表了图论的第一篇论文“哥尼斯堡七哥尼斯堡七桥问题桥问题”。v这个问题是这样的：哥尼斯堡这个问题是这样的：哥尼斯堡(Knigsberg)城城市有一条横贯全城的普雷格尔市有一条横贯全城的普雷格尔(PreGel)河，城河，城的各部分用七座桥连接，每逢假日，城中的的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，居民进行环城的逛游，这样就产生一个问题，能不能设计一次能不能设计一次“逛游逛游”，使得从某地出发，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。却又能回到原地。ABCD42.七桥问题的图表示七桥问题的图表示图中的结点图中的结点A，B，C，D表示表示四块地，而边表示七座桥。四块地，而边表示七座桥。哥尼斯堡七桥问题是在图中找哥尼斯堡七桥问题是在图中找寻经过寻经过每一条边且仅一次而回每一条边且仅一次而回到原地的路到原地的路。欧拉在欧拉在1736年的一篇论文中提年的一篇论文中提出了一条简单的准则，确定了出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。哥尼斯堡七桥问题是不能解的。gfabcdeBCADABCD43.一笔画一笔画v与七桥问题类似的还有一笔画的判别问题，要判与七桥问题类似的还有一笔画的判别问题，要判定一个图定一个图G是否可一笔画出，有两种情况：是否可一笔画出，有两种情况：一是从图一是从图G中某一结点出发，经过图中某一结点出发，经过图G的每一边的每一边一次且仅一次到达另一结点。一次且仅一次到达另一结点。另一种就是从另一种就是从G的某个结点出发，经过的某个结点出发，经过G的每一的每一边一次且仅一次回到该结点。边一次且仅一次回到该结点。v上述两种情况可以由欧拉路和欧拉回路的判定条上述两种情况可以由欧拉路和欧拉回路的判定条件给予解决。件给予解决。44.欧拉图欧拉图(Eulerian)v定义定义7-4.1v欧拉路欧拉路(Eulertrail)：无孤立结点无孤立结点的图（无向图或的图（无向图或有向图），若存在一条路，经过有向图），若存在一条路，经过图中所有边一次图中所有边一次且一次且一次，该条路称为，该条路称为欧拉路欧拉路。v欧拉回路欧拉回路(Eulertour/circuit)：若存在一条：若存在一条回路回路，经过经过图中所有边一次且一次图中所有边一次且一次，该回路称为，该回路称为欧拉回欧拉回路路。v欧拉图欧拉图(Eulerian)：有欧拉回路的图。有欧拉回路的图。v半欧拉图半欧拉图(semi-Eulerian)：有欧拉路的图。有欧拉路的图。几点说明：几点说明：v平凡图是欧拉图。平凡图是欧拉图。v环不影响图的欧拉性。环不影响图的欧拉性。v单向欧拉路（回路）：单向欧拉路（回路）：给定有向图，通过图中每给定有向图，通过图中每个结点一次且一次的单向路（回路），称作单向个结点一次且一次的单向路（回路），称作单向欧拉路（回路）。欧拉路（回路）。45.欧拉图的判定例欧拉图的判定例7-4.1e1e2e3(2)欧拉图欧拉图半欧拉图半欧拉图非（半）欧拉图非（半）欧拉图欧拉图欧拉图半欧拉图半欧拉图非（半）欧拉图非（半）欧拉图46.无向图的欧拉路及欧拉回路的判断无向图的欧拉路及欧拉回路的判断方法方法定理定理7-4.1无向图无向图G具有一条具有一条欧拉路欧拉路，当且仅当当且仅当G是是连通连通的，且的，且有零个或两个奇数度数有零个或两个奇数度数的结点。的结点。推论推论：无向图无向图G具有一条具有一条欧拉回路欧拉回路，当且仅当当且仅当G是是连通连通的，的，所有结点的度数均为偶数所有结点的度数均为偶数。有向图的欧拉路及欧拉回路的判断方有向图的欧拉路及欧拉回路的判断方法法定理定理7-4.2有向图有向图G具有一条具有一条单向欧拉回路单向欧拉回路，当且仅当当且仅当是是G是强连通是强连通的，且的，且每个结点的入度等于出度每个结点的入度等于出度。推论：一个有向图推论：一个有向图G具有具有单向欧拉路单向欧拉路，当且仅当当且仅当是是G是单是单侧连通的侧连通的，而且，而且除两个结点外，每个结点的入度等于出度，除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大但这两个结点中，一个结点的入度比出度大1（终点），（终点），另一个结点的入度比出度小另一个结点的入度比出度小1（起点）（起点）。这个定理的证明可以看作是定理这个定理的证明可以看作是定理7-4.1（无向图的欧拉（无向图的欧拉路）的推广，因为对于有向图的任意一个结点来说，如路）的推广，因为对于有向图的任意一个结点来说，如果果入度与出度相等，则该结点的总度数为偶数入度与出度相等，则该结点的总度数为偶数，若，若入度入度和出度之差为和出度之差为1时，其总度数为奇数时，其总度数为奇数。其原理就是每个结点都要能进去多少其原理就是每个结点都要能进去多少次就能出来多少次。次就能出来多少次。47.一笔画一笔画gfabcdeBCAD无向图无向图G存在欧拉路，当且仅当存在欧拉路，当且仅当()AG中所有结点的度数全为偶数中所有结点的度数全为偶数BG中至多有两个奇数度结点中至多有两个奇数度结点CG连通且所有结点的度数全为偶数连通且所有结点的度数全为偶数DG连通且至多有两个奇数度结点连通且至多有两个奇数度结点gfabcdeCADB思考题：思考题：无向连通图含无向连通图含G有有m个奇数度结点，问个奇数度结点，问（1）至少加入多少条边才能使图）至少加入多少条边才能使图G变为变为欧拉图？欧拉图？（2）至少加入多少条边才能使图）至少加入多少条边才能使图G变为变为半欧拉图？半欧拉图？48.例例7-4.3 欧拉路（回路）判定欧拉路（回路）判定欧拉路（回路）判定欧拉路（回路）判定半欧拉图半欧拉图欧拉图欧拉图非（半）欧拉图非（半）欧拉图欧拉图欧拉图半欧拉图半欧拉图非（半）欧拉图非（半）欧拉图49.定理定理7-4.1 无向图无向图G具有一条具有一条欧拉路欧拉路，当当且仅当且仅当G是是连通连通的，且的，且有零个或两个奇数有零个或两个奇数度数度数的结点。的结点。证明：证明：v设无向图设无向图G具有一条欧拉路，则具有一条欧拉路，则G是是连通连通的，且的，且有零个或有零个或两个奇数度数两个奇数度数的结点。的结点。v设设G有欧拉路有欧拉路L，即有点边序列，即有点边序列v0e1v1e2eiviei+1envn，其中结点可能重复出现，但边不重复。其中结点可能重复出现，但边不重复。v(1)证证G是是连通连通的的，欧拉路欧拉路L经过经过G的所有边，即经过所有结点，的所有边，即经过所有结点，G必连必连通。通。v(2)证证有零个或两个奇数度数。有零个或两个奇数度数。对任意一个不是端点的结点对任意一个不是端点的结点vi，每当沿欧拉路，每当沿欧拉路L经过经过vi一次，一次，都经过该结点关联的两条边（一进一出），即给结点的度都经过该结点关联的两条边（一进一出），即给结点的度数加数加2，vi可重复出现，但可重复出现，但deg(vi)必是偶数必是偶数。对于端点对于端点v0，vn，v若若v0 vn，则则deg(v0)必是奇数必是奇数，(起点仅有射出边，若在起点仅有射出边，若在路中路中也出现，度数必为也出现，度数必为偶数，偶数，1+偶数偶数=奇数奇数)则则deg(vn)必是奇数必是奇数，(终点仅有射入边，同上终点仅有射入边，同上)v若若v0=vn，则则deg(v0)必是偶数，必是偶数，2+偶数偶数=偶数偶数，(实质为欧拉实质为欧拉回路回路)50.证明：设无向图证明：设无向图G是是连通连通的，且的，且有零个或两个奇数度数有零个或两个奇数度数的的结点，则结点，则G具有一条欧拉路。具有一条欧拉路。方法：方法：构造法证明构造法证明-思想：思想：圈套圈圈套圈v(1)若有两个奇数度数结点，则从其中一个结点出发，开若有两个奇数度数结点，则从其中一个结点出发，开始构造一条边不同的路始构造一条边不同的路(即迹即迹)。方法：从方法：从v0出发，经关联边出发，经关联边e1进入进入v1，若，若deg(v1)为偶数，为偶数，则必可由则必可由v1再关联边再关联边e2进入进入v2，如此下去，每边仅取一次，如此下去，每边仅取一次，由于由于G连通，必可到达另一奇数度数结点停下来，得到一连通，必可到达另一奇数度数结点停下来，得到一条迹条迹L1。v(2)若若L1通过了通过了G的所有边，则的所有边，则L1为欧拉路。为欧拉路。v(3)若若G去掉去掉L1(已通已通过的边过的边)后得到的子图为后得到的子图为G(由剩余的由剩余的边组成边组成)，则，则G中每个结点的度数为偶数，因为原中每个结点的度数为偶数，因为原G为连为连通的，则通的，则L1与与G至少有一个结点至少有一个结点vi是重合的，在是重合的，在G中从中从vi出发，重复出发，重复(1)方法，得到另一迹方法，得到另一迹L2，vL1，L2合并在一起为新的合并在一起为新的L1，如果恰为如果恰为G，即得欧拉路，即得欧拉路，否则重复否则重复(3)可得到另一迹可得到另一迹L3，v以此类推直到得到一条经过以此类推直到得到一条经过G中所有边的欧拉路。中所有边的欧拉路。定理定理7-4.1 无向图无向图G具有一条具有一条欧拉路欧拉路，当当且仅当且仅当G是是连通连通的，且的，且有零个或两个奇有零个或两个奇数度数数度数的结点。的结点。51.逐步插入回路算法举例逐步插入回路算法举例走法一走法一走法二走法二52.找出穆罕默德短弯刀的欧拉回路。找出穆罕默德短弯刀的欧拉回路。例题例题jhk53.解解在在图图中中，仅仅有有两两个个度度数数为为奇奇数数的的结结点点b，c，因因而而存存在在从从b到到c的的欧欧拉拉路路，蚂蚂蚁蚁乙乙走走到到c只只要要走走一一条条欧欧拉拉路路，边边数数为为9条条。而而蚂蚂蚁蚁甲甲要要想想走走完完所所有有的的边边到到达达c，至至少少要要先先走走一一条条边边到到达达b，再再走走一一条条欧欧拉拉路路，因因而而它至少要走它至少要走10条边才能到达条边才能到达c，所以乙必胜。，所以乙必胜。欧拉图应用欧拉图应用1-(蚂蚁比赛问蚂蚁比赛问题题)v例例甲、乙两只蚂蚁分别位于右图甲、乙两只蚂蚁分别位于右图中的结点中的结点a，b处，并设图中的边处，并设图中的边长度是相等的。甲、乙进行比赛：长度是相等的。甲、乙进行比赛：从它们所在的结点出发，从它们所在的结点出发，走过图中走过图中的所有边最后到达结点的所有边最后到达结点c处处。如果。如果它们的速度相同，问谁先到达目的它们的速度相同，问谁先到达目的地？地？c cb(b(乙乙)a(a(甲甲)54.例例 设设G为为n(n2)阶无向欧拉图，证明阶无向欧拉图，证明G中无桥（割边）即中无桥（割边）即(G)2。方法一方法一：直接证法，从：直接证法，从桥桥与欧拉图定义考虑。与欧拉图定义考虑。v利用闭迹的一个性质（记为利用闭迹的一个性质（记为*）：删除任意闭迹）：删除任意闭迹上的一条边，仍连通。上的一条边，仍连通。v因为因为G为欧拉图，所以存在欧拉回路，设为欧拉图，所以存在欧拉回路，设C为其为其中的一条欧拉回路，则中的一条欧拉回路，则G中任何边均在中任何边均在C上。于上。于是，对于任意的是，对于任意的eE(G)，删除，删除e后的图记为后的图记为G=G-e=C-e。由。由*可知，可知，G仍连通，故由桥的仍连通，故由桥的定义可知，定义可知，e不是不是G中的桥。由中的桥。由e的任意性得证，的任意性得证，G中无桥。中无桥。即即(G)2。欧拉图应用欧拉图应用255.方法二：反证法：利用方法二：反证法：利用欧拉图的性质欧拉图的性质及及握手定理握手定理的推论的推论v假设假设G中存在桥中存在桥e=(u,v)，由于，由于G为欧拉图，所以为欧拉图，所以e的两个端点在的两个端点在G中的度数中的度数deg(u),deg(v)均为偶数均为偶数。v因为因为e为为G中桥，中桥，所以所以G=G-e，由两个连通分支由两个连通分支G1和和G2组成。组成。不妨设不妨设uV(G1)，vV(G2)。v由于删除了由于删除了e，因而在，因而在G1和和G2中，中，deg(u)与与deg(v)为奇度结点，为奇度结点，而对于任意的而对于任意的wV(G1)，wu，deg(w)为偶数，为偶数，即即G1中只有一个奇度结点中只有一个奇度结点u；v类似地，类似地，G2中也只有一个奇度结点中也只有一个奇度结点v。这与握手这与握手定理的推论矛盾。定理的推论矛盾。故故G中不可能含桥。中不可能含桥。即即(G)2。欧拉图应用欧拉图应用2（续）（续）例例 设设G为为n(n2)阶无向欧拉图，证明阶无向欧拉图，证明G中无桥（割边）即中无桥（割边）即(G)2。56.欧拉图应用欧拉图应用3v例例：设：设G是恰有是恰有2k(k1)个奇度结点的无向连通个奇度结点的无向连通图图,证明证明G中边能分为中边能分为k条边不重的条边不重的迹迹，P1,P2,Pk。证明证明：将：将G中的中的2k个奇度结点分为数目相同的两组为个奇度结点分为数目相同的两组为u1,u2,uk,v1,v2,vk，对图，对图G加边加边(u1,v1)，(u2,v2),(uk,vk),共共k条得图条得图G，则则G中每个结点的度数均为中每个结点的度数均为偶数偶数,故存在一条故存在一条欧拉回路欧拉回路,即有闭迹即有闭迹。若在若在G中删去边中删去边(u1,v1)，则得一条欧拉路，两端点为则得一条欧拉路，两端点为u1,v1，结点结点u2和和v2在此路中，再删去边在此路中，再删去边(u2,v2)则得两则得两条不同的迹，有四个端点分别为条不同的迹，有四个端点分别为u1,u2,v1,v2，而而u3,v3在其中一条迹中，再删除边