离散数学及其应用第7章-图论课件.ppt

1、7.1 图的基本概念图的基本概念 7.1.1 图的基本概念图的基本概念 7.1.2 图的结点的度数及其计算图的结点的度数及其计算 7.1.3 子图和图的同构子图和图的同构 图图 7.1.1哥尼斯堡七桥问题 7.1 图的基本概念图的基本概念 图图 7.1.2 7.1 图的基本概念图的基本概念 7.1.1 图图 现实世界中许多现象能用某种图形表示现实世界中许多现象能用某种图形表示,这种图形这种图形是由一些点和一些连接两点间的连线所组成。是由一些点和一些连接两点间的连线所组成。【例【例7.1.1】a，b，c，d 4个篮球队进行友谊比赛。个篮球队进行友谊比赛。为了为了表示个队之间比赛的情况，表示个队之

2、间比赛的情况，我们作出图我们作出图 7.1.1的图形。的图形。在图中个小圆圈分别表示这个篮球队，在图中个小圆圈分别表示这个篮球队，称之为结点。称之为结点。如果两队进行过比赛，如果两队进行过比赛，则在表示该队的两个结点之间用则在表示该队的两个结点之间用一条线连接起来，一条线连接起来，称之为边。称之为边。这样利用一个图形这样利用一个图形使各队使各队之间的比赛情况一目了然。之间的比赛情况一目了然。1.图的定义图的定义 7.1 图的基本概念图的基本概念 图图 7.1.1如果图如果图 7.1.1中的个中的个结点结点a，b，c，d分别分别表示个人，表示个人，当某两当某两个人互相认识时，个人互相认识时，则则

3、将其对应点之间用边将其对应点之间用边连接起来。连接起来。这时的图这时的图又反映了这个人之又反映了这个人之间的认识关系。间的认识关系。7.1 图的基本概念图的基本概念 我们也可以点代表工厂我们也可以点代表工厂,以连接两点的连线表以连接两点的连线表示这两工厂间有业务往来关系。这样便可用图形示这两工厂间有业务往来关系。这样便可用图形表示某一城市中各工厂间的业务往来关系。这种表示某一城市中各工厂间的业务往来关系。这种用图形来表示事物之间的某种关系的方法我们也用图形来表示事物之间的某种关系的方法我们也曾经在第曾经在第 三三 章中使用过。章中使用过。对于这种图形对于这种图形,我们的我们的兴趣在于有多少个点

4、和哪些点对间有线连接兴趣在于有多少个点和哪些点对间有线连接,至于至于连线的长短曲直和点的位置都无关紧要。对它们连线的长短曲直和点的位置都无关紧要。对它们进行数学抽象我们就得到以下作为数学概念的图进行数学抽象我们就得到以下作为数学概念的图的定义。的定义。7.1 图的基本概念图的基本概念 定义定义7.1.1一个图一个图G是一个序偶是一个序偶V(G),E(G)，记记为为GV(G),E(G)。其中其中V(G)是非空结点集合，是非空结点集合，E(G)是边集合，是边集合，对对E(G)中的每条边，中的每条边，有有V(G)中的中的结点的有序偶或无序偶与之对应。结点的有序偶或无序偶与之对应。若边若边e所对应的结

5、点对是有序偶所对应的结点对是有序偶a,b,则称则称e是有向边。是有向边。a叫边叫边e的始点的始点,b叫边叫边e的终点的终点,统称为统称为e的的端点。若边端点。若边e所对应的结点对是无序偶所对应的结点对是无序偶(a,b),则称则称e是是无向边。这时统称无向边。这时统称e与两个结点与两个结点a和和b互相关联。互相关联。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=(

6、b,b)。则图则图G可用图可用图7.1.2(a)或或(b)表示。表示。我们将结点我们将结点a、b的无序结点对记为的无序结点对记为(a，b），），有有序结点对记为序结点对记为a，b。一个图一个图G可用一个图形来表示且表示是不唯可用一个图形来表示且表示是不唯一的。一的。7.1 图的基本概念图的基本概念 图图 7.1.2 7.1 图的基本概念图的基本概念 图 7.1.2 7.1 图的基本概念图的基本概念 2.图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点:同一条边的两个端点。同一条边的两个端点。孤立点孤立点:没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边:关联同一个结点的两条边

7、。关联同一个结点的两条边。孤立边孤立边:不与任何边相邻接的边。不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（自回路（环）：关联同一个结点的一条边（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是

8、邻接的。是邻接的。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)。在这个图中，在这个图中，e3是是关联同一个结点的一条边关联同一个结点的一条边,即即自回路；自回路；边边e4和和e5都与结点都与结点v2、v3关联，关联，即即它们是多重边。它们是多重边。7.1 图的基本概念图的基本概念 图图 7.1.3 7.1 图的基本概念图的基本概念 3.图图G的分类的分类(1)按按

