《离散数学-图论PPT参考课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-图论PPT参考课件.ppt（237页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1010章章 图论图论(Graph Theory)第十章第十章 图论图论(Graph Theory)10.1 图的基本概念图的基本概念(Graph)10.2 路与图的连通性路与图的连通性(Walks&Connectivity of Graphs)10.3 图的矩阵表示图的矩阵表示(Matrix Notation of Graph)10.4 最短链与关键路最短链与关键路（Minimal path）10.5 欧拉图与哈密尔顿图欧拉图与哈密尔顿图(Eulerian Graph&Hamilton-ian Graph)10.6 平面图平面图(Planar Graph)10.7树树与生成树与生成树(T
2、rees and Spanning Trees)10.8 二部图（二部图（bipartite graph）第第1010章章 图论图论(Graph Theory)10.1 图的基本概念图的基本概念 10.1.1 图的基本概念图的基本概念 10.1.2 图的结点的度数及其计算图的结点的度数及其计算 10.1.3 子图和图的同构子图和图的同构第第1010章章 图论图论(Graph Theory)图图 10.1.1哥尼斯堡七桥问题 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)10.1.1 图图 现现实实世世界界中中许许多多现现象象能能用用某某种种图图形形表
3、表示示,这这种种图图形形是由一些点和一些连接两点间的连线所组成。是由一些点和一些连接两点间的连线所组成。【例例10.1.1】a，b，c，d 4个个篮篮球球队队进进行行友友谊谊比比赛赛。为为了了表表示示个个队队之之间间比比赛赛的的情情况况，我我们们作作出出图图10.1.1的的图图形形。在在图图中中个个小小圆圆圈圈分分别别表表示示这这个个篮篮球球队队，称称之之为为结结点点。如如果果两两队队进进行行过过比比赛赛，则则在在表表示示该该队队的的两两个个结结点点之之间间用用一一条条线线连连接接起起来来，称称之之为为边边。这这样样利利用用一一个个图图形形使使各各队队之之间间的比赛情况一目了然。的比赛情况一目
4、了然。1.图的定义图的定义 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)图图 10.1.1如果图如果图 10.1.1中的个中的个结点结点a，b，c，d分别分别表示个人，当某两个表示个人，当某两个人互相认识时，人互相认识时，则将则将其对应点之间用边连接其对应点之间用边连接起来。起来。这时的图又反这时的图又反映了这个人之间的认映了这个人之间的认识关系。识关系。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)定定义义10.1.1一一个个图图G是是一一个个序序偶偶V(G),E(G)，记记为为GV(G),E(G)。其
5、其中中V(G)是是非非空空结结点点集集合合，E(G)是是边边集集合合，对对E(G)中中的的每每条条边边，有有V(G)中中的的结点的有序偶或无序偶与之对应。结点的有序偶或无序偶与之对应。若若边边e所所对对应应的的结结点点对对是是有有序序偶偶a,b,则则称称e是是有有向向边边。a叫叫边边e的的始始点点,b叫叫边边e的的终终点点,统统称称为为e的的端端点点。若若边边e所所对对应应的的结结点点对对是是无无序序偶偶(a,b),则则称称e是是无无向边。这时统称向边。这时统称e与两个结点与两个结点a和和b互相关联。互相关联。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theo
6、ry)【例例10.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可用图可用图10.1.2(a)或或(b)表示。表示。我们将结点我们将结点a、b的无序结点对记为的无序结点对记为(a，b），），有序有序结点对记为结点对记为a，b。一个图一个图G可用一个图形来表示且表示是不唯一的。可用一个图形来表示且表示是不唯一的。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph
7、 Theory)图图 10.1.2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)图 10.1.2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)2.图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点:同一条边的两个端点。同一条边的两个端点。孤立点孤立点:没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边:关联同一个结点的两条边。关联同一个结点的两条边。孤立边孤立边:不与任何边相邻接的边。不与任何边相邻接的边。自自回回路路（环环）：关关联联同同一一个个结结点点的的一一条条边边（v，v）或）或v
8、，v）。）。平行边平行边(多重边多重边):关联同一对结点的多条边。关联同一对结点的多条边。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)如如例例10.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是邻接的。是邻接的。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)【例例10.1.3】设图设图GV,
9、E 如图如图10.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关关联联，即即它它们们是平行边。是平行边。10.1 图的基本概念图的基本概念 图图 10.1.3第第1010章章 图论图论(Graph Theory)3.图图G的分类的分类(1)按按G的的结结点点个个数数和和边边数数分分为为(n,m)图图,即即n个个
10、结结点点,m条边的图条边的图;特别地特别地,(n,0)称为称为零图零图,(1,0)图称为图称为平凡图平凡图。(2)按按G中中关关联联于于同同一一对对结结点点的的边边数数分分为为多多重重图图和和简简单图单图;多重图多重图:含有平行边的图（如图含有平行边的图（如图 10.1.3）；线线 图图:非多重图称为线图；非多重图称为线图；简单图简单图:不含平行边和自环的图。不含平行边和自环的图。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)G1、G2是多重图是多重图G3是线图是线图G4是简单图是简单图第第1010章章 图论图论(Graph Theory)(3)按按
11、G的边有序、无序分为的边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图;有向图：有向图：每条边都是有向边的图称为有向图每条边都是有向边的图称为有向图 （图（图 10.1.4(b)；无向图：无向图：每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；混合图：混合图：既有无向边既有无向边,又有有向边的图称为混合图。又有有向边的图称为混合图。(4)按按G的的边边旁旁有有无无数数量量特特征征分分为为加加权权图图、无无权权图图(如如图图 10.1.4);10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)图图 10.1.4(5)按按G的任意两
12、个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn(如图如图 10.1.5)和和不完全图不完全图(如图如图 10.1.6)。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)完完全全图图：任任意意两两个个不不同同的的结结点点都都邻邻接接的的简简单单图图称称为为完完全图。全图。n 个结点的无向完全图记为个结点的无向完全图记为Kn。图图10.1.5给给出出了了K3和和K4。从从图图中中可可以以看看出出K3有有条边，条边，K4有条边。有条边。容易证明容易证明Kn有有 条边。条边。10.1 图的基本概念图的基本概念 图图 10.1.6图图 10.1
13、.5 K3与与K4示意图示意图第第1010章章 图论图论(Graph Theory)例例213213有向完全图有向完全图无向完全图无向完全图第第1010章章 图论图论(Graph Theory)给定任意一个含有给定任意一个含有n个结点的图个结点的图G,总可以把它补成一个总可以把它补成一个具有同样结点的完全图具有同样结点的完全图,方法是把那些缺少的边添上。方法是把那些缺少的边添上。定义定义10.1.2 设设GV,E是一个具有是一个具有n个结点的简单个结点的简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G的所有边后的所有边后得到的图（或由得到的图（或由G中所有结点和所有
14、能使中所有结点和所有能使G成为完全图成为完全图的添加边组成的图）称为的添加边组成的图）称为G的的补图补图，记为，记为 。例如，零图和完全图互为补图。例如，零图和完全图互为补图。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)G相对于相对于Kn的补图是下图中的的补图是下图中的第第1010章章 图论图论(Graph Theory)第第1010章章 图论图论(Graph Theory)互为补图互为补图互为补图互为补图互为补图互为补图第第1010章章 图论图论(Graph Theory)【例例10.1.4】（拉拉姆姆齐齐问问题题）试试证证在在任任何何一一个个有
15、有个个人人的的组组里里，存存在在个个人人互互相相认认识识，或或者者存存在在个个人人互互相不认识。相不认识。我我们们用用个个结结点点来来代代表表人人，并并用用邻邻接接性性来来代代表表认认识识关关系系。这这样样一一来来，该该例例就就是是要要证证明明：任任意意一一个个有有个个结结点点的的图图G中中，或或者者有有个个互互相相邻邻接接的的点点，或或者者有有个个互互相相不不邻邻接接的的点点。即即，对对任任何何一一个个有有个个结结点点的的图图G，G或或 中含有一个三角形（即中含有一个三角形（即K3）。）。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)证证明明:设设
16、GV,E，|V|6，v是是G中中一一结结点点。因因为为v 与与G的的其其余余个个结结点点或或者者在在 中中邻邻接接，或或者者在在G中中邻邻接接。故故不不失失一一般般性性可可假假定定，有有个个结结点点v1，v2，v3在在G中与中与v邻接。邻接。如如果果这这个个结结点点中中有有两两个个结结点点（如如v1，v2）邻邻接接，则则它它们们与与v 就就是是G中中一一个个三三角角形形的的个个顶顶点点。如如果果这这3个个结结点点中中任任意意两两个个在在G中中均均不不邻邻接接，则则v1，v2，v3就就是是 中一个三角形的个顶点。中一个三角形的个顶点。10.1 图的基本概念图的基本概念 第第1010章章 图论图论
17、(Graph Theory)10.1.2 图的结点的度数及其计算图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念关联，这就引出了图的一个重要概念结点的度数结点的度数。10.1 图的基本概念图的基本概念 定定义义:在在有有向向图图中中,以以v为为终终点点的的边边数数称称为为结结点点v 的的入入度度，记记为为 ;以以v为为始始点点的的边边数数称称为为结结点点v 的的出出度度，记记为为 。结结点点v的的入入度度与与出出度度之之和和称称为为结结点点v的度数，记为的度数，记为 d(v)或或deg(v)。第第1010章
18、章 图论图论(Graph Theory)定义定义:在无向图中，图中结点在无向图中，图中结点v所关联的边数所关联的边数(有环时计算两次有环时计算两次)称为结点称为结点v 的度数，记为的度数，记为d(v)或或deg(v)。第第1010章章 图论图论(Graph Theory)例例245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0例例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：4第第1010章章 图论图论(Graph Theory)定定理理 10.1.1 无无向向图图GV,E中中结结点点度度数数的的总总和和等等于边数的两倍，于边数的两
19、倍，即即证明证明:因为每条边都与两个结点关联，因为每条边都与两个结点关联，所以加上一条所以加上一条边就使得各结点度数的和增加边就使得各结点度数的和增加 2，由此结论成立。由此结论成立。定义定义：无向图中，如果每个结点的度都是：无向图中，如果每个结点的度都是k,则称为则称为k-度正则图。度正则图。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)推论推论:无向图无向图G中度数为奇数的结点必为偶数个。中度数为奇数的结点必为偶数个。证证明明:设设V1和和V2分分别别是是G中中奇奇数数度度数数和和偶偶数数度度数数的的结结点集。点集。由定理由定理10.1.1知知
20、由于由于 是偶数之和，是偶数之和，必为偶数，必为偶数，而而2|E|也为偶数，也为偶数，故故 是偶数。是偶数。由此由此|V1|必为偶数。必为偶数。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)定理定理 10.1.2 在任何有向图在任何有向图GV,E中，中，有有图图10.1.4第第1010章章 图论图论(Graph Theory)10.1.3 子图和图的同构子图和图的同构 1.子图子图 在在研研究究和和描描述述图图的的性性质质时时，子子图图的的概概念念占占有有重要地位。重要地位。定义定义10.1.5 设有图设有图G=V,E和图和图 G=V,E 。1)若若
21、VV，EE，则称则称G是是G的的子图子图。2)若若G是是G的子图，且的子图，且EE，则称，则称G是是G 的的真子图真子图。第第1010章章 图论图论(Graph Theory)356例例245136图与子图图与子图第第1010章章 图论图论(Graph Theory)3)若若V=V，EE，则称，则称G是是G的的生成子图生成子图。图图10.1.7给出了图给出了图G以及它的真子图以及它的真子图G1和生成子图和生成子图G2。图图10.1.7 图图G以及其真子图以及其真子图G 1和生成子图和生成子图G2 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)例例 画
22、出画出K4的所有非同构的生成子图。的所有非同构的生成子图。第第1010章章 图论图论(Graph Theory)第第1010章章 图论图论(Graph Theory)2.图的同构图的同构 10.1 图的基本概念图的基本概念 试观察下面各图有何异同？试观察下面各图有何异同？第第1010章章 图论图论(Graph Theory)图图 10.1.8 同构的图同构的图 图图 10.1.9 10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)定义定义10.1.6 设有图设有图 G=V,E和图和图G=V,E。如果存在双射如果存在双射：VV，使得，使得 e=(u,v)E
23、 iff e=(u),(v)E，且且 (u，v)与与(u),(v)有相同的重数，则称有相同的重数，则称G与与G 同构。记作同构。记作G G。注注：由由同同构构的的定定义义可可知知，不不仅仅结结点点之之间间要要具具有有一一一一对对应应关关系系，而而且且要要求求这这种种对对应应关关系系保保持持结结点点间间的的邻邻接接关关系系。对对于于有有向向图图的的同同构构还还要要求求保保持持边边的的方向。方向。10.1 图的基本概念图的基本概念 第第1010章章 图论图论(Graph Theory)【例例10.1.5】考考察察图图10.1.9中中的的两两个个图图GV,E和和 G=V,E。显显然然，定定义义：VV
24、,(vi)v i,可可以以验验证证是是满足定义满足定义10.1.6的双射，所以的双射，所以G G。10.1 图的基本概念图的基本概念 图图 10.1.9第第1010章章 图论图论(Graph Theory)一一般般说说来来，证证明明两两个个图图是是同同构构的的并并非非是是轻轻而而易易举举的的事事情情，往往往往需需要要花花些些气气力力。请请读者证明下图中两个图是同构的。读者证明下图中两个图是同构的。第第1010章章 图论图论(Graph Theory)第第1010章章 图论图论(Graph Theory)根据图的同构定义，可以给出图同构的必要条件根据图的同构定义，可以给出图同构的必要条件如下：如
25、下：(1)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同的结点数目相等。度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。第第1010章章 图论图论(Graph Theory)下图中的下图中的(a)和和(b)满足上述三个条件，然而并不同满足上述三个条件，然而并不同构。构。因为在因为在(a)中度数为中度数为3的结点的结点x与两个度数为与两个度数为1的结点的结点邻接，而邻接，而(b)中度数为中度数为3的结点的结点y仅与一个度数为仅与一个度数为1的的结点邻接。结点邻接。寻找一种简单有效的方法来判定图的同构，至今寻找一种简单有效的方法来判
26、定图的同构，至今仍是图论中悬而未决的重要课题。仍是图论中悬而未决的重要课题。第第1010章章 图论图论(Graph Theory)第第1010章章 图论图论(Graph Theory)对对于于同同构构，形形象象地地说说，若若图图的的结结点点可可以以任任意意挪挪动动位位置置，而而边边是是完完全全弹弹性性的的，只只要要在在不不拉拉断断的的条条件件下下，这这个个图图可可以以变变形形为为另另一一个个图图，那那么么这这两两个个图图是是同同构构的的。故故同同构构的的两两个个图图从从外外形形上上看看可能不一样，但它们的可能不一样，但它们的拓扑结构拓扑结构是一样的。是一样的。第第1010章章 图论图论(Gra
27、ph Theory)10.2 路与图的连通性路与图的连通性(Walks&The Connectivity of Graphs)10.2.1 路与回路路与回路(Walks and Circuits)10.2.2 图图的的连连通通性性(The Connectivity of Graphs)第第1010章章 图论图论(Graph Theory)10.2.1 路与回路路与回路(Wlaks and Circuits)定义定义 10.2.1 给定图给定图GV,E,设设v0,v1,vkV，e1，e2，ekE，其其中中ei是是关关联联于于结结点点vi-1和和vi的的边边，称称交交替替序序列列v0e1v1e2e
28、kvk为为连连接接v0到到vk的的路路，v0和和vk分分别别称为路的起点与终点。路中边的数目称为路的起点与终点。路中边的数目k称作路的长度。称作路的长度。当当v0=vk时时,这条路称为回路。这条路称为回路。在在简单图简单图中一条路中一条路v0e1v1e2ekvk由它的结点序列由它的结点序列v0v1vk确定确定,所以简单图的路所以简单图的路,可表示为可表示为v0v1vk。如图。如图10.1.1表示的简单图中，表示的简单图中，路路ae1be4ce5d可写成可写成abcd。第第1010章章 图论图论(Graph Theory)定定义义 10.2.2 设设=v0e1v1e2ekvk是是图图G中中连连接
29、接v0到到vk的的路。路。1)若若e1，e2，ek都都不不相相同同，则则称称路路为为简简单单路路或迹；或迹；2)若若v0，v1，vk都都不不相相同同，则则称称路路为为基基本本路路或或通路；通路；3)圈圈中中若若出出现现的的每每条条边边恰恰好好一一次次，称称简简单单圈圈。若若出出现的每个结点恰好一次，称基本圈。现的每个结点恰好一次，称基本圈。10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)结点重复情况结点重复情况边重复情况边重复情况路路 允许允许 允许允许简单路简单路 允许允许不允许不允许 基本路基本路 不允许不允许 不
30、允许不允许 回路回路允许允许允许允许简单圈简单圈允许允许不允许不允许基本圈基本圈不允许不允许不允许不允许10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)注意：不同的教材定义不同！注意：不同的教材定义不同！途径途径(walk)：图：图G中一个点边交替出现的序列。中一个点边交替出现的序列。迹迹(trail)：边不重的途径。：边不重的途径。路路(path):顶点不重复的迹。顶点不重复的迹。闭途径（闭途径（closed walk）：起点和终点相同的途径。）：起点和终点相同的途径。闭迹闭迹(closed trail)：起点和终点
31、相同的迹，也称为回：起点和终点相同的迹，也称为回路（路（circuit）。）。圈圈(cycle):起点和终点相同的路。起点和终点相同的路。10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)例例157324G26例例245136G1路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，
32、5，2，1简单回路：简单回路：1，2，3，1第第1010章章 图论图论(Graph Theory)例如在图例如在图 10.2.1中，中，有连接有连接v5到到v3的路的路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路这也是一条简单路；路 v1e1v2 e3v3是一条基本路；是一条基本路；路路v1e1v2e3v3e4v2e1v1是一是一 条回路，条回路，但不是基本圈；但不是基本圈；路路v1e1v2e3v3e2v1是一条是一条 回路，回路，也是圈。也是圈。图图 10.2.1 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Th
33、eory)定义定义 10.2.3 在图在图G中，中，若结点若结点vi到到vj有路连接有路连接（这时称（这时称vi和和vj是可达的），是可达的），其中长度最短的其中长度最短的路的长度称为路的长度称为vi到到vj 的距离，的距离，用符号用符号d(vi,vj)表表示。若从示。若从vi到到vj不存在路径不存在路径,则则d(vi,vj)=。例如在图例如在图10.2.1中，中，（v1，v4）。）。10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)注意注意:在有向图中在有向图中,d(vi,vj)不一定等于不一定等于d(vj,vi),但
34、一般地满足以下性质但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi,vi)=0;(3)d(vi,vj)+d(vj,vk)d(vi,vk)。图图 10.2.1 10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)定定理理 10.2.1 设设G是是具具有有n个个结结点点的的图图，如如果果从从结结点点v1到到另另一一结结点点v2存存在在一一条条路路，则则从从结结点点v1到到v2必必存存在在一一条条长长度度不不大大于于n1的的基本路（通路）。基本路（通路）。10.2.1 路与回路路与回路(Wlaks and Circ
35、uits)第第1010章章 图论图论(Graph Theory)证证明明:假假定定从从v1到到v2存存在在一一条条路路径径,(v1,vi,v2)是是所所经的结点经的结点,如果其中有相同的结点如果其中有相同的结点vk,例例 (v1,vi,vk,vk,v2),则删去从则删去从vk到到vk的这些边的这些边,它它仍是从仍是从v1到到v2的路径的路径,如此反复地进行直至如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时中没有重复结点为止。此时,所得的就是所得的就是通路。通路的长度比所经结点数少通路。通路的长度比所经结点数少1,图中共图中共n个结点个结点,故通路长度不超过故通路长度不超过n-1
36、。推推论论 设设图图GV,E，|V|n，则则G中中任任一一基基本本圈长度不大于圈长度不大于n。10.2.1 路与回路路与回路(Wlaks and Circuits)第第1010章章 图论图论(Graph Theory)1.无向图的连通性无向图的连通性 定定义义 10.2.4 在在无无向向图图如如果果一一个个图图的的任任何何两两个个结结点点之之间间都都有有一一条条路路，那那么么我我们们称称这这个个图图是是连连通通的的，否否则是不连通的。则是不连通的。定定义义 10.2.5 图图G的的一一个个连连通通的的子子图图G（称称为为 连连通通子子图图）若若不不包包含含在在G的的任任何何更更大大的的连连通通
37、子子图图中中，它它就就被被称称作作G的的连连通通分分支支。我我们们把把图图G的的连连通通分分支支个个数记作数记作（G）。）。10.2.2 图图 的的 连连 通通 性性(The Connectivity of Graphs)第第1010章章 图论图论(Graph Theory)图图 10.2.3 图图G与与G 在图在图10.2.3中，中，G是不连通的，是不连通的，（G），），而而G是是连通的，连通的，（G）。）。任何一个图都可划分为若干个连通分支。任何一个图都可划分为若干个连通分支。显然，显然，仅当图仅当图G的连通分支数的连通分支数（G）时，）时，图图G是连通的。是连通的。10.2.2 图的连通
38、性图的连通性第第1010章章 图论图论(Graph Theory)在在图图的的研研究究中中，常常常常需需要要考考虑虑删删去去与与增增加加结结点点、结结点点集集、边边和和边边集集（或或弧弧集集）的的问问题题。所所谓谓从从图图G=中中删删去去结结点点集集S，是是指指作作V-S以以及及从从E中中删删去去与与S中中的的全全部部结结点点相相联联结结的的边边而而得得到到的的子子图图，记记作作G-S；特特别别当当S=v时时，简简记记为为G-v；所所谓谓从从图图G=中中删删去去边边集集（或或弧弧集集）T，是是指指作作E-T，且且T中中的的全全部部边边所所关关联联的的结结点点仍仍在在V中中而而得得到到的的子子图
39、图，记记为为G-T；特特别别当当T=e 时，简记作时，简记作G-e。第第1010章章 图论图论(Graph Theory)所谓图所谓图G=增加结点集增加结点集S，是指作，是指作VS以以及向及向E中并入中并入S中、中、S与与V中所成的边而得到的中所成的边而得到的图，记作图，记作G+S；特别当；特别当S=v 时，简记为时，简记为G+v；图图G=增加边集（或弧集）增加边集（或弧集）T是指作是指作ET所得到的图，记作所得到的图，记作G+T，这里，这里T中全部边（或中全部边（或弧）的关联结点属于弧）的关联结点属于V。第第1010章章 图论图论(Graph Theory)定义定义:给定连通无向图给定连通无
40、向图G=，S V。若。若(G-S)(G)，但，但 T S有有(G-T)=(G)，则称，则称S是是G的一个分离结点集。若图的一个分离结点集。若图G的分离结点集的分离结点集S=v ，则称，则称v是是G的的割点割点。类似地可定义图类似地可定义图G的分离边集的分离边集T；若图；若图G的分离的分离边集边集T=e ，则称，则称e是是G的的割边或桥割边或桥。第第1010章章 图论图论(Graph Theory)对对于于连连通通的的非非平平凡凡图图G，称称(G)=|S|S是是G的的分分离离结结点点集集 为为图图G的的结结点点连连通通度度，它它表表明明产产生生不不连连通通图图而而需需要要删删去去结结点点的的最最
41、少少数数目目。于于是是，对对于于分分离离图图G，(G)=0；对对于于存存在在割割点点的的连连通通图图G，(G)=1。第第1010章章 图论图论(Graph Theory)类似地定义边连通度类似地定义边连通度(G)=|T|T是是G的分离边的分离边集集，它，它表明产生不连通图而需要删去边的最少表明产生不连通图而需要删去边的最少数目数目。可见，对于分离图。可见，对于分离图G，(G)=0；对于平凡；对于平凡图图G，(G)=0；对于图；对于图K1，(K1)=0；对于存在割；对于存在割边的连通图边的连通图G，(G)=1；对于完全图；对于完全图Kn，(Kn)=n-1。第第1010章章 图论图论(Graph
42、Theory)下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到的关年得到的关于结点连通度、边连通度和最小度的不等式联系于结点连通度、边连通度和最小度的不等式联系的定理：的定理：定理定理:对于任何一个无向图对于任何一个无向图G，有，有 (G)(G)(G)。定定理理:一一个个连连通通无无向向图图G中中的的结结点点v是是割割点点存存在在两两个结点个结点u和和w，使得联结，使得联结u和和w的每条链都经过的每条链都经过v。第第1010章章 图论图论(Graph Theory)定定理理:一一个个连连通通无无向向图图G中中的的边边e是是割割边边 存存在在两两个个结点结点u和和w，使得联结
43、，使得联结u与与w的每条链都经过的每条链都经过e。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。定定理理:连连通通无无向向图图G中中的的一一条条边边e是是割割边边e不不包包含含在图的任何基本圈中。在图的任何基本圈中。第第1010章章 图论图论(Graph Theory)2.有向图的连通性有向图的连通性 定定义义10.2.6 在在有有向向图图中中,若若从从结结点点u到到v有有一一条路，则称条路，则称u可达可达v。定义定义10.2.7 设有有向图设有有向图G，1)若若G的的任任意意两两个个结结点点中中,至至少少从从一一个个结结点点可可达另一个结点达另一个结点,
44、则称图则称图G是单向连通的是单向连通的;10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory)2)如如果果G的的任任意意两两个个结结点点都都是是相相互互可可达达的的,则则称称图图G是是强连通的强连通的;3)如如果果略略去去边边的的方方向向后后，G成成为为连连通通的的无无向向图图，则则称图称图G是弱连通的。是弱连通的。从从定定义义可可知知：若若图图G是是单单向向连连通通的的，则则必必是是弱弱连连通通的的；若若图图G是是强强连连通通的的，则则必必是是单单向向连连通通的的，且且也也是是弱弱连连通通的的。但但反反之不真。之不真。第第1010章章 图论图论(Graph
45、Theory)定定理理 10.2.2一一个个有有向向图图G是是强强连连通通的的，当当且且仅仅当当G中中有有一一个个（有有向向）回回路路，它它至至少少包含每个结点一次。包含每个结点一次。第第1010章章 图论图论(Graph Theory)证证明明:必必要要性性：如如果果有有向向图图G是是强强连连通通的的，则则任任意意两两个个结结点点都都是是相相互互可可达达的的。故故必必可可作作一一回回路路经经过过图图中中所所有有各各结结点点。否否则则必必有有一一回回路路不不包包含含某某一一结结点点v。这这样样，v与与回回路路上上各各结结点点就就不不能能相相互互可可达达，这与这与G是强连通矛盾。是强连通矛盾。充
46、充分分性性：如如果果G中中有有一一个个回回路路，它它至至少少包包含含每每个个结结点点一一次次，则则G中中任任意意两两个个结结点点是是相相互互可可达达的的，故故G是强连通的。是强连通的。10.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory)定义定义 10.2.8 在有向图在有向图G=V,E中中,G是是G的子的子图图,若若G是强连通的是强连通的(单向连通的单向连通的,弱连通的弱连通的),没没有包含有包含G的更大子图的更大子图G是强连通的是强连通的(单向连通单向连通的的,弱连通的弱连通的),则称则称G是是G的强分图的强分图(单向分图单向分图,弱弱分图分图)。10.2
47、.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory)连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分图连通分图例例245136第第1010章章 图论图论(Graph Theory)图图 10.2.5 10.2.2 图图 的的 连连 通通 性性(The Connectivity of Graphs)第第1010章章 图论图论(Graph Theory)在图在图10.2.5中中,强分图集合是强分图集合是:1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8单向分图集合是单向分图集合是:1,2,3,4,5,e1,e2,e3,e4,e5,
48、6,5,e6,7,8,e7,e8 弱分图集合是弱分图集合是:1,2,3,4,5,6,e1,e2,e3,e4,e5,e6,7,8,e7,e810.2.2 图的连通性图的连通性第第1010章章 图论图论(Graph Theory)下面给出简单有向图的一个应用下面给出简单有向图的一个应用资源分配图。资源分配图。在多道程序的计算机系统中，可以同时执行多个在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、如磁带机、磁盘设备、CPU、主存贮器和编译程、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。
49、序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。操作系统必须保证这一请求得到满足。第第1010章章 图论图论(Graph Theory)对资源的请求可能发生冲突。如程序对资源的请求可能发生冲突。如程序A控制着资控制着资源源r1，请求资源，请求资源r2；但程序；但程序B控制着资源控制着资源r2，请求，请求资源资源r1。这种情况称为处于死锁状态。然而冲突。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死的请求必须解决，资源分配图有助发现和纠正死锁。锁。假设某
50、一程序对一些资源的请求，在该程序运行假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。源，但对不可利用的资源则必须等待。第第1010章章 图论图论(Graph Theory)令令Pt=p1，p2，pm 表示计算机系统在时刻表示计算机系统在时刻t的的程序集合，程序集合，Qt Pt是运行的程序集合，或者说在时是运行的程序集合，或者说在时刻刻t至少分配一部分所请求的资源的程序集合。至少分配一部分所请求的资源的