离散数学-下载课件.ppt

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.图的定义图的定义 现实世界中许多现象能用某种图形表示现实世界中许多现象能用某种图形表示,这种图形这种图形是由一些点和一些连接两点间的连线所组成。是

2、由一些点和一些连接两点间的连线所组成。【例例7.1.1】a，b，c，d4个篮球队进行友谊比赛。个篮球队进行友谊比赛。为了表示个队之间比赛的情况，我们作出图为了表示个队之间比赛的情况，我们作出图7.1.1的图形。在图中个小圆圈分别表示这个篮球队，的图形。在图中个小圆圈分别表示这个篮球队，称之为结点。如果两队进行过比赛，则在表示该队称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这的两个结点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。样利用一个图形使各队之间的比赛情况一目了然。第七章第七章 图论图论7.1 图的基本概念图的基本

3、概念图图7.1.1第七章第七章 图论图论7.1 图的基本概念图的基本概念第七章第七章 图论图论7.1 图的基本概念图的基本概念 如果图如果图7.1.1中的个结点中的个结点a，b，c，d分别表示个人，分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。来。这时的图又反映了这个人之间的认识关系。我们也可以点代表工厂我们也可以点代表工厂,以连接两点的连线表示这两以连接两点的连线表示这两工厂间有业务往来关系。这样便可用图形表示某一城市工厂间有业务往来关系。这样便可用图形表示某一城市中各工厂间的业务往来关

4、系。这种用图形来表示事物之中各工厂间的业务往来关系。这种用图形来表示事物之间的某种关系的方法我们也曾经在第三章中使用过。对间的某种关系的方法我们也曾经在第三章中使用过。对于这种图形于这种图形,我们的兴趣在于有多少个点和哪些点对间有我们的兴趣在于有多少个点和哪些点对间有线连接线连接,至于连线的长短曲直和点的位置都无关紧要。对至于连线的长短曲直和点的位置都无关紧要。对它们进行数学抽象我们就得到以下作为数学概念的图的它们进行数学抽象我们就得到以下作为数学概念的图的定义。定义。定义定义7.1.1一个图一个图G是一个序偶是一个序偶V(G),E(G)，记，记为为GV(G),E(G)。其中。其中V(G)是非

5、空结点集合，是非空结点集合，E(G)是边集合，对是边集合，对E(G)中的每条边，有中的每条边，有V(G)中的结中的结点的有序偶或无序偶与之对应。点的有序偶或无序偶与之对应。若边若边e所对应的结点对是有序偶所对应的结点对是有序偶,则称则称e是有向是有向边。边。a叫边叫边e的始点的始点,b叫边叫边e的终点的终点,统称为统称为e的端点。若的端点。若边边e所对应的结点对是无序偶所对应的结点对是无序偶(a,b),则称则称e是无向边。是无向边。这时统称这时统称e与两个结点与两个结点a和和b互相关联。互相关联。我们将结点我们将结点a、b的无序结点对记为的无序结点对记为(a，b)，有序结点对记为，有序结点对记

6、为 a，b。一个图一个图G可用一个图形来表示且表示是不唯一的。可用一个图形来表示且表示是不唯一的。第七章第七章 图论图论7.1 图的基本概念图的基本概念 【例例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

7、.1.2第七章第七章 图论图论7.1 图的基本概念图的基本概念2.图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点:同一条边的两个端点。同一条边的两个端点。孤立点孤立点:没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边:关联同一个结点的两条边。关联同一个结点的两条边。孤立边孤立边:不与任何边相邻接的边。不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（自回路（环）：关联同一个结点的一条边（v，v）或）或v，v）。）。平行边平行边(多重边多重边):关联同一对结点的多条边。关联同一对结点的多条边。第七章第七章 图论图论7.1 图的基本概念图的基本概念如例如例7.1.1中

8、的图，结点集中的图，结点集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，v3），），e5（v2，v3）。

