离散数学左孝凌第七章

1、7.1 图的基本概念 7.2 路与回路 7.3 图的矩阵表示 7.4 欧拉图与汉密尔顿图 7.5 树与生成树 7.6 根树及其应用 习题七,第七章 图论,7.1.1 图的基本概念 7.1.2 图的结点的度数及其计算 7.1.3 子图和图的同构,第七章 图论7.1 图的基本概念,7.1.1 图的基本概念,1.图的定义 现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。 【例7.1.1】a，b，c，d4个篮球队进行友谊比赛。为了表示个队之间比赛的情况，我们作出图7.1.1的图形。在图中个小圆圈分别表示这个篮球队，称之为结点。如果两队进行过比赛，则在表示该队的两个结

2、点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。,第七章 图论7.1 图的基本概念,图7.1.1,第七章 图论7.1 图的基本概念,第七章 图论7.1 图的基本概念,如果图7.1.1中的个结点a，b，c，d分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。 我们也可以点代表工厂,以连接两点的连线表示这两工厂间有业务往来关系。这样便可用图形表示某一城市中各工厂间的业务往来关系。这种用图形来表示事物之间的某种关系的方法我们也曾经在第三章中使用过。对于这种图形,我们的兴趣在于有多少个点和哪些点对间有线连接,至于连线

3、的长短曲直和点的位置都无关紧要。对它们进行数学抽象我们就得到以下作为数学概念的图的定义。,定义7.1.1一个图G是一个序偶V(G),E(G)，记为GV(G),E(G)。其中V(G)是非空结点集合，E(G)是边集合，对E(G)中的每条边，有V(G)中的结点的有序偶或无序偶与之对应。 若边e所对应的结点对是有序偶,则称e是有向边。a叫边e的始点,b叫边e的终点,统称为e的端点。若边e所对应的结点对是无序偶(a,b),则称e是无向边。这时统称e与两个结点a和b互相关联。我们将结点a、b的无序结点对记为(a，b)，有序结点对记为a，b。 一个图G可用一个图形来表示且表示是不唯一的。,第七章 图论7.1

4、 图的基本概念,【例7.1.2】设G=V(G),E(G),其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。则图G可用图7.1.2(a)或(b)表示。,第七章 图论7.1 图的基本概念,图7.1.2,第七章 图论7.1 图的基本概念,图7.1.2,第七章 图论7.1 图的基本概念,2.图G的结点与边之间的关系 邻接点:同一条边的两个端点。 孤立点:没有边与之关联的结点。 邻接边:关联同一个结点的两条边。 孤立边:不与任何边相邻接的边。

5、 自回路（环）：关联同一个结点的一条边（v，v）或v，v）。 平行边(多重边):关联同一对结点的多条边。,第七章 图论7.1 图的基本概念,如例7.1.1中的图，结点集Va，b，c，d，边集 Ee1，e2，e3，e4，e5，其中 e1（a，b），e2（a，c）， e3（a，d），e4（b，c），e5（c，d）。d与a、d与c是邻接的，但d与b不邻接，边e3与e5是邻接的。,第七章 图论7.1 图的基本概念,【例7.1.3】设图GV,E如图7.1.3所示。 这里Vv1，v2，v3， Ee1，e2，e3，e4，e5， 其中e1（v1，v2）， e2（v1，v3），e3（v3，v3）， e4（v2，

6、v3），e5（v2，v3）。 在这个图中，e3是关联同一个结点的一条边,即自回路；边e4和e5都与结点v2、v3关联，即它们是多重边。,第七章 图论7.1 图的基本概念,图7.1.3,第七章 图论7.1 图的基本概念,3.图G的分类 按G的结点个数和边数分为(n,m)图,即n个结点,m条边的图; 特别地,(n,0)称为零图,(1,0)图称为平凡图。 (2)按G中关联于同一对结点的边数分为多重图和简单图; 多重图:含有平行边的图（如图7.1.3）。 简单图:不含平行边和自环的图。 (3)按G的边有序、无序分为有向图、无向图和混合图; 有向图：每条边都是有向边的图称为有向图（图7.1.4(b)；

