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

《《离散数学》图论-第3-4节.ppt》由会员分享，可在线阅读，更多相关《《离散数学》图论-第3-4节.ppt（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、除用图形表示图外，还可用矩阵表示图，它的优点：(1)将图的问题变为数学计算问题，从而可借助计算机来研究图，进行相关的计算。 (2)表示更清楚。 知识点： 1.邻接矩阵 邻接矩阵求两点间不同长度的路的条数 2.可达性矩阵 3.完全关联矩阵 由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。,7-3 图的矩阵表示,预备知识,预备知识,一、图的邻接矩阵,以结点与结点之间的邻接关系确定的矩阵。 定义7-3.1 设简单图G=，其中V=v1,v2,vn，则n阶方阵A(G)=(aij)nn ，称为图G的邻接矩阵。 其中第i行j列的元

2、素。,图的邻接矩阵例,例7-3.1 (1) 写出下面无向图的邻接矩阵,例7-3.1(2)：写出下面有向图的邻接矩阵,图的邻接矩阵例,0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0,A(G)=,(1)邻接矩阵的主对角线元素aii=0。 (2)主对角线以外的元素aij aij=1 (ij)，说明图G是完全图； aij=0 (ij)，说明图G是零图。 (3)无向图的邻接矩阵是对称的； 而有向图的邻接矩阵不一定对称； 因为在无向图中一条无向边应看成方向相反的两条有向边，因此无向图的邻接矩阵关于主对角线对称。,图的邻接矩阵说明：,(4)结点的度数 无向图： 每行1的个数=每列1的个数=对

3、应结点的度 有向图: 每行1的个数=对应结点的出度 每列1的个数=对应结点的入度,图的邻接矩阵说明：,图的邻接矩阵的应用,(1)由邻接矩阵可计算出从vi到vj的长度为L的路的数 目，也可计算从vi出发的长度为L的回路数。 (2)计算结点vi与vj之间的距离。 (3)判断G是否是连通图，及G中任意两个结点是否 连通。,图G的邻接矩阵为,A2中：G中从结点v2到结点v3长度为2路数目为0。 A3中：G中从结点v2到结点v3长度为3的路数目为2。 A2中：G中长度为2的路(含回路)总数为8，其中6条为回路。 A3中： G中长度为3的路(含回路)总数为10，其中0条为回路。,aij(2)=ai1a1j

4、+ai2a2j+ai3a3j+ainanj aij(L+1)=ai1a1j(L)+ai2a2j(L)+ai3a3j(L)+ainanj(L),图的邻接矩阵的应用,(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+ainanj aij(L+1)=ai1a1j(L)+ai2a2j(L)+ai3a3j(L)+a

5、inanj(L),定理7-3.1 设G是具有结点集v1，v2，vn和邻接矩阵A的图，则矩阵AL（l=1，2，）的第i行第j列的元素aij(L)=m，表示图G中从结点vi到vj长度为L的路有m条（即路的数目）。,证明： （从vi到vj的长度为l的路可看作从vi到vk的长度为1的路，再联结vk到vj的长度为l-1的路。） 用数学归纳法： 1）当l=2时，成立。 2）设l=p时命题对l成立，即aij(p)表示图G中有几条从结点vi到vj长度为p的路（即路的数目）,3)证明lp1时定理成立。 由 故 而aik是结点vi到vk长度为1的路的数目， 是结点vk到vj长度为p的路的数目， 所以上式右边的每一

6、项表示从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条（即路的数目）。,图的邻接矩阵求不同长度的路例,例7-3.2：求下图中图G的从结点v2到结点v3长度为2和3的路数目及所有长度为2和3的路数目。,分析 利用定理7-3.1 ，求图中长度为m的路数目，只需要先写出图的邻接矩阵，然后计算邻接矩阵的

7、m次方即可。,图G的邻接矩阵为,G中从结点v2到结点v3长度为2通路数目为0，G中长度为2的路（含回路）总数为8，其中6条为回路。 G中从结点v2到结点v3长度为3的通路数目为2， G中长度为3的路（含回路）总数为10，其中0条为回路。,若 中至少有一个不为0，,则可断定vi与vj相连接，求 中不为0的最小的L即为d。,(2)计算结点vi与vj之间的距离。,图的邻接矩阵的应用,如： d=1,d=2， d=1,d= ,(3)判断G是否是连通图，及G中任意两个结点是否连通。,计算B= A1 +A2 + An ，bij表示从结点vi到vj有长度分别为1、2、3n 的不同长度路的总数。 连通图的判断