9、G的结点个数和边数分为的结点个数和边数分为(n,m)图图,即即n个结点个结点,m条边的图条边的图;(2)特别地特别地,(n,0)称为称为零图零图,(1,0)图称为图称为平凡图平凡图。(2)按按G中关联于同一对结点的边数分为中关联于同一对结点的边数分为多重图和简多重图和简单图单图;多重图多重图:含有平行边的图（如含有平行边的图（如图图 7.1.3）。简单图简单图:不含平行边和自环的图。不含平行边和自环的图。7.1 图的基本概念图的基本概念 (3)按按G的边有序、无序分为的边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图;有向图：有向图：每条边都是有向边的图称为有向图每条边都是有向边的

10、图称为有向图 （图图 7.1.4(b)；无向图：无向图：每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；混合图：混合图：既有无向边既有无向边,又有有向边的图称为混合图。又有有向边的图称为混合图。本书主要研究无向图和有向图。本书主要研究无向图和有向图。(4)按按G的边旁有无数量特征分为的边旁有无数量特征分为边权图边权图(如图如图 7.1.4(a)、无权图无权图;7.1 图的基本概念图的基本概念 图图 7.1.4(5)按按G的任意两个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn(如图如图 7.1.5)和和不完全图不完全图(如图如图 7.1.6)。7.1 图的基本概

11、念图的基本概念 图图 7.1.6完全图完全图：任意两个不同的结点都邻接的简单图称为：任意两个不同的结点都邻接的简单图称为完完 全图。全图。n 个结点的无向完全图记为个结点的无向完全图记为Kn。图图7.1.5给出了给出了K3和和K4。从图中可以看出。从图中可以看出K3有有条边，条边，K4有条边。有条边。容易证明容易证明Kn有有 条边。条边。(1)2n n 图图 7.1.5 K3与与K4示意图示意图 7.1 图的基本概念图的基本概念 给定任意一个含有给定任意一个含有n个结点的图个结点的图G,总可以把它补成一个总可以把它补成一个具有同样结点的完全图具有同样结点的完全图,方法是把那些缺少的边添上。方法

12、是把那些缺少的边添上。定义定义7.1.2 设设GV,E是一个具有是一个具有n个结点的简单个结点的简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G的所有边后的所有边后得到的图（或由得到的图（或由G中所有结点和所有能使中所有结点和所有能使G成为成为完全图完全图的添加边组成的图）称为的添加边组成的图）称为G的补图，记为的补图，记为 。例如，零图和完全图互为补图。例如，零图和完全图互为补图。图图 7.1.6给出了一个图给出了一个图G和和G的补图的补图 。GG 7.1 图的基本概念图的基本概念 【例【例7.1.4】（拉姆齐问题）试证在任何一个有个人（拉姆齐问题）试证在任何一个

13、有个人的组里，的组里，存在个人互相认识，存在个人互相认识，或者存在个人互相或者存在个人互相不认识。不认识。我们用个结点来代表人，我们用个结点来代表人，并用邻接性来代表认并用邻接性来代表认识关系。识关系。这样一来，这样一来，该例就是要证明：该例就是要证明：任意一个有任意一个有个结点的图个结点的图G中，中，或者有个互相邻接的点，或者有个互相邻接的点，或者或者有个互相不邻接的点。有个互相不邻接的点。即，即，对任何一个有个结点对任何一个有个结点的图的图G，G或或 中含有一个三角形（即中含有一个三角形（即K3）。）。G 7.1 图的基本概念图的基本概念 证明证明:设设GV,E，|V|6，v是是G中一结点

14、。中一结点。因为因为v 与与G的其余个结点或者在的其余个结点或者在 中邻接，中邻接，或者在或者在G中邻接。中邻接。故不失一般性可假定，故不失一般性可假定，有个结点有个结点v1，v2，v3在在G中与中与v邻接。邻接。如果这个结点中有两个结点（如如果这个结点中有两个结点（如v1，v2）邻接，）邻接，则它们与则它们与v 就是就是G中一个三角形的个顶点。中一个三角形的个顶点。如果这如果这3个结点中任意两个在个结点中任意两个在G中均不邻接，中均不邻接，则则v1，v2，v3就就是是 中一个三角形的个顶点。中一个三角形的个顶点。GG 7.1 图的基本概念图的基本概念 7.1.2 图的结点的度数及其计算图的结

15、点的度数及其计算 我们常常需要关心图中有多少条边与某一结点我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念关联，这就引出了图的一个重要概念结点的度数。结点的度数。定义定义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中结点度数的总和等于边中结点度数的总和等于边数的两倍，数的两倍，即即证明证明:因为每条边都与两个结点关联，

16、因为每条边都与两个结点关联，所以加上一条所以加上一条边就使得各结点度数的和增加边就使得各结点度数的和增加 2，由此结论成立。由此结论成立。推论推论:图图G中度数为奇数的结点必为偶数个。中度数为奇数的结点必为偶数个。deg()2VE 7.1 图的基本概念图的基本概念 证明证明:设设V1和和V2分别是分别是G中奇数度数和偶数度数的中奇数度数和偶数度数的结点集。结点集。由定理由定理7.1.1知知 由于由于 是偶数之和，是偶数之和，必为偶数，必为偶数，而而2|E|也为偶数，也为偶数，故故 是偶数。是偶数。由此由此|V1|必为偶数。必为偶数。1deg()VEvvVvVv2)deg()deg(212)de