9、）。在这个图中，在这个图中，e3是关联同一个结点的一条边是关联同一个结点的一条边,即自回路；即自回路；边边e4和和e5都与结点都与结点v2、v3关联，即它们是多重边。关联，即它们是多重边。第七章第七章 图论图论7.1 图的基本概念图的基本概念图图7.1.3第七章第七章 图论图论7.1 图的基本概念图的基本概念3.图图G的分类的分类(1)按按G的结点个数和边数分为的结点个数和边数分为(n,m)图图,即即n个结点个结点,m条边条边的图的图;特别地特别地,(n,0)称为称为零图零图,(1,0)图称为图称为平凡图平凡图。(2)按按G中关联于同一对结点的边数分为中关联于同一对结点的边数分为多重图和简单图

10、多重图和简单图;多重图多重图:含有平行边的图（如图含有平行边的图（如图7.1.3）。）。简单图简单图:不含平行边和自环的图。不含平行边和自环的图。(3)按按G的边有序、无序分为的边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图;有向图：有向图：每条边都是有向边的图称为有向图（图每条边都是有向边的图称为有向图（图7.1.4(b)；无向图：无向图：每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；混合图：混合图：既有无向边，又有有向边的图称为混合图。既有无向边，又有有向边的图称为混合图。本书主要研究无向图和有向图。本书主要研究无向图和有向图。(a)(b)(4)按按G的边旁