7、无向图：每条边都是无向边的图称为无向图； 混合图：既有无向边，又有有向边的图称为混合图。 本书主要研究无向图和有向图。,(a)(b) (4)按G的边旁有无数量特征分为边权图(如图7.1.4(a)、无权图; (5)按G的任意两个结点间是否有边分为完全图Kn (如图7.1.5)和不完全图(如图7.1.6)。,图7.1.4,图7.1.6,完全图：任意两个不同的结点都是邻接的简单图称为完全图。n个结点的无向完全图记为Kn。 图7.1.5给出了K3和K4。从图中可以看出K3有条边，K4有条边。容易证明Kn有条边。,图7.1.5K3与K4示意图,第七章 图论7.1 图的基本概念,给定任意一个含有n个结点的

8、图G,总可以把它补成一个具有同样结点的完全图,方法是把那些缺少的边添上。 定义7.1.2设GV,E是一个具有n个结点的简单图。以V为结点集，以从完全图Kn中删去G的所有边后得到的图（或由G中所有结点和所有能使G成为完全图的添加边组成的图）称为G的补图，记为 。 例如，零图和完全图互为补图。 图7.1.6给出了一个图G和G的补图。,第七章 图论7.1 图的基本概念,【例7.1.4】（拉姆齐问题）试证在任何一个有个人的组里，存在个人互相认识，或者存在个人互相不认识。 我们用个结点来代表人，并用邻接性来代表认识关系。这样一来，该例就是要证明：任意一个有个结点的图G中，或者有个互相邻接的点，或者有个互

9、相不邻接的点。即，对任何一个有个结点的图G，G或 中含有一个三角形（即K3）。,第七章 图论7.1 图的基本概念,证明:设GV,E，|V|6，v是G中一结点。因为v与G的其余个结点或者在 中邻接，或者在G中邻接。故不失一般性可假定，有个结点v1，v2，v3在G中与v邻接。 如果这个结点中有两个结点（如v1，v2）邻接，则它们与v3就是G中一个三角形的个顶点。如果这3个结点中任意两个在G中均不邻接，则v1，v2，v3就是 中一个三角形的个顶点。,第七章 图论7.1 图的基本概念,7.1.2图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念结点的度数。

10、 定义7.1.3图中结点v所关联的边数（有自回路时计算两次）称为结点v的度数，记为deg（v）。 如图7.1.3中的deg（v1）2，deg（v2）3，deg（v3）5。,第七章 图论7.1 图的基本概念,定理7.1.1图GV,E中结点度数的总和等于边数的两倍，即,证明:因为每条边都与两个结点关联，所以加上一条边就使得各结点度数的和增加2，由此结论成立。 推论:图G中度数为奇数的结点必为偶数个。,第七章 图论7.1 图的基本概念,证明:设V1和V2分别是G中奇数度数和偶数度数的结点集。 由定理7.1.1知,由于 是偶数之和，必为偶数，而2|E|也为偶数，故 是偶数。由此|V1|必为偶数。,第七

11、章 图论7.1 图的基本概念,定义7.1.4在有向图中,射入结点v的边数称为结点v的入度，记为 ;由结点v射出的边数称为结点v的出度，记为 。结点v的入度与出度之和就是结点v的度数。 如图7.1.4中 1， 2。,图7.1.4,定理7.1.2在任何有向图GV,E中，有,第七章 图论7.1 图的基本概念,7.1.3子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。 定义7.1.5设有图GV,E和图 GV,E。 1)若VV，EE，则称G是G的子图。 2)若G是G的子图，且EE，则称G是G的真子图。,第七章 图论7.1 图的基本概念,3)若VV，EE，则称G是G的生成子图。

12、图7.1.7给出了图G以及它的真子图G1和生成子图G2。,图7.1.7图G以及其真子图G1和生成子图G2,第七章 图论7.1 图的基本概念,2.图的同构 从图的定义可以看出，图的最本质的内容是结点与结点的邻接关系。例如例7.1.1也可以用图7.1.8中几种不同形状的图形表示。它们与图7.1.1一样，都同样表示例7.1.1中个队之间的比赛情况。从这个意义上讲，我们说它们是同一个图，并称图7.1.1与图7.1.8的(a)和(b)是同构的。,第七章 图论7.1 图的基本概念,图7.1.8同构的图,图7.1.9,图7.1.1,第七章 图论7.1 图的基本概念,定义7.1.6设有图GV,E和图GV,E。

13、如果存在双射：VV，使得e（u，v）Eiffe（(u)，(v)）E，且（u，v）与（(u)，(v)）有相同的重数，则称G与G同构。记作GG。 【例7.1.5】考察图7.1.9中的两个图GV,E和GV,E。,第七章 图论7.1 图的基本概念,显然，定义：VV，（vi）vi，可以验证是满足定义7.1.6的双射，所以GG。 对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。,第七章 图论7.1 图的基本概念,小结:本结介绍了图的基本概念、图的结点的度数及

14、其性质以及子图、生成子图与图的同构等概念。 重点：图的结点的度数及其性质以及生成子图的概念。 作业：P279（1），（2）,第七章 图论7.1 图的基本概念,7.2.1路与回路 7.2.2图的连通性,第七章 图论7.2 路与回路,定义7.2.1给定图GV,E,设v0,v1,vkV，e1，e2，ekE，其中ei是关联于结点vi-1和vi的边，称交替序列v0e1v1e2ekvk为连接v0到vk的路，v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。当v0=vk时,这条路称为回路。 在简单图中一条路v0e1v1e2ekvk由它的结点序列v0v1vk确定,所以简单图的路,可表示为v0v1v

15、k。如图7.1.1表示的简单图中，路ae1be4ce5d可写成abcd。,第七章 图论7.2 路与回路,定义7.2.2设v0e1v1e2ekvk是图G中连接v0到vk的路。 1)若e1，e2，ek都不相同，则称路为迹； 2)若v0，v1，vk都不相同，则称路为通路； 3)长度大于的闭的通路（即除v0vk外，其余结点均不相同的路）称作圈。,图7.1.1,第七章 图论7.2 路与回路,例如在图7.2.1中，有连接v5到v3的路v5e8v4e5v2e6v5e7v3，这也是一条迹；路v1e1v2e3v3是一条通路；路v1e1v2e3v3e4v2e1v1是一条回路，但不是圈；路v1e1v2e3v3e2v