17、g(Vvv 7.1 图的基本概念图的基本概念 定义定义7.1.4 在有向图中在有向图中,射入结点射入结点v的边数称为结点的边数称为结点v 的入度，的入度，记为记为 ;由结点由结点v射出的边数称为结射出的边数称为结点点v 的出度，的出度，记为记为 。结点。结点v的入度与出度之的入度与出度之和就是结点和就是结点v的度数。的度数。如图如图7.1.4中中 1，2。)(deg v)(deg v)(deg a)(deg v 定理定理 7.1.2 在任何有向图在任何有向图GV,E中，中，有有EvvVvVv)(deg)(deg 7.1 图的基本概念图的基本概念 图图7.1.4 7.1 图的基本概念图的基本概念

18、 7.1.3 子图和图的同构子图和图的同构 1.子图子图 在研究和描述图的性质时，子图的概念占有在研究和描述图的性质时，子图的概念占有重要地位。重要地位。定义定义7.1.5 设有图设有图G=V,E和图和图 G=V,E 。1)若若VV，EE，则称则称G是是G的子图。的子图。2)若若G是是G的子图，且的子图，且EE，则称，则称G是是G 的真子图。的真子图。3)若若V=V，EE，则称，则称G是是G的生成子图。的生成子图。图图7.1.7给出了图给出了图G以及它的真子图以及它的真子图G1和生成子图和生成子图G2。图图7.1.7 图图G以及其真子图以及其真子图G 1和生成子图和生成子图G2 7.1 图的基

19、本概念图的基本概念 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 同构的图同

20、构的图 图图 7.1.9 7.1 图的基本概念图的基本概念 定义定义7.1.6 设有图设有图 G=V,E和图和图G=V,E。如果存在双射如果存在双射：VV，使得，使得 e=(u,v)E iff e=(u),(v)E，且且 (u，v)与与(u),(v)有相同的重数，则称有相同的重数，则称G与与G 同构。记作同构。记作G G。【例【例7.1.5】考察图考察图7.1.9中的两个图中的两个图GV,E和和 G=V,E。7.1 图的基本概念图的基本概念 显然，定义显然，定义：VV,(vi)v i,可以验证可以验证是满足定义是满足定义7.1.6的双射，所以的双射，所以G G。对于同构，形象地说，若图的结点可

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

22、性质以及生成子图的重点：图的结点的度数及其性质以及生成子图的 概念。概念。作业：作业：P231:4,5,7 7.1 图的基本概念图的基本概念 7.2 路与图的连通性路与图的连通性(Walks&The Connectivity of Graphs)7.2.1 路与回路路与回路(Wlaks and Circuits)7.2.2 图的连通性图的连通性(The Connectivity of Graphs)7.2.1 路与回路路与回路(Wlaks and Circuits)定义定义 7.2.1 给定图给定图GV,E,设设v0,v1,vkV，e1，e2，ekE，其中其中ei是关联于结点是关联于结点vi-