11、有无数量特征分为的边旁有无数量特征分为边权图边权图(如图如图7.1.4(a)、无权图无权图;(5)按按G的任意两个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn(如图如图7.1.5)和和不完全图不完全图(如图如图7.1.6)。图图7.1.4图图7.1.6完全图完全图：任意两个不同的结点都是邻接的简单图称为：任意两个不同的结点都是邻接的简单图称为完全图。完全图。n n个结点的无向完全图记为个结点的无向完全图记为K Kn n。图图7.1.57.1.5给出了给出了K K3 3和和K K4 4。从图中可以看出。从图中可以看出K K3 3有条边，有条边，K K4 4有条边。容易证明有条边

12、。容易证明K Kn n有条边。有条边。(1)2n n 图图7.1.5K3与与K4示意图示意图第七章第七章 图论图论7.1 图的基本概念图的基本概念 给定任意一个含有给定任意一个含有n个结点的图个结点的图G,总可以把它补成总可以把它补成一个具有同样结点的完全图一个具有同样结点的完全图,方法是把那些缺少的边方法是把那些缺少的边添上。添上。定义定义7.1.2设设GV,E是一个具有是一个具有n个结点的简单个结点的简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G的所有边的所有边后得到的图（或由后得到的图（或由G中所有结点和所有能使中所有结点和所有能使G成为完成为完全图的添加边

13、组成的图）称为全图的添加边组成的图）称为G的补图，记为的补图，记为 。例如，零图和完全图互为补图。例如，零图和完全图互为补图。图图7.1.6给出了一个图给出了一个图G和和G的补图。的补图。GG第七章第七章 图论图论7.1 图的基本概念图的基本概念 【例例7.1.4】（拉姆齐问题）试证在任何一个（拉姆齐问题）试证在任何一个有个人的组里，存在个人互相认识，或者有个人的组里，存在个人互相认识，或者存在个人互相不认识。存在个人互相不认识。我们用个结点来代表人，并用邻接性来代我们用个结点来代表人，并用邻接性来代表认识关系。这样一来，该例就是要证明：任表认识关系。这样一来，该例就是要证明：任意一个有个结点

14、的图意一个有个结点的图G中，或者有个互相邻中，或者有个互相邻接的点，或者有个互相不邻接的点。即，对接的点，或者有个互相不邻接的点。即，对任何一个有个结点的图任何一个有个结点的图G，G或或 中含有一个中含有一个三角形（即三角形（即K3）。）。G第七章第七章 图论图论7.1 图的基本概念图的基本概念 证明证明:设设GV,E，|V|6，v是是G中一结点。中一结点。因为因为v与与G的其余个结点或者在的其余个结点或者在 中邻接，或者中邻接，或者在在G中邻接。故不失一般性可假定，有个结点中邻接。故不失一般性可假定，有个结点v1，v2，v3在在G中与中与v邻接。邻接。如果这个结点中有两个结点（如如果这个结点

15、中有两个结点（如v1，v2）邻）邻接，则它们与接，则它们与v3就是就是G中一个三角形的个顶点。中一个三角形的个顶点。如果这如果这3个结点中任意两个在个结点中任意两个在G中均不邻接，则中均不邻接，则v1，v2，v3就是就是 中一个三角形的个顶点。中一个三角形的个顶点。GG第七章第七章 图论图论7.1 图的基本概念图的基本概念 7.1.2图的结点的度数及其计算图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念点关联，这就引出了图的一个重要概念结点的结点的度数。度数。定义定义7.1.3图中结点图中结点v所关联的边数（

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

17、结点必为偶数个。第七章第七章 图论图论7.1 图的基本概念图的基本概念 证明证明:设设V1和和V2分别是分别是G中奇数度数和偶数度数的中奇数度数和偶数度数的结点集。结点集。由定理由定理7.1.1知知 由于由于 是偶数之和，必为偶数，而是偶数之和，必为偶数，而2|E|也也为偶数，故为偶数，故 是偶数。由此是偶数。由此|V1|必为偶数。必为偶数。1deg()VEvvVvVv2)deg()deg(212)deg(Vvv第七章第七章 图论图论7.1 图的基本概念图的基本概念 定义定义7.1.4在有向图中在有向图中,射入结点射入结点v的边数称为结点的边数称为结点v的入度，记为的入度，记为 ;由结点由结点

18、v射出的边数称为结点射出的边数称为结点v的出度，记为的出度，记为 。结点。结点v的入度与出度之和就是的入度与出度之和就是结点结点v的度数。的度数。如图如图7.1.4中中 1，2。)(degv)(degv)(deg a)(deg d图图7.1.4 定理定理7.1.2在任何有向图在任何有向图GV,E中，有中，有EvvVvVv)(deg)(deg第七章第七章 图论图论7.1 图的基本概念图的基本概念7.1.3子图和图的同构子图和图的同构1.子图子图在研究和描述图的性质时，子图的概念占有重要地在研究和描述图的性质时，子图的概念占有重要地位。位。定义定义7.1.5设有图设有图GV,E和图和图GV,E。1

19、)若若V V，E E，则称，则称G是是G的子图。的子图。2)若若G是是G的子图，且的子图，且EE，则称，则称G是是G的真子图。的真子图。第七章第七章 图论图论7.1 图的基本概念图的基本概念3)若若VV，E E，则称，则称G是是G的生成子图。的生成子图。图图7.1.7给出了图给出了图G以及它的真子图以及它的真子图G1和生成子图和生成子图G2。图图7.1.7图图G以及其真子图以及其真子图G1和生成子图和生成子图G2第七章第七章 图论图论7.1 图的基本概念图的基本概念 2.图的同构图的同构 从图的定义可以看出，图的最本质的内从图的定义可以看出，图的最本质的内容是结点与结点的邻接关系。例如例容是结

20、点与结点的邻接关系。例如例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和图

21、和图GV,E。如果存在双射。如果存在双射：VV，使得，使得e（u，v）Eiffe（(u)，(v)）E，且（，且（u，v）与）与（(u)，(v)）有相同的重数，则称）有相同的重数，则称G与与G同构。同构。记作记作G G。【例例7.1.5】考察图考察图7.1.9中的两个图中的两个图GV,E和和GV,E。第七章第七章 图论图论7.1 图的基本概念图的基本概念 显然，定义显然，定义：VV，（vi）vi，可以验，可以验证证是满足定义是满足定义7.1.6的双射，所以的双射，所以G G。对于同构，形象地说，若图的结点可以任意挪对于同构，形象地说，若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条