16、1是一条回路，也是圈。 下面我们利用通路的概念解决一个古老的著名问题。,图7.2.1,第七章 图论7.2 路与回路,【例7.2.1】（渡河问题）一个摆渡人，要把一只狼、一只羊和一捆干草运过河去，河上有一只木船，每次除了人以外，只能带一样东西。另外，如果人不在旁时，狼就要吃羊，羊就要吃干草。问这人怎样才能把它们运过河去？ 【游戏】 解 用F表示摆渡人，W表示狼，S表示羊，H表示干草。,第七章 图论7.2 路与回路,若用FWSH表示人和其它样东西在河的左岸的状态。这样在左岸全部可能出现的状态为以下16种： FWSH FWS FWH FSH WSH FW FS FH WS WH SH F W S H

17、 这里表示左岸是空集，即人、狼、羊、干草都已运到右岸去了。,第七章 图论7.2 路与回路,根据题意检查一下就可以知道，这16种情况中有6种情况是不允许出现的。它们是：WSH、FW、FH、WS、SH、F。如FH表示人和干草在左岸，而狼和羊在右岸，这当然是不行的。因此，允许出现的情况只有10种。,第七章 图论7.2 路与回路,我们构造一个图，它的结点就是这10种状态。若一种状态可以转移到另一种状态，就在表示它们的两结点间连一条边，这样就画出图7.2.2。本题就转化为找结点FWSH到结点的通路。从图中得到两条这样的通路，即有两种渡河方案。,第七章 图论 7.2 路与回路,图7.2.2,第七章 图论

18、7.2 路与回路,定义7.2.2在图G中，若结点vi到vj有路连接（这时称vi和vj是连通的），其中长度最短的路的长度称为vi到vj的距离，用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=。 例如在图7.2.1中，（v1，v4）。 注意:在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质: (1) d(vi,vj)0; (2) d(vi,vi)=0; (3) d(vi,vj)+d(vj,vk)d(vi,vk)。,第七章 图论 7.2 路与回路,定理7.2.1 设G是具有n个结点的图，如果从结点v1到另一结点v2存在一条路，则从结点v1到v2必

19、存在一条路长度不大于n1的通路。 证明: 假定从v1到v2存在一条路径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例 (v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是通路。通路的长度比所经结点数少1,图中共n个结点,故通路长度不超过n-1。 推论 设图GV,E，|V|n，则G中任一圈长度不大于n。,7.2.2图的连通性 1.无向图的连通性 定义7.2.3在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。 定义7.2.4图G的

20、一个连通的子图G（称为连通子图）若不包含在G的任何更大的连通子图中，它就被称作G的连通分支。我们把图G的连通分支数记作W（G）。,第七章 图论 7.2 路与回路,图7.2.3图G与G,在图7.2.3中，G是不连通的，W（G），而G是连通的，W（G）。 任何一个图都可划分为若干个连通分支。显然，仅当图G的连通分支数W（G）时，图G是连通的。,第七章 图论 7.2 路与回路,2.有向图的连通性 定义7.2.5在有向图中,如果若从结点u到v有一条路，则称u可达v。 定义7.2.6设有有向图G， 1)若G的任意两个结点中,至少从一个结点可达另一个结点,则称图G是单向连通的; 2)如果G的任意两个结点都

21、是相互可达的,则称图G是 强连通的; 3)如果略去边的方向后，G成为连通的无向图，则称 图G是弱连通的。,从定义可知：若图G是单向连通的，则必是弱连通的；若图G是强连通的，则必是单向连通的，且也是弱连通的。但反之不真。 在图7.2.4中,(a)是强连通的,(b)是单向连通的,(c)是弱连通的。,第七章 图论 7.2 路与回路,图7.2.4,第七章 图论 7.2 路与回路,定理7.2.2 一个有向图G是强连通的，当且仅当G中有一个（有向）回路，它至少包含每个结点一次。 证明:必要性：如果有向图G是强连通的，则任意两个结点都是相互可达的。故必可作一回路经过图中所有各结点。否则必有一回路不包含某一结

22、点v。这样，v与回路上各结点就不能相互可达，这与G是强连通矛盾。 充分性：如果G中有一个回路，它至少包含每个结点一次，则G中任意两个结点是相互可达的，故G是强连通的。 例如，图7.2.4(a)中有一回路v1v3v2v1，它包含图中所有结点。,定义7.2.6 在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),没有包含G的更大子图G是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。 在图7.2.5中,强分图集合是: 1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8,第七章 图论 7.2 路与回路,单向分图集合是: 1,2,3,4,5,

23、e1,e2,e3,e4,e5,6,5,e6, 7,8,e7,e8 弱分图集合是: 1,2,3,4,5,6,e1,e2,e3,e4,e5,e6, 7,8,e7,e8,第七章 图论 7.2 路与回路,图7.2.5,第七章 图论 7.2 路与回路,小结:本结介绍了路、迹、通路、回路、圈及图的连通性。 作业：P287（5）a）-c），（7）,第七章 图论 7.2 路与回路,7.3.1 邻接矩阵 7.3.2 可达性矩阵,第七章 图论 7.3 图的矩阵表示,7.3.1邻接矩阵,上面我们介绍了图的一种表示方法，即用图形表示图。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。下面我们提供另一