8、若B的每一个元素都非0，则为连通图。 结点间的连通性 若bij为0，那么结点vi与vj不相连接。 若bij不为0 ，vi与vj有路相连接。,图的邻接矩阵的应用,在许多问题中需要判断有向图的一个结点vi到另一个结点vj是否存在路的问题。,如果利用图G的邻接矩阵A，则可计算A，A2 ，A3，An，当发现其中的某个Al的 1，就表明结点vi到vj可达。,二、有向图的可达矩阵,（1）可达矩阵的定义 （2）可达矩阵的计算方法 （3）可达矩阵的应用,可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。 定义7-3.2 设简单有向图G=（V，E），其中V=v1，v2，vn ，n

9、阶方阵P=（pij）nn ，称为图G的可达性矩阵，其中第i行j列的元素,=,从vi到vj没有路,至少有一条路,和,0,v,v,1,p,j,i,ij,1 1 1 0 0,1 1 1 0 0,1 1 1 0 0,0 0 0 1 1,0 0 0 1 1,（一）有向图的可达性矩阵,设G是n阶简单有向图，由可达性矩阵的定义知，当ij时， 如果vi到vj有路，则pij=1； 如果vi到vj无路，则pij=0； 又由定理7-2.1知，如果vi到vj有路，则必存在长度小于等于n1的路。 通过对图G的邻接矩阵A进行运算可得到G的可达性矩阵P。其方法如下： 1由A计算A2，A3，An。 2计算B=A+A2+An。

10、 3将矩阵B中非零元素改为1，所得到的矩阵即为可达性矩阵P。,（二）图的可达性矩阵计算方法（1）,由邻接矩阵A求可达性矩阵P的另一方法： 将邻接矩阵A看作是布尔矩阵，矩阵的乘法运算和加法运算中，元素之间的加法与乘法采用布尔运算 布尔乘：只有11=1 布尔加：只有00=0 计算过程： 1由A，计算A2，A3，An。 2计算P=A A2 An P便是所要求的可达性矩阵。,图的可达性矩阵计算方法（2）,无向图的可达性矩阵称为连通矩阵，也是对称的。,图的可达性矩阵计算方法（3）Warshall算法,A(4)= A(2) A(5)=A(3),解：,例7-3.3 求右图中图G中的可达性矩阵。,分析：先计算

11、图的邻接矩阵A布尔乘法的的2、3、4、5次幂，然后做布尔加即可。,P=A A(2) A(3) A(4)A(5),图的可达性矩阵的应用,(1)利用可达性矩阵判断有向图的连通性。 强连通 单侧连通 弱连通 (2) 求强分图 (3)利用可达性矩阵判断无向图的连通性。 无向图G为连通图的充要条件是图的可达性矩阵所有元素均为1。,（2）利用可达性矩阵判断有向图的连通性,有向图G为强连通的充要条件是图的可达性矩阵所有元素均为1。 有向图G为单侧连通的充要条件是图的可达性矩阵P及其转置矩阵PT所组成的矩阵P=PPT，在P中除对角线元素外所有元素均为1。 原因： 设 PT为Q， 即qij=pji， 若qij

12、pij=1，则结点vi与vj可达，或vj与vi可达； 若qij pij=0，则结点vi与vj不可达。 有向图G为弱连通的充要条件是忽略边的方向得到矩阵B=AAT，求B的可达性矩阵PB，在PB中除对角线元素外所有元素均为1。,利用可达性矩阵判断有向图的连通性,强连通图,利用可达性矩阵判断有向图的连通性,单侧连通图,（3）利用可达性矩阵P，求强分图,方法：设PT为P的转置矩阵,由PPT求强分图 原因：因为对PT，PijT =Pji 若从vi到vj 可达，则Pij=1， 若从vj到vi可达，则Pji=1，即PijT=1，于是当且仅当Vi和Vj相互可达时，PPT的第(i,j)项PijPijT值为1。