22、件动位置，而边是完全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。但它们的拓扑结构是一样的。第七章第七章 图论图论7.1 图的基本概念图的基本概念 小结小结:本结介绍了图的基本概念、图的结点的度本结介绍了图的基本概念、图的结点的度数及其性质以及子图、生成子图与图的同构等概念。数及其性质以及子图、生成子图与图的同构等概念。重点：图的结点的度数及其性质以及生成子图的重点：图的结点的度数及其性质以及生成子图的概念。概念。

23、作业：作业：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时时,这条路称为回路。这条路称为回路。在简单

24、图中一条路在简单图中一条路v0e1v1e2ekvk由它的结点序列由它的结点序列v0v1vk确定确定,所以简单图的路所以简单图的路,可表示为可表示为v0v1vk。如图。如图7.1.1表示的简单图中，路表示的简单图中，路ae1be4ce5d可写成可写成abcd。第七章第七章 图论图论7.2 路与回路路与回路 定义定义7.2.2设设v0e1v1e2ekvk是是图图G中连接中连接v0到到vk的路。的路。1)若若e1，e2，ek都不相同，都不相同，则称路则称路为迹；为迹；2)若若v0，v1，vk都不相同，都不相同，则称路则称路为通路；为通路；3)长度大于的闭的通路（即长度大于的闭的通路（即除除v0vk外

25、，其余结点均不相同的外，其余结点均不相同的路）路）称作圈。称作圈。图图7.1.1第七章第七章 图论图论7.2 路与回路路与回路 例如在图例如在图7.2.1中，有连接中，有连接v5到到v3的路的路v5e8v4e5v2e6v5e7v3，这，这也是一条迹；路也是一条迹；路v1e1v2e3v3是一是一条通路；路条通路；路v1e1v2e3v3e4v2e1v1是是一条回路，但不是圈；路一条回路，但不是圈；路v1e1v2e3v3e2v1是一条回路，也是是一条回路，也是圈。圈。下面我们利用通路的概念解下面我们利用通路的概念解决一个古老的著名问题。决一个古老的著名问题。图图7.2.1第七章第七章 图论图论7.2

26、 路与回路路与回路 【例例7.2.1】（渡河问题）一个摆渡人，要把一只（渡河问题）一个摆渡人，要把一只狼、一只羊和一捆干草运过河去，河上有一只木船，狼、一只羊和一捆干草运过河去，河上有一只木船，每次除了人以外，只能带一样东西。另外，如果人每次除了人以外，只能带一样东西。另外，如果人不在旁时，狼就要吃羊，羊就要吃干草。问这人怎不在旁时，狼就要吃羊，羊就要吃干草。问这人怎样才能把它们运过河去？样才能把它们运过河去？【游戏游戏】解解 用用F表示摆渡人，表示摆渡人，W表示狼，表示狼，S表示羊，表示羊，H表表示干草。示干草。第七章第七章 图论图论7.2 路与回路路与回路 若用若用FWSH表示人和其它样东

27、西在河的左岸的表示人和其它样东西在河的左岸的状态。这样在左岸全部可能出现的状态为以下状态。这样在左岸全部可能出现的状态为以下16种：种：FWSH FWS FWH FSH WSH FW FS FH WS WH SH F W S H 这里这里表示左岸是空集，即人、狼、羊、干草都表示左岸是空集，即人、狼、羊、干草都已运到右岸去了。已运到右岸去了。第七章第七章 图论图论7.2 路与回路路与回路 根据题意检查一下就可以知道，这根据题意检查一下就可以知道，这16种情种情况中有况中有6种情况是不允许出现的。它们是：种情况是不允许出现的。它们是：WSH、FW、FH、WS、SH、F。如。如FH表示表示人和干草在