24、种用矩阵表示图的方法。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。,第七章 图论 7.3 图的矩阵表示,定义7.3.1设GV,E是有n个结点的简单图，则n阶方阵（aij）称为G的邻接矩阵。其中,否则,如图7.3.1所示的图G，其邻接矩阵A为,第七章 图论 7.3 图的矩阵表示,如图7.3.1所示的图G，其邻接矩阵A为,显然无向图的邻接矩阵必是对称的。 下面的定理说明，在邻接矩阵A的幂A2，A3，等矩阵中，每个元素有特定的含义。,图7.3.1图G,定理7.3.1设G是具有n个结点v1,v2,vn的图，其邻接矩阵为A，则Ak（k1，2，）的（i，j）项

25、元素a(k)ij是从vi到vj的长度等于k的路的总数。 证明:施归纳于k。 当k1时，A1A，由A的定义，定理显然成立。 若kl时定理成立， 则当kl1时，Al+1AlA，,所以,根据邻接矩阵定义arj是联结vr和vj的长度为1的路数目,a(l)ir是联结vi和vr的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr经过1条边到vj的总长度为l+1的路的数目。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。,第七章 图论 7.3 图的矩阵表示,由定理7.3.1可得出以下结论： 1)如果对l1，2，n-1，Al的（i，j）

26、项元素（ij）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。 2)结点vi到vj（ij）间的距离d（vi，vj）是使Al（l1，2，n-1）的（i，j）项元素不为零的最小整数l。 3)Al的（i，i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。,第七章 图论 7.3 图的矩阵表示,【例7.3.1】图GV,E的图形如图7.3.2，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。 解:,图7.3.2,第七章 图论 7.3 图的矩阵表示,1)由A中a(1)121知，v1和v2是邻接的；由A3中a(3)122知，v1到v

27、2长度为3的路有两条，从图中可看出是v1v2v1v2和v1v2v3v2。 2)由A2的主对角线上元素知，每个结点都有长度为的回路，其中结点v2有两条：v2v1v2和v2v3v2，其余结点只有一条。 3)由于A3的主对角线上元素全为零，所以G中没有长度为的回路。,第七章 图论 7.3 图的矩阵表示,4)由于 所以结点v3和v4间无路，它们属于不同的连通分支。 5)d（v1，v3）。 对其他元素读者自己可以找出它的意义。,7.3.2可达性矩阵,下面用矩阵来研究有向图的可达性。 与无向图一样，有向图也能用相应的邻接矩阵A（aij）表示，其中,但注意这里A不一定是对称的。,第七章 图论 7.3 图的矩

28、阵表示,定义7.3.2 设GV,E是一个有n个结点的有向图，则n阶方阵P（pij）称为图G的可达性矩阵。其中,(vi到vj可达),(否则),根据可达性矩阵，可知图中任意两个结点之间是否至少存在一条路以及是否存在回路。 由7.2节定理7.2.1可知，利用有向图的邻接矩阵A，分以下两步可得到可达性矩阵。,第七章 图论 7.3 图的矩阵表示,1)令BnAA2An, 2)将矩阵n中不为零的元素均改为，为零的元素不变，所得的矩阵P就是可达性矩阵。 当n很大时，这种求可达性矩阵的方法就很复杂。下面再介绍一种更简便的求可达性矩阵的方法。,第七章 图论 7.3 图的矩阵表示,因可达性矩阵是一个元素仅为或的矩阵

29、（称为布尔矩阵），而在研究可达性问题时，我们对于两个结点间具有路的数目并不感兴趣，所关心的只是两结点间是否有路存在。因此，我们可将矩阵A，A2,An,分别改为布尔矩阵A(1)，A(2)，A(n)。,第七章 图论 7.3 图的矩阵表示,由此有 A(2)A(1)A(1)AA A(3)A(2)A(1) A(n)A(n-1)A(1) PA(1)A(2)A(n) 相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘。,第七章 图论 7.3 图的矩阵表示,图7.3.3,第七章 图论 7.3 图的矩阵表示,【例7.3.2】求出图7.3.3所示图的可达性矩阵。 解:该图的邻接矩阵为,第七章 图论 7.3 图的矩阵表示

30、,故,定理7.3.2 有向图G是强连通的当且仅当其可达性矩阵P除主对角线外，其它元素均为。,第七章 图论 7.3 图的矩阵表示,小结：本节介绍了图的邻接矩阵、可达性矩阵的概念。 重点:掌握邻接矩阵、可达性矩阵及由vi到vj长 度为k的路径的条数的求法。 作业:P300(1),(3),第七章 图论 7.3 图的矩阵表示,7.4.1 欧拉图 7.4.2 汉密尔顿图,第七章 图论 7.4 欧拉图与汉密尔顿图,7.4.1欧拉图 历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的：18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来（