13、步骤如下：,计算可达性矩阵P； 计算P的转置矩阵PT ； 计算PPT ； PPT第i行元素为1的在第j1,j2,jk列，则结点vi,vj1,vj2,vjk在同一个强连通分支中，即vi,vj1,vj2,vjk导出的子图是G的一个强连通分支。,例,强分图为 v1,v3,v2,v4,v5,由可达性矩阵，求强分图例,V1,V2,V3,V4,V5,可达矩阵的应用,判断是否存在递归调用， 设P=P1,P2, ,Pn表示程序中的函数集合，对应为结点，若一函数Pi调用Pj，则在有向图中用从Pi到Pj的有向边表示， 设函数集合P=P1,P2,P3,P4,P5 调用关系：P1调用P2；P2调用P4； P3调用P1

14、； P4调用P5； P5调用P2；,可达矩阵的应用,P2，P4，P5产生递归调用,P1,P2,P3,P4,P5,完全关联矩阵 表示结点和边的关系 无向图的完全关联矩阵 有向图的完全关联矩阵,四、图的完全关联矩阵（结点和边关系）,定义 7-3.3 给定无向图G=，V=v1,v2, vp，E=e1, e2, eq，则矩阵M(G)=(mij)pq，其中,称M(G)为G的完全关联矩阵。,无向图的完全关联矩阵（结点和边关系）,1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0,图的完全关联矩阵例,(3) 这个结果正是握手定理的内容，即各

15、结点的度数之和等于边数的2倍。 (4)一行中元素全为0，其对应结点是孤立结点。 (5)若两列相同，则相应的两边平行。,(2)每行元素的和 即,是结点vi的度数deg(vi),(1)图中的一边关联两个点，M(G)中每列中只有两个1。,图的完全关联矩阵性质,定义 7-3.3 给定简单有向图G=， V=v1,v2, vp，E=e1, e2, ,eq， 则矩阵M(G)= (mij)pq，其中,称M(G)为G的完全关联矩阵。,有向图的完全关联矩阵,v1 V2 V3 V4 v5,M(G)=,e1 e2 e3 e4 e5 e6 e7,1 0 0 0 1 1 1 -1 1 0 0 0 0 0 0 -1 1 0

16、 0 -1 0 0 0 -1 1 0 0 -1 0 0 0 -1 -1 0 0,e3,e1,e2,e5,e4,e6,e7,v2,v1,v3,v4,v5,有向图的完全关联矩阵例,（1）图中的一边关联两个点，M(G)中每列中只有一个1和一个-1。 （2）每行中1的个数和-1的个数分别为相应结点的出度、入度。 （3）结点vi的度数： （4）一行中元素全为0，其对应结点是孤立结点。,有向图的完全关联矩阵性质,小结,掌握邻接矩阵（有向图、无向图）的求法及性质应用 理解利用邻接矩阵求两点间不同长度的路的数目 掌握有向图可达性矩阵的求法 了解完全关联矩阵的求法及性质,7-4 欧拉图和汉密尔顿图,具有某种特殊

17、路（回路）的图。 知识点： 欧拉路（回路）定义、七桥问题、一笔画问题 欧拉路（回路）判别定理 有向图欧拉路（回路） 汉密尔顿路（回路）定义、周游世界问题 汉密尔顿路（回路）必要条件 汉密尔顿路（回路）充分条件 图的闭包,欧拉图与汉密尔顿图总结,欧拉图与汉密尔顿图的判别方法,全体非空连通图,满足定理7-4.1的条件,不满足定理7-4.1的条件,欧拉图,非欧拉图,全体非空连通图,汉密尔顿图,非汉密尔顿图,满足必要条件但不满足任何充分条件,至少满足一个充分条件,不满足某个必要条件,不能根据已知的充分条件或已知的必要条件判别是否是汉密尔顿图。 根据给定的图的特点采用特定的方法 1.若能找到汉密尔顿回路