23、1和和vi的边，的边，称交替序列称交替序列v0e1v1e2ekvk为连接为连接v0到到vk的路，的路，v0和和vk分别分别称为路的起点与终点。路中边的数目称为路的起点与终点。路中边的数目k称作路的长度。称作路的长度。当当v0=vk时时,这条路称为回路。这条路称为回路。在简单图中一条路在简单图中一条路v0e1v1e2ekvk由它的结点序列由它的结点序列v0v1vk确定确定,所以简单图的路所以简单图的路,可表示为可表示为v0v1vk。如图。如图7.1.1表示的简单图中，表示的简单图中，路路ae1be4ce5d可写成可写成abcd。定义定义 7.2.2 设设=v0e1v1e2ekvk是图是图G中连接

24、中连接v0到到vk的的路。路。1)若若e1，e2，ek都不相同，都不相同，则称路则称路为迹；为迹；2)若若v0，v1，vk都不相都不相 同，则称路同，则称路为通路；为通路；3)长度大于的闭的通路长度大于的闭的通路（即除（即除v0vk外，外，其余结其余结 点均不相同的路）点均不相同的路）称作圈。称作圈。图图7.1.17.2.1 路与回路路与回路(Wlaks and Circuits)结点重复情况结点重复情况边重复情况边重复情况路路(Wlaks)允许允许 允许允许迹迹(Trails)允许允许不允许不允许 通路通路(Paths)不允许不允许 不允许不允许 回路回路(Circuits)允许允许允许允许

25、圈圈(cycle)不允许不允许（除始点（除始点和终点外）和终点外）不允许不允许 7.2.1 路与回路路与回路(Wlaks and Circuits)例如在图例如在图 7.2.1中，中，有连接有连接v5到到v3的路的路v5e8v4e5v2e6v5e7v3，这也是一条迹；路这也是一条迹；路 v1e1v2 e3v3是一条通路；是一条通路；路路v1e1v2e3v3e4v2e1v1是一是一 条回路，条回路，但不是圈；但不是圈；路路v1e1v2e3v3e2v1是一条是一条 回路，回路，也是圈。也是圈。图图 7.2.1 7.2.1 路与回路路与回路(Wlaks and Circuits)【例【例7.2.1】

26、（渡河问题）（渡河问题）一个摆渡人，一个摆渡人，要要把一只狼、把一只狼、一只羊和一捆干草运过河去，一只羊和一捆干草运过河去，河上有一只木船，河上有一只木船，每次除了人以外，每次除了人以外，只只能带一样东西。能带一样东西。另外，另外，如果人不在旁时，如果人不在旁时，狼就要吃羊，狼就要吃羊，羊就要吃干草。羊就要吃干草。问这人怎问这人怎样才能把它们运过河去？样才能把它们运过河去？下面我们利用通路的概念解决一个古老的下面我们利用通路的概念解决一个古老的著名问题。著名问题。7.2.1 路与回路路与回路(Wlaks and Circuits)解解:用用F表示摆渡人，表示摆渡人，W表示狼，表示狼，S表表示羊

27、，示羊，H表示干草。表示干草。若用若用FWSH表示人和其它样东西在表示人和其它样东西在河的左岸的状态。河的左岸的状态。这样在左岸全部可能这样在左岸全部可能出现的状态为以下出现的状态为以下16种：种：7.2.1 路与回路路与回路(Wlaks and Circuits)FWSH FWS FWH FSH WSH FW FS FH WS WH SH F W S H 这里这里表示左岸是空集，表示左岸是空集，即人、即人、狼、狼、羊、羊、干草都已运到右岸去了。干草都已运到右岸去了。7.2.1 路与回路路与回路(Wlaks and Circuits)根据题意检查一下就可以知道，根据题意检查一下就可以知道，这这

28、16种情况中有种情况是不允许出现的。种情况中有种情况是不允许出现的。它们是：它们是：WSH、FW、FH、WS、SH、F。如如FH表示人和干草在左岸，表示人和干草在左岸，而而狼和狼和羊在右岸，羊在右岸，这当然是不行的。这当然是不行的。因此，因此，允允许出现的情况只有许出现的情况只有10种。种。7.2.1 路与回路路与回路(Wlaks and Circuits)我们构造一个图，我们构造一个图，它的结点就是这它的结点就是这10种状态。种状态。若一种状态可以转移到另一若一种状态可以转移到另一种状态，种状态，就在表示它们的两结点间连一就在表示它们的两结点间连一条边，条边，这样就画出图这样就画出图7.2.