28、左岸，而狼和羊在右岸，这当然人和干草在左岸，而狼和羊在右岸，这当然是不行的。因此，允许出现的情况只有是不行的。因此，允许出现的情况只有10种。种。第七章第七章 图论图论7.2 路与回路路与回路 我们构造一个图，它的结点就是这我们构造一个图，它的结点就是这10种状种状态。若一种状态可以转移到另一种状态，就态。若一种状态可以转移到另一种状态，就在表示它们的两结点间连一条边，这样就画在表示它们的两结点间连一条边，这样就画出图出图7.2.2。本题就转化为找结点。本题就转化为找结点FWSH到结到结点点的通路。从图中得到两条这样的通路，的通路。从图中得到两条这样的通路，即有两种渡河方案。即有两种渡河方案。

29、第七章第七章 图论图论 7.2 路与回路路与回路图7.2.2第七章第七章 图论图论 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),但一般但一般地满足以下性质地满足以下

30、性质:(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必必存在一条路长度不大于存在一条路长度不大于n1的通路。的通路。证明证明:假定从假定从v1到到v2存在一条路径存在一条路径,(v1,vi,v2)是是所经的结点所经的结点,如果其中有相同的结点如果其中有相同的结点vk,例例 (v1,vi,vk,vk,v2),则删去从则删

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

32、结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。通的，否则是不连通的。定义定义7.2.4图图G的一个连通的子图的一个连通的子图G（称为连（称为连通子图）若不包含在通子图）若不包含在G的任何更大的连通子图的任何更大的连通子图中，它就被称作中，它就被称作G的连通分支。我们把图的连通分支。我们把图G的的连通分支数记作连通分支数记作W（G）。）。第七章第七章 图论图论 7.2 路与回路路与回路图图7.2.3图图G与与G在图在图7.2.3中，中，G是不连通的，是不连通的，W（G），而），而G是连是连通的，通的，W（G）。）。任何一个图都可划分为若干个连通分支。显然，仅当任何一个图都可划分为

33、若干个连通分支。显然，仅当图图G的连通分支数的连通分支数W（G）时，图）时，图G是连通的。是连通的。第七章第七章 图论图论 7.2 路与回路路与回路2.有向图的连通性有向图的连通性定义定义7.2.5在有向图中在有向图中,如果若从结点如果若从结点u到到v有一条路，有一条路，则称则称u可达可达v。定义定义7.2.6设有有向图设有有向图G，1)若若G的任意两个结点中的任意两个结点中,至少从一个结点可达另一至少从一个结点可达另一个结点个结点,则称图则称图G是单向连通的是单向连通的;2)如果如果G的任意两个结点都是相互可达的的任意两个结点都是相互可达的,则称图则称图G是是强连通的强连通的;3)如果略去边

34、的方向后，如果略去边的方向后，G成为连通的无向图，则称成为连通的无向图，则称图图G是弱连通的。是弱连通的。从定义可知：若图从定义可知：若图G是单向连通的，则必是单向连通的，则必是弱连通的；若图是弱连通的；若图G是强连通的，则必是是强连通的，则必是单向连通的，且也是弱连通的。但反之不单向连通的，且也是弱连通的。但反之不真。真。在图在图7.2.4中中,(a)是强连通的是强连通的,(b)是单向连通是单向连通的的,(c)是弱连通的。是弱连通的。第七章第七章 图论图论 7.2 路与回路路与回路图图7.2.4第七章第七章 图论图论 7.2 路与回路路与回路 定理定理7.2.2 一个有向图一个有向图G是强连

35、通的，当且仅当是强连通的，当且仅当G中有一中有一个（有向）回路，它至少包含每个结点一次。个（有向）回路，它至少包含每个结点一次。证明证明:必要性：如果有向图必要性：如果有向图G是强连通的，则任意两个结是强连通的，则任意两个结点都是相互可达的。故必可作一回路经过图中所有各结点都是相互可达的。故必可作一回路经过图中所有各结点。否则必有一回路不包含某一结点点。否则必有一回路不包含某一结点v。这样，。这样，v与回路与回路上各结点就不能相互可达，这与上各结点就不能相互可达，这与G是强连通矛盾。是强连通矛盾。充分性：如果充分性：如果G中有一个回路，它至少包含每个结点一中有一个回路，它至少包含每个结点一次，