18、，则它是汉密尔顿图。 2.(反证法)假设存在一个汉密尔顿回路，如果导致发生矛盾，则它不是汉密尔顿图。 3.暂时无法判别。,1.欧拉图,（1）七桥问题，一笔画，欧拉(回)路，欧拉图 （2）判定欧拉图的充分必要条件(求欧拉回路的算法),七桥问题,1736年瑞士数学家列昂哈德欧拉(leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。 这个问题是这样的：哥尼斯堡(Knigsberg)城市有一条横贯全城的普雷格尔(PreGel)河，城的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，能不能设计一次“逛游”，使得从某地出发对每座跨河桥走一次，而在遍历了七桥

19、之后却又能回到原地。,七桥问题的图表示,图中的结点A，B，C，D表示四块地，而边表示七座桥。 哥尼斯堡七桥问题是在图中找寻经过每一条边且仅一次而回到原地的路。 欧拉在1736年的一篇论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。,g,f,a,b,c,d,e,一笔画,与七桥问题类似的还有一笔画的判别问题，要判定一个图G是否可一笔画出，有两种情况： 一是从图G中某一结点出发，经过图G的每一边一次且仅一次到达另一结点。 另一种就是从G的某个结点出发，经过G的每一边一次且仅一次回到该结点。 上述两种情况可以由欧拉路和欧拉回路的判定条件给予解决。,欧拉图(Eulerian),定义7-4.

20、1 欧拉路(Euler trail)：无孤立结点的图（无向图或有向图），若存在一条路，经过图中所有边一次且一次，该条路称为欧拉路。 欧拉回路(Euler tour/circuit)：若存在一条回路，经过图中所有边一次且一次，该回路称为欧拉回路。 欧拉图(Eulerian)： 有欧拉回路的图。 半欧拉图(semi-Eulerian)： 有欧拉路的图。 几点说明： 平凡图是欧拉图。 环不影响图的欧拉性。 单向欧拉路（回路）：给定有向图，通过图中每个结点一次且一次的单向路（回路），称作单向欧拉路（回路）。,欧拉图的判定例7-4.1,e1,e2,(2),欧拉图,半欧拉图,非（半）欧拉图,欧拉图,半欧拉

21、图,非（半）欧拉图,无向图的欧拉路及欧拉回路的判断方法,定理7-4.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度数的结点。 推论：无向图G具有一条欧拉回路，当且仅当G是连通的，所有结点的度数均为偶数。,有向图的欧拉路及欧拉回路的判断方法,定理7-4.2 有向图G具有一条单向欧拉回路，当且仅当是G是强连通的，且每个结点的入度等于出度。 推论：一个有向图G具有单向欧拉路，当且仅当是G是单侧连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1（终点），另一个结点的入度比出度小1（起点）。 这个定理的证明可以看作是定理7-4.1（无向图的欧拉

22、路）的推广，因为对于有向图的任意一个结点来说，如果入度与出度相等，则该结点的总度数为偶数，若入度和出度之差为1时，其总度数为奇数。,其原理就是每个结点都要能进去多少次就能出来多少次。,一笔画,g,f,a,b,c,d,e,无向图G存在欧拉路，当且仅当( ) AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点 CG连通且所有结点的度数全为偶数 DG连通且至多有两个奇数度结点,g,f,a,b,c,d,e,思考题： 无向连通图含G有m个奇数度结点，问 （1）至少加入多少条边才能使图G变为欧拉图？ （2）至少加入多少条边才能使图G变为半欧拉图？,例7-4.3 欧拉路（回路）判定,欧拉路（回路）判定

23、,半欧拉图,欧拉图,非（半）欧拉图,欧拉图,半欧拉图,非（半）欧拉图,定理7-4.1 无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度数的结点。,证明： 设无向图G具有一条欧拉路，则G是连通的，且有零个或两个奇数度数的结点。 设G有欧拉路L，即有点边序列v0e1v1e2eiviei+1 envn，其中结点可能重复出现，但边不重复。 (1)证G是连通的， 欧拉路L经过G的所有边，即经过所有结点， G必连通。 (2)证有零个或两个奇数度数。 对任意一个不是端点的结点vi ，每当沿欧拉路L经过vi一次，都经过该结点关联的两条边（一进一出），即给结点的度数加2，vi可重复出现，但deg

24、(vi)必是偶数。 对于端点v0，vn， 若v0vn， 则deg(v0)必是奇数，(起点仅有射出边，若在路中也出现，度数必为偶数，1+偶数=奇数) 则deg(vn)必是奇数，(终点仅有射入边，同上) 若v0=vn，则deg(v0)必是偶数，2+偶数=偶数 ，(实质为欧拉回路),证明：设无向图G是连通的，且有零个或两个奇数度数的结点，则G具有一条欧拉路。 方法：构造法证明-思想：圈套圈 (1)若有两个奇数度数结点，则从其中一个结点出发，开始构造一条边不同的路(即迹)。 方法：从v0出发，经关联边e1进入v1，若deg(v1)为偶数，则必可由v1再关联边e2进入v2，如此下去，每边仅取一次，由于G

25、连通，必可到达另一奇数度数结点停下来，得到一条迹L1。 (2)若L1通过了G的所有边，则L1为欧拉路。 (3)若G去掉L1 (已通过的边)后得到的子图为G (由剩余的边组成) ，则G中每个结点的度数为偶数，因为原G为连通的，则L1与G至少有一个结点vi是重合的，在G中从vi出发，重复(1)方法，得到另一迹L2， L1，L2合并在一起为新的L1，如果恰为G，即得欧拉路，否则重复(3)可得到另一迹L3， 以此类推直到得到一条经过G中所有边的欧拉路。,定理7-4.1 无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度数的结点。,逐步插入回路算法举例,走法一,走法二,找出穆罕默德短弯刀的

26、欧拉回路。,例题,j,h,k,解 在图中，仅有两个度数为奇数的结点b，c，因而存在从b到c的欧拉路，蚂蚁乙走到c只要走一条欧拉路，边数为9条。而蚂蚁甲要想走完所有的边到达c，至少要先走一条边到达b，再走一条欧拉路，因而它至少要走10条边才能到达c，所以乙必胜。,欧拉图应用1-(蚂蚁比赛问题),例 甲、乙两只蚂蚁分别位于右图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？,例 设G为n(n2)阶无向欧拉图，证明G中无桥（割边）即 (G)2。,方法一 ：直接证法，从桥与欧拉图定义考虑。 利用闭

27、迹的一个性质（记为*）：删除任意闭迹上的一条边，仍连通。 因为G为欧拉图，所以存在欧拉回路，设C为其中的一条欧拉回路，则G中任何边均在C上。于是，对于任意的eE(G)，删除e后的图记为G=G-e=C-e。由*可知，G仍连通，故由桥的定义可知，e不是G中的桥。由e的任意性得证，G中无桥。 即(G)2。,欧拉图应用2,方法二：反证法：利用欧拉图的性质及握手定理的推论 假设G中存在桥e=(u,v)，由于G为欧拉图，所以e的两个端点在G中的度数deg (u),deg(v)均为偶数。 因为e为G中桥， 所以G=G-e， 由两个连通分支G1和G2组成。 不妨设 uV(G1)，vV(G2)。 由于删除了e，

28、因而在G1和G2中，deg(u)与deg(v)为奇度结点， 而对于任意的wV(G1)，wu，deg(w)为偶数，即G1中只有一个奇度结点u； 类似地， G2中也只有一个奇度结点v。这与握手定理的推论矛盾。 故G中不可能含桥。 即(G)2。,欧拉图应用2（续）例 设G为n(n2)阶无向欧拉图，证明G中无桥（割边）即 (G)2。,欧拉图应用3,例：设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

29、，则G中每个结点的度数均为偶数,故存在一条欧拉回路,即有闭迹。 若在G中删去边(u1,v1)，则得一条欧拉路，两端点为u1,v1，结点u2和v2在此路中，再删去边(u2,v2)则得两条不同的迹，有四个端点分别为u1,u2,v1,v2，而u3,v3在其中一条迹中，再删除边(u3，v3)则得3条不同的迹，u4,v4在其一条中，依次继续，直到删去全部加边可得到k条不同的迹。,欧拉图主要内容,1. 欧拉路、欧拉回路、欧拉图、半欧拉图的定义。 2. 判别定理（有向与无向）。 3. 求欧拉图中欧拉回路的算法。欧拉图是若干个边不重的圈之并。,2. 汉密尔顿回路,1859年威廉汉密尔顿爵士在给他的朋友的一封信

30、中， 问题1：在一个十二面体中能否找到一条回路，使它含有这个图的所有结点？ 问题2：把每个结点看成一个城市，联结两个结点的边看成是交通线，能否找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。,周游世界,Sir William Rowan Hamilton, 1859, Icosian game：,汉密尔顿图定义,定义7-4.3 给定图G，若存在一条路经过图中的每一个结点恰好一次，这条路称作汉密尔顿路。 若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作汉密尔顿回路。 具有汉密尔顿回路的图称为汉密尔顿图。 具有汉密尔顿路的图称为半汉密尔顿图

31、。 几点说明： 1.平凡图是汉密尔顿图. 2.环与平行边不影响图的汉密尔顿性.,例,(a),(c),(b),a,c,(d),既存在汉密尔顿通路，又存在汉密尔顿回路，即为汉密尔顿图。,既不存在汉密尔顿通路，也不存在汉密尔顿回路。,既存在汉密尔顿通路，又存在汉密尔顿回路，即为汉密尔顿图。,存在汉密尔顿通路，但不存在汉密尔顿回路。,例,证明Kn(n3)是汉密尔顿图。 证明：例用构造法来获得一个汉密尔顿回路。 在Kn中，从任意一个结点v1开始前进，由于和其它的所有结点都有边相连，则可以沿着某条边到达另一个结点，设为v2 ， v2也与其它的所有结点有边相连，若除v1和v2外还有结点没遍历到的话，可以经过

32、某个边到达一个新的结点v3。依次类推，由于每个结点都与其他任何结点相连接，只要有结点没遍历到的话，必然能找到新的边到达该结点，最终可以遍历所有结点后回到v2，得到汉密尔顿回路。,欧拉图与汉密尔顿图的关系,欧拉图不一定是汉密尔顿图： 汉密尔顿图也不一定是欧拉图： 有的图既是欧拉图也是汉密尔顿图 有的图既不是欧拉图也不是汉密尔顿图： Petersen图,汉密尔顿图的相关定理,无向汉密尔顿图的充分条件 满足P，则汉密尔顿图。 用于汉密尔顿图的判定及计算。 但是不满足P，也可能是汉密尔顿图。 无向汉密尔顿图的必要条件 汉密尔顿图则Q。 用于非汉密尔顿图的判定。 即非Q则非汉密尔顿图。,无向半汉密尔顿图

33、的充分条件,定理7-4.4： 设G是n阶无向简单图，若对G中任意结点u与v有 deg(u)+deg(v) n-1 则G是半汉密尔顿图。（图中存在汉密尔顿路） 定理7-4.5 ： 设G是n(3)阶无向简单图，若对G中任意结点u与v有 deg(u)+deg(v) n 则G是汉密尔顿图。,无向半汉密尔顿图的充分条件,定理7-4.4： 设G是n阶无向简单图，若对G中任意结点u与v有 deg(u)+deg(v) n-1 则G是半汉密尔顿图。（图中存在汉密尔顿路） 证明思想： （一）G连通 （二）构造汉密尔顿路 (1) 由极大路径得圈（路径即为通路） (2) 由圈得更长路径 路径-极大路径-圈-更长路径

34、-更长极大路径-更长圈-更长路径 -汉密尔顿路。 只要在G中构作出一条长为n1的汉密尔顿路即可得证。,定理7-4.4： 设G是n阶无向简单图,若对G中任意结点u与v有deg(u)+deg(v) n-1。则G是半汉密尔顿图。,证明： （一） G连通： 反证法：若G不是连通图，则G至少有两个连通分支，设为G1,G2，其阶数为分别为n1,n2，设v1V(G1)，v2V(G2)，因为G是简单图，所以 degG1(v1) n1-1 degG2(v2) n2-1 因此，degG(v1)+degG(v2)=degG1(v1)+degG2(v2) n1-1+n2-1n-2n-1 与已知条件（deg(u)+de

35、g(v) n-1）矛盾。 所以G连通。,无向半汉密尔顿图的充分条件,无向半汉密尔顿图的充分条件,（二）构造汉密尔顿路 证明汉密尔顿回路存在的过程其实就是构造这条回路的过程，分成以下几个步骤：（1）构造极大路径 任意找两个相邻的结点 S 和 T，在它们基础上扩展出一条尽量长的没有重复结点的路。也就是说，如果 S 与结点 v 相邻，而且 v 不在路 S T 上，则可以把该路变成 v S T，然后 v 成为新的 S。从 S 和 T 分别向两头扩展，直到无法扩为止，即所有与 S 或 T 相邻的结点都在路 S T 上。令P为G中任意一条长为p-1(pn)的通路，设其结点序列为v1,v2,vp。,（2）构

36、造圈 由极大路径得圈： 设极大路径 =v1vp, pn-1， 反复应用下面方法来扩充这一通路，直到P长度为n-1（即包括所有结点）。 若(v1,vp)E（即v1和vp相邻），则得圈C=v1vpv1。 若(v1,vp)E（即v1和vp不相邻）,可构造出一个回路。 可以证明存在结点 vi， i 1, p)，满足 vi 与v1 相邻，且 vi-1 与 vp 相邻。 反证法：设v1与上的k个结点（记为vi1, vi2, , vik）相邻，则 vp与vi1-1, , vik-1之一相邻，否则（即vp与vi1-1, , vik-1均不相邻），则vp至多邻接于p-2-k结点，即deg(vp) p-2-k，