31、如图7.4.1）。,第七章 图论 7.4 欧拉图与汉密尔顿图,每逢假日，城中居民进行环城游玩，人们对此提出了一个“遍游”问题，即能否有这样一种走法，使得从某地出发通过且只通过每座桥一次后又回到原地呢？ 我们将图7.4.1中的哥尼斯堡城的4块陆地部分分别标以A，B，D，将陆地设想为图的结点，而把桥画成相应的连接边，这样图7.4.1可简化成图7.4.2。于是七桥“遍游”问题等价于在图7.4.2中，从某一结点出发找到一条回路，通过它的每条边一次且仅一次，并回到原来的结点。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.1哥尼斯堡七桥问题示图,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.

32、2哥尼斯保七桥问题简化图,第七章 图论 7.4 欧拉图与汉密尔顿图,定义7.5.1 给定无孤立结点的图G，若存在一条经过G中每边一次且仅一次的回路，则该回路为欧拉回路。具有欧拉回路的图称为欧拉图。 例如，给出如图7.4.3所示的两个图，容易看出，(a)是欧拉图，而(b)不是欧拉图。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.3,第七章 图论 7.4 欧拉图与汉密尔顿图,定理7.5.1连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。 证明:必要性：设G是一欧拉图，是G中的一条欧拉回路。当通过G的任一结点时，必通过关联于该点的两条边。又因为G中的每条边仅出现一次，所以所通过的每个

33、结点的度数必定是偶数。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.4图G,第七章 图论 7.4 欧拉图与汉密尔顿图,充分性：我们可以这样来作一个闭迹，假设它从某结点A开始，沿着一条边到另一结点，接着再从这个结点，沿没有走过的边前进，如此继续下去。因为我们总是沿着先前没有走过的新边走，又由于图G的边数有限，所以这个过程一定会停止。但是，因为每一个结点都与偶数条边关联，而当沿前进到达结点v时，若vA，走过了与v关联的奇数条边，这样在v上总还有一条没有走过的边。因此，必定返回停止在A（见图7.4.4）。,第七章 图论 7.4 欧拉图与汉密尔顿图,如果走遍了G的所有边，那么我们就得到所希望的

34、一条欧拉回路。如果不是这样，那么在上将有某一结点B，与它关联的一些边尚未被走过（因G连通）。但是，实际上，因为走过了与B关联的偶数条边，因此不属于的与B关联的边也是偶数条。对于其他有未走过边所关联的所有结点来说，上面的讨论同样正确。于是若设G1是G的包含点B的一个连通分支，则G1的结点全是偶数度结点。,第七章 图论 7.4 欧拉图与汉密尔顿图,运用上面的讨论，我们在G1中得到一个从B点出发的一条闭迹1。这样我们就得到了一条更大的闭迹，它是从A点出发沿前进到达B，然后沿闭迹1回到B，最后再沿由B走到A。如果我们仍然没有走遍整个图，那么我们再次把闭迹扩大，以此类推，直到最后得到一个欧拉回路。 由于

35、在七桥问题的图7.4.2中，有个点是奇数度结点，故不存在欧拉回路，七桥问题无解。,第七章 图论 7.4 欧拉图与汉密尔顿图,在图7.2.3中，(a)图的每个结点的度数都为，所以它是欧拉图；(b)图不是欧拉图。但我们继续考察(b)图可以发现，该图中有一条路v2v3v4v5v2v1v5，它经过(b)图中的每条边一次且仅一次，我们把这样的路称为欧拉路(非欧拉回路)。 定义7.5.2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。对于欧拉路有下面的判定方法。,第七章 图论 7.4 欧拉图与汉密尔顿图,定理7.5.2连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的奇数度结点。

36、 证明:将边(vi，vj)加于图G上，令其所得的图为G（可能是多重图）。 由定理7.5.1知： G有连接结点vi和vj的欧拉路， iffG有一条欧拉回路， iffG的所有结点均为偶度结点， iffG的所有结点除vi和vj外均为偶度结点， iffvi和vj是G中仅有的奇度结点。,第七章 图论 7.4 欧拉图与汉密尔顿图,我国民间很早就流传一种“一笔画”游戏。由定理7.5.1和定理7.5.2知，有两种情况可以一笔画。 1)如果图中所有结点是偶数度结点，则可以任选一点作为始点一笔画完； 2)如果图中只有两个奇度结点，则可以选择其中一个奇度结点作为始点也可一笔画完。,第七章 图论 7.4 欧拉图与汉密

37、尔顿图,【例7.4.1】图7.4.5(a)是一幢房子的平面图形，前门进入一个客厅，由客厅通向4个房间。如果要求每扇门只能进出一次，现在你由前门进去，能否通过所有的门走遍所有的房间和客厅，然后从后门走出。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.5,第七章 图论 7.4 欧拉图与汉密尔顿图,解:将4个房间和一个客厅及前门外和后门外作为结点，若两结点有边相连就表示该两结点所表示的位置有一扇门相通。由此得图7.4.5(b)。由于图中有4个结点是奇度结点，故由定理7.5.2知本题无解。 类似于无向图的结论，对有向图有以下结果。,第七章 图论 7.4 欧拉图与汉密尔顿图,定理7.5.3一个连