29、2。本题就转化本题就转化为找结点为找结点FWSH 到结点到结点的通路。的通路。从图从图中得到两条这样的通路，中得到两条这样的通路，即有两种渡河即有两种渡河方案。方案。7.2.1 路与回路路与回路(Wlaks and Circuits)图 7.2.27.2.1 路与回路路与回路(Wlaks and Circuits)定义定义 7.2.3 在图在图G中，中，若结点若结点vi到到vj有路连接有路连接（这时称（这时称vi和和vj是连通的），是连通的），其中长度最短的其中长度最短的路的长度称为路的长度称为vi到到vj 的距离，的距离，用符号用符号d(vi,vj)表表示。若从示。若从vi到到vj不存在路径

30、不存在路径,则则d(vi,vj)=。例如在图例如在图7.2.1中，中，（v1，v4）。）。7.2.1 路与回路路与回路(Wlaks and Circuits)注意注意:在有向图中在有向图中,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.1 7.2.1 路与回路路与回路(Wlaks and Circuits)定理定理 7.2.1 设设G是具有是具有n个结点的图，个结点的图，如如果从结点果从结点v1到另一结点到另一结点v2存

31、在一条路，存在一条路，则从则从结点结点v1到到v2必存在一条路长度不大于必存在一条路长度不大于n1的的通路。通路。7.2.1 路与回路路与回路(Wlaks and Circuits)证明证明:假定从假定从v1到到v2存在一条路径存在一条路径,(v1,vi,v2)是所是所经的结点经的结点,如果其中有相同的结点如果其中有相同的结点vk,例例 (v1,vi,vk,vk,v2),则删去从则删去从vk到到vk的这些边的这些边,它仍它仍是从是从v1到到v2的路径的路径,如此反复地进行直至如此反复地进行直至(v1,vi,v2)中中没有重复结点为止。此时没有重复结点为止。此时,所得的就是通路。通路的长所得的就

32、是通路。通路的长度比所经结点数少度比所经结点数少1,图中共图中共n个结点个结点,故通路长度不超故通路长度不超过过n-1。推论推论 设图设图GV,E，|V|n，则则G中任一圈长中任一圈长 度不大于度不大于n。7.2.1 路与回路路与回路(Wlaks and Circuits)1.无向图无向图的连通性的连通性 定义定义 7.2.4 在无向图如果一个图的任何两个结点在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否之间都有一条路，那么我们称这个图是连通的，否则是不连通的。则是不连通的。定义定义 7.2.5 图图G的一个连通的子图的一个连通的子图G（称为（称为 连通连通子图）

33、若不包含在子图）若不包含在G的任何更大的连通子图中，的任何更大的连通子图中，它它就被称作就被称作G的连通分支。的连通分支。我们把图我们把图G的连通分支数的连通分支数记作记作W（G）。）。7.2.2 图的连通性图的连通性(The Connectivity of Graphs)图图 7.2.3 图图G与与G 在图在图7.2.3中，中，G是不连通的，是不连通的，W（G），），而而G是是连通的，连通的，W（G）。）。任何一个图都可划分为若干个连通分支。任何一个图都可划分为若干个连通分支。显然，显然，仅当图仅当图G的连通分支数的连通分支数W（G）时，）时，图图G是连通的。是连通的。7.2.2 图的连通性

34、图的连通性(The Connectivity of Graphs)2.有向图有向图的连通性的连通性 定义定义7.2.6 在有向图中在有向图中,若从结点若从结点u到到v有一条有一条路，则称路，则称u可达可达v。定义定义7.2.7 设有有向图设有有向图G，1)若若G的任意两个结点中的任意两个结点中,至少从一个结点可至少从一个结点可达另一个结点达另一个结点,则称图则称图G是单向连通的是单向连通的;7.2.2 图的连通性图的连通性(The Connectivity of Graphs)2)如果如果G的任意两个结点都是相互可达的的任意两个结点都是相互可达的,则则称图称图G是强连通的是强连通的;3)如果略