37、deg(v1)=k, deg(v1)+deg(vp) k +(p-2-k)= p-2n-3，与题设矛盾。,无向半汉密尔顿图的充分条件,定理7-4.4(证明(2)（续）,找到了满足条件的结点 vir 以后，于是得圈C=v1vir-1vpvp-1virv1. 方法：在P中添加边(v1,vir)、(vP,vir-1)，删除边(vir-1,vir)。,v1,vp,vir-1,vir,v1,vp,vir,vir-1,定理7-4.4(证明(3),(3) 由圈得更长路径： 连通 考虑G中这条包含v1，v2，vp、长度为p的回路。 由于pn，所以V中还有一些结点不在C中，即必有回路外结点v与回路上结点(例如v

38、k)相邻，在C中删除边(vk-1,vk)而添加边(v,vk)得到通路 P=vvkvk+1vir-1vpvp-1rvirv1。显然，P比P长1，且P上有k+1个不同的结点。如图所示，可以得到一条长度为p的、包含v1，v2，vp的通路： vvkvk+1vir-1vpvp-1rvirv1 。 如此继续下去，直到得到一个包含所有结点的圈为止。,vir-1,定理7-4.4(证明(3),v,v1,vp,vir-1,vir,vk-1,vk,v,v1,vp,vir,vk-1,vk,无向汉密尔顿图的充分条件,定理7-4.5 ： 设G是n(3)阶无向简单图，若对G中任意结点u与v有 deg(u)+deg(v) n

39、 则G是汉密尔顿图。 证明： 由定理7-4.4知G连通且有汉密尔顿路=v1v2vp。 (1) 若(v1,vp)E,则得汉密尔顿回路C=v1v2vpv1. (2) 若(v1,vp)E,则与定理7-4.4证明(2b)类似,也存在汉密尔顿回路。#,4,1,3,6,2,5,极大路径：6-1-3-4-2-5 6仅与1、2、3邻接， 5与1、2、4邻接 其中6邻接于2，5邻接于4,汉密尔顿回路：6-1-3-4-5-2-6,6,3,2,1,5,4,例题 汉密尔顿图的判定,判定图是否存在汉密尔顿回路? 解： 在图中，有5个结点， deg(1)3，deg(2)3，deg(3)4，deg(4)3，deg(5)3。

40、 由于每一对结点的度数之和都大于5， 所以G中存在一条汉密尔顿回路，如 132541。,利用充分条件判定汉密尔顿图例,汉密尔顿图判定,定理给出的是汉密尔顿图（半汉密尔顿图）的充分条件，而不是必要条件。 即具有n个结点的无向图G=，若对任意两个不相邻的结点u,v E，均有deg(u)+deg(v)n（或deg(u)+deg(v) n ，但是G中仍然会存在汉密尔顿路（或汉密尔顿路）。 例图 (a)有6个结点，任意两个结点度数的和小于5，但图中存在一条汉密尔顿路。 例如：图(b)六边形中，任意两个不相邻的结点度数之和都是4，46，但是六边形存在汉密尔顿回路。,(a),(b),例 考虑在七天内安排七门

41、课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。 证明： 结点：每个结点对应于一门课程考试，共七个结点； 边：关联的两个结点对应的课程考试是由不同教师担任的； 构成7阶无向简单图。 viV，deg(vi)为与vi不是由同一位教师任课的数目。 因为每个教师所任课程数不超过4，故每个结点的度数至少是3，即deg(v)3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当的安排。,汉密尔顿图应用1,例 在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中

42、任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 证明： 结点：参加会议的人，共8个； 边：相关联的结点有共同语言； 构成8阶无向简单图， viV，deg(vi)为与vi有共同语言的人数。 由已知条件可知， vi,vjV且ij，均有deg(vi)+deg(vj)8。由定理7-4.5可知，G中存在汉密尔顿回路，设C 为G中一条汉密尔顿回路，按这条回路的顺序安排座次即可。,汉密尔顿图应用2,汉密尔顿图应用2的具体例子,例设已知下列事实：a 会讲英语，b 会讲英语和汉语，c 会讲英语、意大利语和俄语，d 会讲日语和汉

43、语，e 会讲德语和意大利语，f 会讲法语、日语和俄语，g 会讲法语、德语。问这7 个人应如何排座位，才能使每个人和他身边的人交谈？ 解：设无向图G=。其中，V=a,b,c,d,e,f,g，E= |u,vV 且u 和v 有共同语言，如下图所示，图G 是连通图，将这七个人排座围圆桌而座，使得每个人能与两边交谈，即在图G 中找汉密尔顿回路，经观察，该回路是abdfgeca。,a,c,b,e,d,f,g,例 今有n个人，已知他们中的任何二人合起来认识其余的n-2个人。证明下列各题： （1）当n3时，这n个人能排成一列，使得中间的任何人都认识两旁的人，而两端的人认识左边（或右边）的人。 （2）当n4时，

44、这n个人能排成一个圈，使得每个人都认识两旁的人。,汉密尔顿图应用3（自学）,证明： 作无向图G=，其中 V=v|v为此人群的成员，则|V|=n，并可将V表成V=v1,v2,vn。 E=(u,v)|u,vV，uv，且u与v认识 ，则G为n阶无向简单图。 由题中给的条件可知， u,vV，若uv，则 deg(u)+deg(v)n-2。 记为（*） 要证明G中存在汉密尔顿路或回路，需要对于 vi,vjV，ij，分vi与vj是否认识两种情况讨论：,汉密尔顿图应用3 （自学）,vi与vj认识，则 deg(vi)+deg(vj)2+(n-2)=n vi与vj不认识，则对于任意vkV，且kikj，vi与vj都

45、认识vk。 反证法：否则vi或vj不认识vk，比如说vi不认识vk。此时，vj与vk都不认识vi（认识是彼 此的），则vj与vk合起来至多认识其余的n-3个人， 这与已知矛盾。 于是，vi与vj都认识vk，因而由vk的任意性可知deg(vi)+deg(vj)2(n-2) （1）当n3时，2(n-2)n-1，即 deg(vi)+deg(vj)n-1，于是，无论vi与vj是否认识，都有 deg(vi)+deg(vj)n-1，由vi，vj的任意性可知，G中存在汉密尔顿路，只需按 上结点的顺序排列就可以达到要求。 （2）当n4时，2(n-2)n，即 deg(vi)+deg(vj)n 因而，无论vi与v

46、j是否认识，都有 deg(vi)+deg(vj)n ，G中存在汉密尔顿回路C，按C中顺序排圈即可达 到目的。,汉密尔顿图应用3 （自学）,汉密尔顿图判定,不满足充分条件，不能由此判断它是否汉密尔顿图。 事实上，它不满足必要条件，故不是汉密尔顿图。,无向汉密尔顿图的必要条件,定理7-4.3 ：若图G=具有汉密尔顿回路（即G是汉密尔顿图），则对于结点集V的每一个非空子集S均有W(GS)|S|成立。其中W(GS)是GS中连通分支数，|S|是结点子集S中结点的个数。 汉密尔顿图必有W(GS)|S| ， 但满足W(GS)|S|的不一定是汉密尔顿图。 用于判定非汉密尔顿图： W(GS)|S|，则为非汉密尔

47、顿图。,无向汉密尔顿图的必要条件 W(GS)|S|,知识点：母图的连通分支数小于等于生成子图的连通分支数。 删除圈中的结点产生的连通分支数删除结点个数 证明： 设C是G的一条汉密尔顿回路，则对于V的任何一个非空子集S，由点不重复的回路的特性知任意删去C 中 | S | 个点，最多将C 分为 | S | “段” ，即W(CS)|S|。 若在C中删去S中任一结点a1，则Ca1是连通非回路，即W(Ca1)=1； 若删去S中的另一个结点a2， 则当a1、a2邻接时，W(C-a1,a2)=12； 而当a1、a2不邻接时，W(C-a1,a2)=2，即 W(C-a1,a2)2=|a1，a2| 如此做下去，归纳可证 W(CS)|S| 因为CS是GS的一个生成子图，且母图的连通分支数小于等于生成子图的连通分支数 ； 因而 W(GS)W(CS) 所以 W(GS)|S|,例 判断是否为汉密尔顿图,必要条件的应用例,在图中取|S|=5，则W(G-S)6|S|5，因而该图不存在汉密尔顿回路,在图中取S=v1,v4 则GS中有三个连通分支，即W(G-S)=3|S|=2，故G不是汉密尔顿图。,必要条件的应用例,例 判断下图是否为汉密尔顿图？,因此选取