38、通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度，但在这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度少1。 下面举一个有趣的例子是计算机鼓轮的设计。,第七章 图论 7.4 欧拉图与汉密尔顿图,【例7.4.1】设一个旋转鼓的表面被分成24个部分，如图7-26所示。其中每一部分分别由导体或绝缘体构成，图中阴影部分表示导体，空白部分表示绝缘体，绝缘体部分给出信号0，导体部分给出信号1。根据鼓轮转动后所处的位置，4个触头a，b，c，d将获得一定的信息。图中所示的信息为1101，若将鼓轮沿

39、顺时针方向旋转一格，则4个触头a，b，c，d获得1010。试问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一格后，4个触头得到的每组信息（共16组）均不相同？这个问题也即为：把16个二进制数字排成一个环形，使得4个依次相连的数字所组成的16个4位二进制数均不相同。,图7.4.6,第七章 图论 7.4 欧拉图与汉密尔顿图,解:问题的答案是肯定的。下面谈一下解决这个问题的思路。 设i0，1（i16）。每旋转一格，信号从1234转到2345，前者的右3位决定了后者的左3位。于是，我们的想法是将这16个二进制数字的环形1216对应一个欧拉有向路，使其边依次为1234，2345，3456，（图

40、727）。我们把234对应一个结点，它是弧1234的终点也是弧2345的始点。这样我们的问题就转化为以位二进制数为结点作一个有向图，再在图中找出欧拉回路。,图7.4.7欧拉有向路示图,第七章 图论 7.4 欧拉图与汉密尔顿图,构造一个有个结点的有向图G（图728）。其结点分别记为位二进制数000、001、010、011、100、101、110、111。从结点123出发可引出两条有向边，其终点分别是23和23，记这两条有向边为123和123。这样图G就有16条边。由于G中每点的入度等于出度都等于，故在图中可找到一条欧拉回路。,第七章 图论 7.4 欧拉图与汉密尔顿图,例如（仅写出边的序列）e0e

41、1e2e4e9e3e6e13e10e5e11e7e15e14e12e8。根据邻接边的标号记法，这16个二进制数可写成对应的二进制序列0000100110101111，把这个序列排成环状，与所求的鼓轮相对应，如图7.4.6所示。 该例可推广到鼓轮有n个触点的情况。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.8具有8个结点的有向图G,7.4.2汉密尔顿图 与欧拉回路类似的是汉密尔顿回路问题。它是1859年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在图7.4.9中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变

42、成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。,图7.4.9 12面体游戏示图,第七章 图论 7.4 欧拉图与汉密尔顿图,对图7.4.9，图中粗线给出了这样的回路。 定义7.5.3 给定图G，若有一条路通过G中每个结点恰好一次，则这样的路称为汉密尔顿路；若有一个圈，通过G个每个结点恰好一次，这样的圈称为汉密尔顿回路（或汉密尔顿圈）。具有汉密尔顿回路的图称为汉密尔顿图。 尽管汉密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不知道一个图为汉密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的主要问题之一。下面

43、先给出一个简单而有用的必要条件。,第七章 图论 7.4 欧拉图与汉密尔顿图,定理7.5.4设图GV,E是汉密尔顿图，则对于V的每个非空子集S，均有 W（GS）|S| 成立，其中W（GS）是图GS的连通分支数。,第七章 图论 7.4 欧拉图与汉密尔顿图,证明:设是G的汉密尔顿回路，S是V的任一非空子集。在GS中，最多被分为|S|段，所以 W（GS）|S| 利用本定理可判别某些图不为汉密尔顿图。如在图7.4.10中，若取Sv1，v4，则GS有3个连通分支，故该图不是汉密尔顿图。 判断汉密尔顿图的充分条件很多，我们仅介绍其中一个。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.10,第七章 图

44、论 7.4 欧拉图与汉密尔顿图,定理7.5.5设GV,E是有n个结点的简单图， 1）如果任两结点u，vV，均有 deg(u)deg(v)n1， 则在G中存在一条汉密尔顿路； 2）如果对任两结点u，vV，均有 deg(u)deg(v)n， 则G是汉密尔顿图。证明略。,第七章 图论 7.4 欧拉图与汉密尔顿图,【例7.4.2】某地有个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这处？ 解将景点作为结点，道路作为边，则得到一个有个结点的无向图。 由题意，对每个结点vi，有deg(vi)2（i5）。 则对任两点vi，vj（i，j5）均有 deg(vi)deg(vj)

45、22451 可知此图一定有一条汉密尔顿路，本题有解。,第七章 图论 7.4 欧拉图与汉密尔顿图,我们再通过一个例子，介绍一个判别汉密尔顿路不存在的标号法。 【例7.4.3】证明图731所示的图没有汉密尔顿路。 证明:任取一结点如v1，用A标记，所有与它相邻的结点标B。继续不断地用A标记所有邻接于B的结点，用B标记所有邻接于A的结点，直到图中所有结点全部标记完毕。 如果图中有一条汉密尔顿路，则必交替通过结点A和B。因此或者结点A和B数目一样，或者两者相差个。,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.11,而本题有个结点标记A，个结点标记B，它们相差个，所以该图不存在汉密尔顿路。 作为