36、则次，则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,e

37、3,4,5,6,7,8,e7,e8第七章第七章 图论图论 7.2 路与回路路与回路单向分图集合是单向分图集合是:1,2,3,4,5,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 路与回路

38、路与回路7.3.1 邻接矩阵邻接矩阵7.3.2 可达性矩阵可达性矩阵第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示7.3.1邻接矩阵邻接矩阵 上面我们介绍了图的一种表示方法，即用图上面我们介绍了图的一种表示方法，即用图形表示图。它的优点是形象直观，但是这种形表示图。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。表示在结点与边的数目很多时是不方便的。下面我们提供另一种用矩阵表示图的方法。下面我们提供另一种用矩阵表示图的方法。利用这种方法，我们能把图用矩阵存储在计利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的算机中，利用矩阵的运算还可以了

39、解到它的一些有关性质。一些有关性质。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示 定义定义7.3.1设设GV,E是有是有n个结点的简单图，个结点的简单图，则则n阶方阵（阶方阵（aij）称为）称为G的邻接矩阵。其中的邻接矩阵。其中1(,)0ijijEa 否则否则如图如图7.3.1所示的图所示的图G，其邻接矩阵，其邻接矩阵A为为第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示如图如图7.3.1所示的图所示的图G，其邻，其邻接矩阵接矩阵A为为0111110100110101010110010A 显然无向图的邻接矩阵必是对称的。显然无向图的邻接矩阵必是对称的。下面的定理说明，在邻接

40、矩阵下面的定理说明，在邻接矩阵A的幂的幂A2，A3，等矩阵中，每个元素有特定的含义。等矩阵中，每个元素有特定的含义。图图7.3.1图图G定理定理7.3.1设设G是具有是具有n个结点个结点v1,v2,vn的图，的图，其邻接矩阵为其邻接矩阵为A，则，则Ak（k1，2，）的（）的（i，j）项元素）项元素a(k)ij是从是从vi到到vj的长度等于的长度等于k的路的的路的总数。总数。证明证明:施归纳于施归纳于k。当当k1时，时，A1A，由，由A的定义，定理显然成立。的定义，定理显然成立。若若kl时定理成立，时定理成立，则当则当kl1时，时，Al+1AlA，所以所以rjnrlirlijaaa1)()1(根

41、据邻接矩阵定义根据邻接矩阵定义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可得出以下结论：可得出以下结

42、论：1)如果对如果对l1，2，n-1，Al的（的（i，j）项元素（）项元素（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 图的矩阵

43、表示图的矩阵表示【例例7.3.1】图图GV,E的图形如图的图形如图7.3.2，求，求邻接矩阵邻接矩阵A和和A2，A3，A4，并分析其元素的图，并分析其元素的图论意义。论意义。解解:0100010000000100010100010A图图7.3.2第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示1)由由A中中a(1)121知，知，v1和和v2是邻接的；由是邻接的；由A3中中a(3)122知，知，v1到到v2长度为长度为3的路有两条，从的路有两条，从图中可看出是图中可看出是v1v2v1v2和和v1v2v3v2。2)由由A2的主对角线上元素知，每个结点都有的主对角线上元素知，每个结点都有长度