35、去边的方向后，如果略去边的方向后，G成为连通的无向成为连通的无向图，则称图图，则称图G是弱连通的。是弱连通的。从定义可知：从定义可知：若图若图G是单向连通的，是单向连通的，则必是弱连通的；若图则必是弱连通的；若图G是强连通的，是强连通的，则则必是单向连通的，必是单向连通的，且也是弱连通的。且也是弱连通的。但反但反之不真。之不真。在图在图7.2.4中中,(a)是强连通的是强连通的,(b)是单向连通是单向连通的的,(c)是弱连通的。是弱连通的。图图 7.2.4 定理定理 7.2.2一个有向图一个有向图G是强连通的，是强连通的，当当且仅当且仅当G中有一个（有向）回路，中有一个（有向）回路，它至少它至

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

37、的。例如，例如，图图7.2.4(a)中有一回路中有一回路v1v3v2v1，它包含图，它包含图中所有结点。中所有结点。7.2.2 图的连通性图的连通性(The Connectivity of Graphs)定义定义 7.2.8 在有向图在有向图G=V,E中中,G是是G的子的子图图,若若G是强连通的是强连通的(单向连通的单向连通的,弱连通的弱连通的),没没有包含有包含G的更大子图的更大子图G是强连通的是强连通的(单向连通单向连通的的,弱连通的弱连通的),则称则称G是是G的强分图的强分图(单向分图单向分图,弱弱分图分图)。在图在图7.2.5中中,强分图集合是强分图集合是:1,2,3,e1,e2,e3

38、,4,5,6,7,8,e7,e87.2.2 图的连通性图的连通性(The Connectivity of Graphs)单向分图集合是单向分图集合是: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,e87.2.2 图的连通性图的连通性(The Connectivity of Graphs)图图 7.2.5 7.2.2 图的连通性图的连通性(The Connectivity of Graphs)小结小结:本结介绍了路、迹、通路、回路、圈本结介绍了路、迹、通路、回

39、路、圈及图的连通性。及图的连通性。作业：作业：P238:2,47.2 路与图的连通性路与图的连通性7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)7.3.1 邻接矩阵邻接矩阵(Adjacency Matrices)7.3.2 可达性矩阵可达性矩阵(Reachability Matrices)7.3.1邻接矩阵邻接矩阵(Adjacency Matrices)上面我们介绍了图的一种表示方法，上面我们介绍了图的一种表示方法，即即用图形表示图。用图形表示图。它的优点是形象直观，它的优点是形象直观，但是但是这种表示在结点与边的数目很多时是不方便的。这种表示在结点与边的

40、数目很多时是不方便的。下面我们提供另一种用矩阵表示图的方法。下面我们提供另一种用矩阵表示图的方法。利利用这种方法，用这种方法，我们能把图用矩阵存储在计算机我们能把图用矩阵存储在计算机中，中，利用矩阵的运算还可以了解到它的一些有利用矩阵的运算还可以了解到它的一些有关性质。关性质。定义定义 7.3.1 设设GV,E是有是有n个结点的简单图，个结点的简单图，则则n阶方阵（阶方阵（aij）称为）称为G的邻接矩阵。的邻接矩阵。其中其中1(,)0ijijEa 否则否则 如图如图7.3.1所示的图所示的图G，其邻接矩阵其邻接矩阵A为为7.3 图的矩阵表示图的矩阵表示(Matrix Notation of G

41、raph)如图如图7.3.1所示的图所示的图G，其邻接矩阵其邻接矩阵A为为0111110100110101010110010A 显然无向图的邻接矩阵必是对称的。显然无向图的邻接矩阵必是对称的。下面的定理说明，下面的定理说明，在邻接矩阵在邻接矩阵A的幂的幂A2，A3，等矩阵中，等矩阵中，每个元素有特定的含义。每个元素有特定的含义。图图7.3.1 G 7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)图图7.3.1 图图G 7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)定理定理 7.3.1 设设G是具有是具有n个结点个结点v1

42、,v2,vn 的图，的图，其邻接矩阵为其邻接矩阵为A，则则Ak（k1，2，）的（）的（i，j）项）项元素元素a(k)ij是从是从vi到到vj的长度等于的长度等于k的路的总数。的路的总数。证明证明:施归纳于施归纳于k。当当k1时，时，A1A，由由A的定义，的定义，定理显然成立。定理显然成立。若若kl时定理成立，时定理成立，则当则当kl1时，时，A l+1Al A，所以所以 rjnrlirlijaaa1)()1(7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)根据邻接矩阵定义根据邻接矩阵定义arj是联结是联结vr和和vj的长度为的长度为1的路数目的路数目,a(l

43、)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 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)由定理由定理7.3.1可得出以下结论：可得出以下结论：1)如果对如果对l1，2，n-1，Al的的（i，j）项元素（）项元素（