46、汉密尔顿回路的自然推广是著名的货郎担问题。问题是这样叙述的：设有一个货郎，从他所在的城镇出发去n个城镇。要求经过每个城镇恰好一次，然后返回原地，问他的旅行路线怎样安排才最经济？从图论的观点来看，该问题就是：在一个有权完全图中找一条权最小的汉密尔顿回路。,第七章 图论 7.4 欧拉图与汉密尔顿图,研究这个问题是十分有趣且有实用价值的。但很可惜，至今没有找到一个很有效的算法。 当然我们可以用枚举法来解，但是当完全图的结点较多时，枚举法的运算量在计算机上也很难实现。下面介绍的“最邻近方法”给出了问题的近似解。最邻近方法的步骤如下： 1)由任意选择的结点开始，找与该点最靠近（即权最小）的点，形成有一条

47、边的初始路径。,第七章 图论 7.4 欧拉图与汉密尔顿图,2) 设表示最新加到这条路上的结点，从不在路上的所有结点中选一个与最靠近的结点，把连接与这一结点的边加到这条路上。重复这一步，直到G中所有结点包含在路上。 3) 将连接起始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为问题的近似解。,第七章 图论 7.4 欧拉图与汉密尔顿图,【例7.4.4】某流动售货员居住在城，为推销货物他要访问，d城后返回城。若该城间的距离如图7.4.12所示，试用最邻近方法找出完成该旅行的最短路线？ 解按最邻近方法一共有步，见图7.4.13。得到的总距离为46。,第七章 图论 7.4 欧拉图与汉密尔顿图

48、,图7.4.12,第七章 图论 7.4 欧拉图与汉密尔顿图,图7.4.13,第七章 图论 7.4 欧拉图与汉密尔顿图,小结：本节介绍了两种特殊的图欧拉图与汉密尔顿图及其判别方法。 重点:掌握欧拉图及一笔画图的判别方法。 作业:P311(1),(3),第七章 图论 7.4 欧拉图与汉密尔顿图,7.5.1 无向树 7.5.2 无向图中的生成树与最小生成树,第七章 图论 7.5 树与生成树,7.5.1无向树 树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中2H2n+2的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树

49、的基本知识，其中谈到的图都假定是简单图。,第七章 图论 7.5 树与生成树,定义7.5.1 一个连通无环无向图称为无向树(简称为树)。记作T。树中度数为1的结点称为树叶（或终端结点），度数大于的结点称为分枝点（或内点，或非终端结点）。一个无圈图称为森林。 显然若图G是森林，则G的每个连通分支是树。如图7.5.1(a)所示的是一棵树；(b)所示的是森林。,第七章 图论 7.5 树与生成树,图7.5.1树和森林示意图,第七章 图论 7.5 树与生成树,【例7.5.1】判断图7.5.2中各图是否为树.,图7.5.2,第七章 图论 7.5 树与生成树,证：因为T是一棵n的（n，m）树，所以由定理7.5

50、.1，有,若T中的无树叶，则T中每个顶点的度数2,则 deg(vi)2n,（2） 若T中只有一片树叶，则T中只有一个结点度数为1,其它结点度数2,所以,(1),(3),(2),(3)都与(1)矛盾。所以T中至少有两片树叶。证毕。,定理7.5.1 任一树T中,至少有两片树叶(n2时)。,定理7.5.2一个无向图（n,m）图T是树,当且仅当下列5条之一成立。(或者说,这5条的任一条都可作为树的定义。) (1)无环且m=n-1。 (2)连通且m=n-1。 (3)无环,但增加任一新边,得到且仅得到一个环。 (4)连通但删去任一边,图便不连通(n2)。 (5)每一对结点间有唯一的一条通路。(n2)。,第

51、七章 图论 7.5 树与生成树,证:(1)证明由树的定义可知T无环。下证m=n-1。 对n作归纳。 n=1时,m=0,显然m=n-1。 假设n=k时命题成立,现证明n=k+1时也成立。 由于树是连通而无环,所以至少有一个度数为1的结点v,在T中删去v及其关联边,便得到k个结点的连通无环图。由归纳假设它有k-1条边。再将顶点v及其关联边加回得到原图T,所以T中含有k+1个顶点和k条边,符合公式m=n-1。所以树是无环且m=n-1的图。,第七章 图论 7.5 树与生成树,(2)证明由第(1)条可推出第(2)条。 用反证法。若图不连通,设T有k个连通分支(k2)T1,T2,Tk,其结点数分别是n1,

52、n2,nk,边数分别为m1,m2,mk,于是,得出矛盾。所以T是连通且m=n-1的图。,第七章 图论 7.5 树与生成树,(3)证明由第(2)条可推出第(3)条。 首先证明T无圈。对n作归纳证明。 n=1时,m=n-1=0,显然无圈。 假设结点数为n-1时无圈,今考察结点数是n的情况。此时至少有一个结点v其度数deg(v)=1。我们删去v及其关联边得到新图T,根据归纳假设T无圈,再加回v及其关联边又得到图T,则T也无圈。 其次,若在连通图T中增加一条新边(vi,vj),则由于T中由vi到vj存在一条通路,故必有一个圈通过vi,vj。若这样的圈有两个，则去掉(vi,vj),T中必存在通过vi,v