44、为的回路，其中结点长度为的回路，其中结点v2有两条：有两条：v2v1v2和和v2v3v2，其余结点只有一条。，其余结点只有一条。3)由于由于A3的主对角线上元素全为零，所以的主对角线上元素全为零，所以G中中没有长度为的回路。没有长度为的回路。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示4)由于由于 所以结点所以结点v3和和v4间无路，它们属于不同的连通分支。间无路，它们属于不同的连通分支。5)d（v1，v3）。）。对其他元素读者自己可以找出它的意义。对其他元素读者自己可以找出它的意义。,0)4(34)3(34)2(34)1(34aaaa7.3.2可达性矩阵可达性矩阵下面用矩阵来研究

45、有向图的可达性。下面用矩阵来研究有向图的可达性。与无向图一样，有向图也能用相应的邻接与无向图一样，有向图也能用相应的邻接矩阵矩阵A（aij）表示，其中）表示，其中但注意这里但注意这里A不一定是对称的。不一定是对称的。01ija否则Evvji,第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示 定义定义7.3.2 设设GV,E是一个有是一个有n个结点的有向图，个结点的有向图，则则n阶方阵阶方阵P（pij）称为图）称为图G的的可达性矩阵可达性矩阵。其中。其中10ijp(vi到到vj可达可达)(否则否则)根据可达性矩阵，可知图中任意两个结点之间是否根据可达性矩阵，可知图中任意两个结点之间是否至

46、少存在一条路以及是否存在回路。至少存在一条路以及是否存在回路。由由7.2节定理节定理7.2.1可知，利用有向图的邻接矩阵可知，利用有向图的邻接矩阵A，分以下两步可得到可达性矩阵。分以下两步可得到可达性矩阵。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示1)令令BnAA2An,2)将矩阵将矩阵n中不为零的元素均改为，为中不为零的元素均改为，为零的元素不变，所得的矩阵零的元素不变，所得的矩阵P就是可达就是可达性矩阵。性矩阵。当当n很大时，这种求可达性矩阵的方法就很很大时，这种求可达性矩阵的方法就很复杂。下面再介绍一种更简便的求可达复杂。下面再介绍一种更简便的求可达性矩阵的方法。性矩阵的方

47、法。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示因可达性矩阵是一个元素仅为或的矩因可达性矩阵是一个元素仅为或的矩阵（称为布尔矩阵），而在研究可达性阵（称为布尔矩阵），而在研究可达性问题时，我们对于两个结点间具有路的问题时，我们对于两个结点间具有路的数目并不感兴趣，所关心的只是两结点数目并不感兴趣，所关心的只是两结点间是否有路存在。因此，我们可将矩阵间是否有路存在。因此，我们可将矩阵A，A2,An,分别改为布尔矩阵分别改为布尔矩阵A(1)，A(2)，A(n)。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示由此有由此有A(2)A(1)A(1)AAA(3)A(2)A(1)A(n

48、)A(n-1)A(1)PA(1)A(2)A(n)相应的矩阵加法和乘法称为矩阵的布尔加相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘和布尔乘。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示图图7.3.3第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示【例例7.3.2】求出图求出图7.3.3所示图的可达性矩阵。所示图的可达性矩阵。解解:该图的邻接矩阵为该图的邻接矩阵为0100001011001110A第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示(2)(3)(4)(1)(2)(3)(4)0100010000100010001011001100110001101110111

49、01110110001 10011011 10111011 10111011 101 1 101 1 101 1 101 1 10AAAPAAAA故故 定理定理7.3.2 有向图有向图G是强连通的当且仅当是强连通的当且仅当其可达性矩阵其可达性矩阵P除主对角线外，其它元素除主对角线外，其它元素均为。均为。第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示小结：本节介绍了图的邻接矩阵、可达性矩小结：本节介绍了图的邻接矩阵、可达性矩阵的概念。阵的概念。重点重点:掌握邻接矩阵、可达性矩阵及由掌握邻接矩阵、可达性矩阵及由vi到到vj长长度为度为k的路径的条数的求法。的路径的条数的求法。作业作业:P

50、300(1),(3)第七章第七章 图论图论 7.3 图的矩阵表示图的矩阵表示7.4.1 欧拉图欧拉图7.4.2 汉密尔顿图汉密尔顿图第七章第七章 图论图论 7.4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图 7.4.1欧拉图欧拉图 历史上的哥尼斯堡七桥问题是著名的图历史上的哥尼斯堡七桥问题是著名的图论问题。论问题。问题是这样的：问题是这样的：18世纪的东普鲁士有个世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了岸和两个岛之间架设了7座桥，它们把河的座桥，它们把河的两岸和两个岛连接起来（如图两岸和两个岛连接起来（如图7.4.1）。）。第七章