44、ij）都为零，）都为零，那么那么vi和和vj之间无任何路相连接，之间无任何路相连接，即即vi和和vj不连通。不连通。因此，因此，vi和和vj必属于必属于G的不同的连通分支。的不同的连通分支。7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)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 图的矩阵表示图的矩阵表

45、示(Matrix Notation of Graph)【例【例7.3.1】图图GV,E的图形如图的图形如图7.3.2，求邻接矩阵求邻接矩阵A和和A2，A3，A4，并分析其元并分析其元素的图论意义。素的图论意义。7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)解解:0100010000000100010100010A7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)图图 7.3.27.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)1)由由A中中a(1)121知，知，v1和和v2是邻接的；是邻接

46、的；由由A3中中a(3)122知，知，v1到到v2长度为长度为3的路有两条，的路有两条，从图从图中可看出是中可看出是v1v2v1v2和和v1v2v3v2。2)由由A2的主对角线上元素知，的主对角线上元素知，每个结点都每个结点都有长度为的回路，有长度为的回路，其中结点其中结点v2有两条：有两条：v2v1v2和和v2v3v2，其余结点只有一条。其余结点只有一条。3)由于由于A3的主对角线上元素全为零，的主对角线上元素全为零，所以所以G中没有长度为的回路。中没有长度为的回路。7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)4)由于由于 所以结点所以结点v3和和v4

47、间无路，间无路，它们属于不同的连通它们属于不同的连通分支。分支。5)d（v1，v3）。）。对其他元素读者自己可以找出它的意义。对其他元素读者自己可以找出它的意义。,0)4(34)3(34)2(34)1(34aaaa7.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)7.3.2可达性矩阵可达性矩阵(Reachability Matrices)下面用矩阵来研究有向图的可达性。下面用矩阵来研究有向图的可达性。与无向图一样，与无向图一样，有向图也能用相应的邻接有向图也能用相应的邻接矩阵矩阵 A（aij）表示，）表示，其中其中但注意这里但注意这里A不一定是对称的。不一定是

48、对称的。01ija否则Evvji,定义定义 7.3.2 设设GV,E是一个有是一个有n个结个结点的有向图，点的有向图，则则n阶方阵阶方阵（pij）称为）称为图图G的可达性矩阵。的可达性矩阵。其中其中10ijp(vi到到vj可达可达)(否则否则)7.3.2可达性矩阵可达性矩阵(Reachability Matrices)根据可达性矩阵，根据可达性矩阵，可知图中任意两个可知图中任意两个结点之间是否至少存在一条路以及是否存结点之间是否至少存在一条路以及是否存在回路。在回路。由由7.2节定理节定理7.2.1 可知，可知，利用有向图利用有向图的邻接矩阵的邻接矩阵A，分以下两步可得到可达性分以下两步可得到

49、可达性矩阵。矩阵。7.3.2可达性矩阵可达性矩阵(Reachability Matrices)1)令令BnAA2An,2)将矩阵将矩阵n中不为零的元素均改为，中不为零的元素均改为，为零的元素不变，为零的元素不变，所得的矩阵所得的矩阵P就是可达性矩就是可达性矩阵。阵。当当n很大时，很大时，这种求可达性矩阵的方法就这种求可达性矩阵的方法就很复杂。很复杂。下面再介绍一种更简便的求可达性矩下面再介绍一种更简便的求可达性矩阵的方法。阵的方法。7.3.2可达性矩阵可达性矩阵(Reachability Matrices)因可达性矩阵是一个元素仅为或的矩因可达性矩阵是一个元素仅为或的矩阵（称为布尔矩阵），阵（

50、称为布尔矩阵），而在研究可达性问题时，而在研究可达性问题时，我们对于两个结点间具有路的数目并不感兴趣，我们对于两个结点间具有路的数目并不感兴趣，所关心的只是两结点间是否有路存在。所关心的只是两结点间是否有路存在。因此，因此，我们可将矩阵我们可将矩阵A，A2,An,分别改为布尔矩阵分别改为布尔矩阵A(1)，A(2)，A(n)。7.3.2可达性矩阵可达性矩阵(Reachability Matrices)由此有由此有 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)相应的矩阵加法和乘法称为矩阵的布尔相应的矩阵加法和乘法称为矩阵的布尔加加和布