53、j的圈，与T无圈矛盾。故加上边(vi,vj)得到一个切仅一个圈。,第七章 图论 7.5 树与生成树,(4)证明由第(3)条可推出第(4)条。 若图不连通,则存在两个结点vi和vj,在vi和vj之间没有路,若加边(vi,vj)不会产生简单回路（圈）,但这与假设矛盾。由于T无圈,所以删去任一边,图便不连通。 (5)证明由第(4)条可推出第(5)条。 由连通性知,任两点间有一条路径,于是有一条通路。若此通路不唯一,则T中含有简单回路,删去此回路上任一边,图仍连通,这与假设不符,所以通路是唯一的。,第七章 图论 7.5 树与生成树,(6)证明由第(5)条可推出树的定义。 显然连通。若有圈,则圈上任意两

54、点间有两条通路,此与通路的唯一性矛盾。证毕。 由定理7.5.2所刻画的树的特征可见：在结点数给定的所有图中，树是边数最少的连通图，也是边数最多的无圈图。由此可知，在一个（n，m）图G中，若mn1，则G是不连通的；若mn1，则G必定有圈。,第七章 图论 7.5 树与生成树,【例7.5.2】T是一棵树,有两个2度结点，一个3度结点，三个4度结点，T有几片树叶？ 解：设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数 m=n-1=5+x 又由 得2（5+x）=22+31+43+x 所以x=9，即树T有9片树叶。,第七章 图论 7.5 树与生成树,7.5.2无向图中的生成树与最小生成树 定义

55、7.5.2若无向(连通图)G的生成子图是一棵树，则称该树是G的生成树，记为TG。生成树TG中的边称为树枝。图G中其它边称为TG的弦。所有这些弦的集合称为TG的补。 如图7.5.3中(b)、(c)所示的树T1、T2是(a)图的生成树，而(d)所示的树T3不是(a)图的生成树。一般的，图的生成树不唯一。,第七章 图论 7.5 树与生成树,图7.5.3,第七章 图论 7.5 树与生成树,考虑生成树T1，可知e1，e2，e3，e4是T1的树枝，e5，e6，e7是T1的弦，集合e5，e6，e7是T1的补。生成树有其一定的实际意义。 【例7.5.3】某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如

56、图7.5.3(a)图的无向边铺设。为使这处都有道路相通，问至少要铺几条路？ 解这实际上是求G的生成树的边数问题。 一般情况下，设连通图G有n个结点，m条边。由树的性质知，T有n个结点，n1条树枝，mn1条弦。 在图7.5.3(a)中，n5，则n1514，所以至少要修条路才行。,定义7.5.3设GV,E是一连通的有权图，则G的生成树TG为带权生成树,TG的树枝所带权之和称为生成树TG的权,记为C(TG)。G中具有最小权的生成树TG称为G的最小生成树。 求最小生成树问题是有实际意义的。 如要建造一个连接若干城市的铁路网络，已知城市vi和vj之间直达铁路的造价，设计一个总造价为最小的铁路网络，就是求

57、最小生成树TG。 下面介绍求TG的克鲁斯克尔（Kruskal)算法。,此方法又称为“避环法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下： 1)在G中选取最小权边，置边数i1。 2)当in1时，结束。否则，转3)。 3)设已选择边为e1,e2,ei，在G中选取不同于e1,e2,ei的边ei+1,使e1,e2,ei,ei+1无环且ei+1是满足此条件的最小权边。 4)置i为i1，转2)。,第七章 图论 7.5 树与生成树,【例7.5.4】求图7.5.4(0)中有权图的最小生成树。 解:因为图中n8，所以按算法要执行n17次，其过程见图7.5.4中(1)(7)。,第七章 图论 7

58、.5 树与生成树,图7.5.4,第七章 图论 7.5 树与生成树,【例7.5.5】求图7.5.5中有权图G的最小生成树。 解:因为图中n8，所以按算法要执行n17次。,图7.5.5,第七章 图论 7.5 树与生成树,【例7.5.6】图7.5.6所示的赋权图G表示七个城市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。,图7.5.6,解:该问题相当于求图的最小生成树问题，此图的最小生成树为图7.5.6中的TG,因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为： ()2348,第七章 图论 7.5 树与

59、生成树,小结：本节介绍了树、生成树和最小生成树的概念、树的六种等价定义及最小生成树的求法。 重点:掌握六种等价定义及最小生成树的求法。 作业:P327(2),(3),(6),第七章 图论 7.5 树与生成树,7.6.1 有向树 7.6.2 m叉树 7.6.3 最优二叉树,第七章 图论 7.6 根树及其应用,7.6.1 有向树,图7.6.1,7.6.1 有向树 定义7.6.1一个有向图，若不考虑边的方向，它是一棵树，则这个有向图称为有向树。一棵有向树，如果恰有一个结点的入度为，其余所有结点的入度都为，则称为根树，其中入度为的结点称为树根，出度为的结点称为树叶，出度不为的结点称为分枝点或内点。,第七章 图论 7.6 根树及其应用,如图7.6.2(a)表示一棵根树，其中v1为树根，v1，v2，v3为分枝点，其余结点为树叶。习惯上我们把根树的根画在上方，叶画在下方。这样就