离散数学-图论名师优质课获奖市赛课一等奖课件.ppt

第十章第十章图论图论(GraphTheory)10.1图基本概念图基本概念(Graph)10.2路与图连通性路与图连通性(Walks&ConnectivityofGraphs)10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)10.4最短链与关键路最短链与关键路（Minimalpath）10.5欧拉图与哈密尔顿图欧拉图与哈密尔顿图(EulerianGraph&Hamilton-ianGraph)10.6平面图平面图(PlanarGraph)10.7树树与生成树与生成树(TreesandSpanningTrees)10.8二部图（二部图（bipartitegraph）第1页10.1图基本概念图基本概念10.1.1图基本概念图基本概念10.1.2图结点度数及其计算图结点度数及其计算10.1.3子图和图同构子图和图同构第2页图图10.1.1哥尼斯堡七桥问题10.1图基本概念图基本概念第3页10.1.1图图现现实实世世界界中中许许多多现现象象能能用用某某种种图图形形表表示示,这这种种图图形形是由一些点和一些连接两点间连线所组成。是由一些点和一些连接两点间连线所组成。【例例10.1.1】a，b，c，d4个个篮篮球球队队进进行行情情谊谊比比赛赛。为为了了表表示示个个队队之之间间比比赛赛情情况况，我我们们作作出出图图10.1.1图图形形。在在图图中中个个小小圆圆圈圈分分别别表表示示这这个个篮篮球球队队，称称之之为为结结点点。假假如如两两队队进进行行过过比比赛赛，则则在在表表示示该该队队两两个个结结点点之之间间用用一一条条线线连连接接起起来来，称称之之为为边边。这这么么利利用用一一个个图图形形使使各各队队之之间间比比赛情况一目了然。赛情况一目了然。1.图定义图定义10.1图基本概念图基本概念第4页图图10.1.1假如图假如图10.1.1中个结中个结点点a，b，c，d分别表分别表示个人，当某两个人示个人，当某两个人相互认识时，相互认识时，则将其则将其对应点之间用边连接起对应点之间用边连接起来。来。这时图又反应了这时图又反应了这个人之间认识关系。这个人之间认识关系。10.1图基本概念图基本概念第5页定定义义10.1.1一一个个图图G是是一一个个序序偶偶V(G),E(G)，记记为为GV(G),E(G)。其其中中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图基本概念图基本概念第6页【例【例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图基本概念图基本概念第7页图图10.1.210.1图基本概念图基本概念第8页图 10.1.210.1图基本概念图基本概念第9页2.图图G结点与边之间关系结点与边之间关系邻接点邻接点:同一条边两个端点。同一条边两个端点。孤立点孤立点:没有边与之关联结点。没有边与之关联结点。邻接边邻接边:关联同一个结点两条边。关联同一个结点两条边。孤立边孤立边:不与任何边相邻接边。不与任何边相邻接边。自自回回路路（环环）：关关联联同同一一个个结结点点一一条条边边（v，v）或）或v，v）。）。平行边平行边(多重边多重边):关联同一对结点多条边。关联同一对结点多条边。10.1图基本概念图基本概念第10页如如例例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图基本概念图基本概念第11页【例【例10.1.3】设图设图GV,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第12页3.图图G分类分类(1)按按G结结点点个个数数和和边边数数分分为为(n,m)图图,即即n个个结结点点,m条边图条边图;(2)尤尤其其地地,(n,0)称称为为零零图图,(1,0)图图称称为为平平凡凡图图。(2)按按G中中关关联联于于同同一一对对结结点点边边数数分分为为多多重重图图和和简简单单图图;多重图多重图:含有平行边图（如图含有平行边图（如图10.1.3）；线线图图:非多重图称为线图；非多重图称为线图；简单图简单图:不含平行边和自环图。不含平行边和自环图。10.1图基本概念图基本概念第13页G1、G2是多重图是多重图G3是线图是线图G4是简单图是简单图第14页(3)按按G边有序、无序分为边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图;有向图：有向图：每条边都是有向边图称为有向图每条边都是有向边图称为有向图（图（图10.1.4(b)；无向图：无向图：每条边都是无向边图称为无向图；每条边都是无向边图称为无向图；混合图：混合图：现有没有向边现有没有向边,又有有向边图称为混合图。又有有向边图称为混合图。(4)按按G边边旁旁有有没没有有数数量量特特征征分分为为加加权权图图、无无权权图图(如如图图10.1.4);10.1图基本概念图基本概念第15页图图10.1.4(5)按按G任意两个结点间是否有边分为任意两个结点间是否有边分为完全图完全图Kn(如图如图10.1.5)和和不完全图不完全图(如图如图10.1.6)。10.1图基本概念图基本概念第16页 完完全全图图：任任意意两两个个不不一一样样结结点点都都邻邻接接简简单单图图称称为为完完全全图。图。n个结点无向完全图记为个结点无向完全图记为Kn。图图10.1.5给给出出了了K3和和K4。从从图图中中能能够够看看出出K3有有条边，条边，K4有条边。有条边。轻易证实轻易证实Kn有有条边。条边。10.1图基本概念图基本概念图图10.1.6图图10.1.5K3与与K4示意图示意图第17页例例213213有向完全图有向完全图无向完全图无向完全图第18页给定任意一个含有给定任意一个含有n个结点图个结点图G,总能够把它补成一个总能够把它补成一个含有一样结点完全图含有一样结点完全图,方法是把那些缺乏边添上。方法是把那些缺乏边添上。定义定义10.1.2设设GV,E是一个含有是一个含有n个结点简单个结点简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G全部边后全部边后得到图（或由得到图（或由G中全部结点和全部能使中全部结点和全部能使G成为完全图成为完全图添加边组成图）称为添加边组成图）称为G补图补图，记为，记为 。比如，零图和完全图互为补图。比如，零图和完全图互为补图。10.1图基本概念图基本概念第19页G相对于相对于Kn补图是下列图中补图是下列图中第20页第21页互为补图互为补图互为补图互为补图互为补图互为补图第22页【例例10.1.4】（拉拉姆姆齐齐问问题题）试试证证在在任任何何一一个个有有个个人人组组里里，存存在在个个人人相相互互认认识识，或或者者存存在在个个人人相相互互不认识。不认识。我我们们用用个个结结点点来来代代表表人人，并并用用邻邻接接性性来来代代表表认认识识关关系系。这这么么一一来来，该该例例就就是是要要证证实实：任任意意一一个个有有个个结结点点图图G中中，或或者者有有个个相相互互邻邻接接点点，或或者者有有个个相相互互不不邻邻接接点点。即即，对对任任何何一一个个有有个个结结点点图图G，G或或 中含有一个三角形（即中含有一个三角形（即K3）。）。10.1图基本概念图基本概念第23页证证实实:设设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图基本概念图基本概念第24页10.1.2图结点度数及其计算图结点度数及其计算我们经常需要关心图中有多少条边与某一结点我们经常需要关心图中有多少条边与某一结点关联，这就引出了图一个主要概念关联，这就引出了图一个主要概念结点度数结点度数。10.1图基本概念图基本概念定定义义:在在有有向向图图中中,以以v为为终终点点边边数数称称为为结结点点v入入度度，记记为为 ;以以v为为始始点点边边数数称称为为结结点点v出出度度，记记为为 。结结点点v入入度度与与出出度度之之和和称称为为结结点点v度度数数，记记为为 d(v)或或deg(v)。第25页定义定义:在无向图中，图中结点在无向图中，图中结点v所关联边数所关联边数(有有环时计算两次环时计算两次)称为结点称为结点v度数，记为度数，记为d(v)或或deg(v)。第26页例例245136G1顶点顶点2入度：入度：1出度：出度：3顶点顶点4入度：入度：1出度：出度：0例例157324G26顶点顶点5度：度：3顶点顶点2度：度：4第27页定定理理10.1.1无无向向图图GV,E中中结结点点度度数数总总和和等等于于边数两倍，边数两倍，即即证实证实:因为每条边都与两个结点关联，因为每条边都与两个结点关联，所以加上一条所以加上一条边就使得各结点度数和增加边就使得各结点度数和增加2，由此结论成立。由此结论成立。定义定义：无向图中，假如每个结点度都是：无向图中，假如每个结点度都是k,则称为则称为k-度度正则图。正则图。10.1图基本概念图基本概念第28页推论推论:无向图无向图G中度数为奇数结点必为偶数个。中度数为奇数结点必为偶数个。证证实实:设设V1和和V2分分别别是是G中中奇奇数数度度数数和和偶偶数数度度数数结结点集。点集。由定理由定理10.1.1知知因为因为是偶数之和，是偶数之和，必为偶数，必为偶数，而而2|E|也为偶数，也为偶数，故故是偶数。是偶数。由此由此|V1|必为偶数。必为偶数。10.1图基本概念图基本概念第29页定理定理10.1.2在任何有向图在任何有向图GV,E中，中，有有图图10.1.4第30页10.1.3子图和图同构子图和图同构1.子图子图在在研研究究和和描描述述图图性性质质时时，子子图图概概念念占占有有主主要要地位。地位。定义定义10.1.5设有图设有图G=V,E和图和图 G=V,E。1)若若V V，E E，则称则称G是是G子图子图。2)若若G是是G子图，且子图，且EE，则称，则称G是是G 真子图真子图。第31页356例例245136图与子图图与子图第32页3)若若V=V，E E，则称，则称G是是G生成子图生成子图。图图10.1.7给出了图给出了图G以及它真子图以及它真子图G1和生成子图和生成子图G2。图图10.1.7图图G以及其真子图以及其真子图G1和生成子图和生成子图G210.1图基本概念图基本概念第33页例例画出画出K4全部非同构生成子图。全部非同构生成子图。第34页第35页2.图同构图同构10.1图基本概念图基本概念试观察下面各图有何异同？试观察下面各图有何异同？第36页图图10.1.8同构图同构图图图10.1.910.1图基本概念图基本概念第37页定义定义10.1.6设有图设有图G=V,E和图和图G=V,E。假如存在双射假如存在双射：VV，使得，使得e=(u,v)Eiffe=(u),(v)E，且且(u，v)与与(u),(v)有相同重数，则称有相同重数，则称G与与G同构。记作同构。记作G G。注注：由由同同构构定定义义可可知知，不不但但结结点点之之间间要要含含有有一一一一对对应应关关系系，而而且且要要求求这这种种对对应应关关系系保保持持结结点点间间邻邻接关系。对于有向图同构还要求保持边方向。接关系。对于有向图同构还要求保持边方向。10.1图基本概念图基本概念第38页【例例10.1.5】考考查查图图10.1.9中中两两个个图图GV,E和和G=V,E。显显然然，定定义义：VV,(vi)v i,能能够够验验证证是满足定义是满足定义10.1.6双射，所以双射，所以G G。10.1图基本概念图基本概念图图10.1.9第39页 普普通通说说来来，证证实实两两个个图图是是同同构构并并非非是是轻轻而而易易举举事事情情，往往往往需需要要花花些些气气力力。请请读读者者证实下列图中两个图是同构。证实下列图中两个图是同构。第40页第41页依据图同构定义，能够给出图同构必要条件以下：依据图同构定义，能够给出图同构必要条件以下：(1)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同结点数目相等。度数相同结点数目相等。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。第42页下列图中下列图中(a)和和(b)满足上述三个条件，然而并不满足上述三个条件，然而并不一样构。一样构。因为在因为在(a)中度数为中度数为3结点结点x与两个度数为与两个度数为1结点邻结点邻接，而接，而(b)中度数为中度数为3结点结点y仅与一个度数为仅与一个度数为1结点邻结点邻接。接。寻找一个简单有效方法来判定图同构，至今仍是寻找一个简单有效方法来判定图同构，至今仍是图论中悬而未决主要课题。图论中悬而未决主要课题。高等学校高等学校2121世纪教世纪教材材第43页第44页对对于于同同构构，形形象象地地说说，若若图图结结点点能能够够任任意意挪挪动动位位置置，而而边边是是完完全全弹弹性性，只只要要在在不不拉拉断断条条件件下下，这这个个图图能能够够变变形形为为另另一一个个图图，那那么么这这两两个个图图是是同同构构。故故同同构构两两个个图图从从外外形形上上看看可可能能不不一一样样，但它们但它们拓扑结构拓扑结构是一样。是一样。第45页10.2路与图连通性路与图连通性(Walks&TheConnectivityofGraphs)10.2.1路与回路路与回路(WalksandCircuits)10.2.2 图图 连连 通通 性性(The ConnectivityofGraphs)第46页10.2.1路与回路路与回路(WlaksandCircuits)定定义义10.2.1给给定定图图GV,E,设设v0,v1,vkV，e1，e2，ekE，其其中中ei是是关关联联于于结结点点vi-1和和vi边边，称称交交替替序序列列v0e1v1e2ekvk为为连连接接v0到到vk路路，v0和和vk分分别别称称为路起点与终点。路中边数目为路起点与终点。路中边数目k称作路长度。称作路长度。当当v0=vk时时,这条路称为回路。这条路称为回路。在在简单图简单图中一条路中一条路v0e1v1e2ekvk由它结点序列由它结点序列v0v1vk确定确定,所以简单图路所以简单图路,可表示为可表示为v0v1vk。如图。如图10.1.1表示简单图中，表示简单图中，路路ae1be4ce5d可写成可写成abcd。第47页定义定义10.2.2设设=v0e1v1e2ekvk是图是图G中连接中连接v0到到vk路。路。1)若若e1，e2，ek都都不不相相同同，则则称称路路为为简简单单路路或迹；或迹；2)若若v0，v1，vk都都不不相相同同，则则称称路路为为基基本本路路或通路；或通路；3)圈圈中中若若出出现现每每条条边边恰恰好好一一次次，称称简简单单圈圈。若若出出现现每个结点恰好一次，称基本圈。每个结点恰好一次，称基本圈。10.2.1路与回路路与回路(WlaksandCircuits)第48页结点重复情况结点重复情况边重复情况边重复情况路路允许允许允许允许简单路简单路允许允许不允许不允许基本路基本路不允许不允许不允许不允许回路回路允许允许允许允许简单圈简单圈允许允许不允许不允许基本圈基本圈不允许不允许不允许不允许10.2.1路与回路路与回路(WlaksandCircuits)第49页注意：不一样教材定义不一样！注意：不一样教材定义不一样！路径路径(walk)：图：图G中一个点边交替出现序列。中一个点边交替出现序列。迹迹(trail)：边不重路径。：边不重路径。路路(path):顶点不重复迹。顶点不重复迹。闭路径（闭路径（closedwalk）：起点和终点相同路径。）：起点和终点相同路径。闭迹闭迹(closedtrail)：起点和终点相同迹，也称为回路：起点和终点相同迹，也称为回路（circuit）。）。圈圈(cycle):起点和终点相同路。起点和终点相同路。10.2.1路与回路路与回路(WlaksandCircuits)第50页例例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，5，2，1简单回路：简单回路：1，2，3，1第51页比如在图比如在图10.2.1中，中，有连接有连接v5到到v3路路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路这也是一条简单路；路 v1e1v2e3v3是一条基本路；是一条基本路；路路v1e1v2e3v3e4v2e1v1是一是一条回路，条回路，但不是基本圈；但不是基本圈；路路v1e1v2e3v3e2v1是一条是一条回路，回路，也是圈。也是圈。图图10.2.110.2.1路与回路路与回路(WlaksandCircuits)第52页定义定义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路与回路路与回路(WlaksandCircuits)第53页注意注意:在有向图中在有向图中,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)。图图10.2.110.2.1路与回路路与回路(WlaksandCircuits)第54页定定理理10.2.1设设G是是含含有有n个个结结点点图图，假假如如从从结结点点v1到到另另一一结结点点v2存存在在一一条条路路，则则从从结结点点v1到到v2必必存存在在一一条条长长度度小小于于n1基基本本路路（通路）。（通路）。10.2.1路与回路路与回路(WlaksandCircuits)第55页证证实实:假假定定从从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。10.2.1路与回路路与回路(WlaksandCircuits)第56页1.无向图连通性无向图连通性定定义义10.2.4在在无无向向图图假假如如一一个个图图任任何何两两个个结结点点之之间间都都有有一一条条路路，那那么么我我们们称称这这个个图图是是连连通通，不不然然是是不连通。不连通。定定义义10.2.5图图G一一个个连连通通子子图图G（称称为为连连通通子子图图）若若不不包包含含在在G任任何何更更大大连连通通子子图图中中，它它就就被被称称作作G连通分支。我们把图连通分支。我们把图G连通分支个数记作连通分支个数记作（G）。）。10.2.2图连通性图连通性(TheConnectivityofGraphs)第57页图图10.2.3图图G与与G在图在图10.2.3中，中，G是不连通，是不连通，（G），），而而G是连是连通，通，（G）。）。任何一个图都可划分为若干个连通分支。任何一个图都可划分为若干个连通分支。显然，显然，仅当图仅当图G连通分支数连通分支数（G）时，）时，图图G是连通。是连通。10.2.2图连通性图连通性第58页 在在图图研研究究中中，经经常常需需要要考考虑虑删删去去与与增增加加结结点点、结结点点集集、边边和和边边集集（或或弧弧集集）问问题题。所所谓谓从从图图G=中中删删去去结结点点集集S，是是指指作作V-S以以及及从从E中中删删去去与与S中中全全部部结结点点相相联联结结边边而而得得到到子子图图，记记作作G-S；尤尤其其当当S=v时时，简简记记为为G-v；所所谓谓从从图图G=中中删删去去边边集集（或或弧弧集集）T，是是指指作作E-T，且且T中中全全部部边边所所关关联联结结点点仍仍在在V中中而而得得到到子图，记为子图，记为G-T；尤其当；尤其当T=e 时，简记作时，简记作G-e。第59页 所谓图所谓图G=增加结点集增加结点集S，是指作，是指作VS以以及向及向E中并入中并入S中、中、S与与V中所成边而得到图，中所成边而得到图，记作记作G+S；尤其当；尤其当S=v 时，简记为时，简记为G+v；图；图G=增加边集（或弧集）增加边集（或弧集）T是指作是指作ET所所得到图，记作得到图，记作G+T，这里，这里T中全部边（或弧）中全部边（或弧）关联结点属于关联结点属于V。第60页定义定义:给定连通无向图给定连通无向图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割边或桥割边或桥。第61页 对对于于连连通通非非平平凡凡图图G，称称(G)=|S|S是是G分分离离结结点点集集 为为图图G结结点点连连通通度度，它它表表明明产产生生不不连连通通图图而而需需要要删删去去结结点点最最少少数数目目。于于是是，对对于于分分离离图图G，(G)=0；对于存在割点连通图；对于存在割点连通图G，(G)=1。第62页类似地定义边连通度类似地定义边连通度(G)=|T|T是是G分离边集分离边集，它，它表明产生不连通图而需要删去边最少数目表明产生不连通图而需要删去边最少数目。可见，对于分离图可见，对于分离图G，(G)=0；对于平凡图；对于平凡图G，(G)=0；对于图；对于图K1，(K1)=0；对于存在割边连；对于存在割边连通图通图G，(G)=1；对于完全图；对于完全图Kn，(Kn)=n-1。第63页下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到关于年得到关于结点连通度、边连通度和最小度不等式联络定理：结点连通度、边连通度和最小度不等式联络定理：定理定理:对于任何一个无向图对于任何一个无向图G，有，有(G)(G)(G)。定定理理:一一个个连连通通无无向向图图G中中结结点点v是是割割点点存存在在两两个个结点结点u和和w，使得联结，使得联结u和和w每条链都经过每条链都经过v。第64页定定理理:一一个个连连通通无无向向图图G中中边边e是是割割边边存存在在两两个个结点结点u和和w，使得联结，使得联结u与与w每条链都经过每条链都经过e。下面再给出一个判定一条边是割边充要条件。下面再给出一个判定一条边是割边充要条件。定定理理:连连通通无无向向图图G中中一一条条边边e是是割割边边e不不包包含含在在图任何基本圈中。图任何基本圈中。第65页2.有向图连通性有向图连通性定定义义10.2.6在在有有向向图图中中,若若从从结结点点u到到v有有一一条路，则称条路，则称u可达可达v。定义定义10.2.7设有有向图设有有向图G，1)若若G任任意意两两个个结结点点中中,最最少少从从一一个个结结点点可可达另一个结点达另一个结点,则称图则称图G是单向连通是单向连通;10.2.2图连通性图连通性第66页2)假假如如G任任意意两两个个结结点点都都是是相相互互可可达达,则则称称图图G是是强强连通连通;3)假假如如略略去去边边方方向向后后，G成成为为连连通通无无向向图图，则则称称图图G是弱连通。是弱连通。从从定定义义可可知知：若若图图G是是单单向向连连通通，则则必必是是弱弱连连通通；若若图图G是是强强连连通通，则则必必是是单单向连通，向连通，且也是弱连通。且也是弱连通。但反之不真。但反之不真。第67页定定理理10.2.2一一个个有有向向图图G是是强强连连通通，当当且且仅仅当当G中中有有一一个个（有有向向）回回路路，它它最最少少包包含每个结点一次。含每个结点一次。第68页证证实实:必必要要性性：假假如如有有向向图图G是是强强连连通通，则则任任意意两两个个结结点点都都是是相相互互可可达达。故故必必可可作作一一回回路路经经过过图图中中全全部部各各结结点点。不不然然必必有有一一回回路路不不包包含含某某一一结结点点v。这这么么，v与与回回路路上上各各结结点点就就不不能能相相互互可可达达，这这与与G是强连通矛盾。是强连通矛盾。充充分分性性：假假如如G中中有有一一个个回回路路，它它最最少少包包含含每每个个结结点点一一次次，则则G中中任任意意两两个个结结点点是是相相互互可可达达，故故G是强连通。是强连通。10.2.2图连通性图连通性第69页定义定义10.2.8在有向图在有向图G=V,E中中,G是是G子图子图,若若G是强连通是强连通(单向连通单向连通,弱连通弱连通),没有包含没有包含G更大子图更大子图G是强连通是强连通(单向连通单向连通,弱连通弱连通),则称则称G是是G强分图强分图(单向分图单向分图,弱分图弱分图)。10.2.2图连通性图连通性第70页连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分图连通分图例例245136第71页图图10.2.510.2.2图连通性图连通性(TheConnectivityofGraphs)第72页在图在图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,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图连通性图连通性第73页下面给出简单有向图一个应用下面给出简单有向图一个应用资源分配图。资源分配图。在多道程序计算机系统中，能够同时执行多个程在多道程序计算机系统中，能够同时执行多个程序。实际上，程序共享计算机系统中资源，如磁序。实际上，程序共享计算机系统中资源，如磁带机、磁盘设备、带机、磁盘设备、CPU、主存贮器和编译程序等。、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作个程序要求使用某种资源，它要发出请求，操作系统必须确保这一请求得到满足。系统必须确保这一请求得到满足。第74页对资源请求可能发生冲突。如程序对资源请求可能发生冲突。如程序A控制着资源控制着资源r1，请求资源，请求资源r2；但程序；但程序B控制着资源控制着资源r2，请求资，请求资源源r1。这种情况称为处于死锁状态。然而冲突请。这种情况称为处于死锁状态。然而冲突请求必须处理，资源分配图有助发觉和纠正死锁。求必须处理，资源分配图有助发觉和纠正死锁。假设某一程序对一些资源请求，在该程序运行完假设某一程序对一些资源请求，在该程序运行完之前必须都得到满足。在请求时间里，被请求资之前必须都得到满足。在请求时间里，被请求资源是不能利用，程序控制着可利用资源，但对不源是不能利用，程序控制着可利用资源，但对不可利用资源则必须等候。可利用资源则必须等候。第75页令令Pt=p1，p2，pm 表示计算机系统在时刻表示计算机系统在时刻t程程序集合，序集合，Qt Pt是运行程序集合，或者说在时刻是运行程序集合，或者说在时刻t最最少分配一部分所请求资源程序集合。少分配一部分所请求资源程序集合。Rt=r1，r2，rn 是系统在时刻是系统在时刻t资源集合。资源分配图资源集合。资源分配图Gt=是有向图，它表示了时刻是有向图，它表示了时刻t系统中资源系统中资源分配状态。把每个资源分配状态。把每个资源ri看作图中一个结点，其中看作图中一个结点，其中i=1，2，n。表示有向边，表示有向边，E当且仅当程序当且仅当程序pkQt已分配到资源已分配到资源ri且等候资源且等候资源rj。第76页比如，令比如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资。资源分配状态是：源分配状态是：p1占用资源占用资源r4且请求资源且请求资源r1；p2占用资源占用资源r1且请求资源且请求资源r2和和r3；p3占用资源占用资源r2且请求资源且请求资源r3；p4占用资源占用资源r3且请求资源且请求资源r1和和r4。第77页于是，可得到资源分配图于是，可得到资源分配图Gt=，如图，如图10.2.7所表示。所表示。能够证实，在时刻能够证实，在时刻t计算机系统处于死锁状态计算机系统处于死锁状态资资源分配图源分配图Gt中包含强分图。于是，对于图中包含强分图。于是，对于图10.2.7，Gt是强连通，即处于死锁状态。是强连通，即处于死锁状态。第78页图图 10.2.7第79页10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)10.3.1邻接矩阵邻接矩阵(AdjacencyMatrices)10.3.2可达性矩阵可达性矩阵(ReachabilityMatrices)第80页10.3.1邻接矩阵邻接矩阵(AdjacencyMatrices)上上面面我我们们介介绍绍了了图图一一个个表表示示方方法法，即即用用图图形形表表示示图图。它它优优点点是是形形象象直直观观，不不过过这这种种表表示示在在结结点点与与边边数数目目很很多多时时是是不不方方便便。下下面面我我们们提提供供另另一一个个用用矩矩阵阵表表示示图图方方法法。利利用用这这种种方方法法，我我们们能能把把图图用用矩矩阵阵存存放放在在计计算算机机中中，利利用用矩矩阵阵运算还能够了解到它一些相关性质。运算还能够了解到它一些相关性质。第81页定定义义10.3.1设设GV,E是是有有n个个结结点点简简单单图图，则则n阶方阵（阶方阵（aij）称为）称为G邻接矩阵。邻接矩阵。其中其中不然不然如图如图10.3.1所表示图所表示图G，其邻接矩阵其邻接矩阵A为为10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第82页显然无向图邻接矩阵必是对称。显然无向图邻接矩阵必是对称。下下面面定定理理说说明明，在在邻邻接接矩矩阵阵A幂幂A2，A3，等矩阵中，等矩阵中，每个元素有特定含义。每个元素有特定含义。图图10.3.1G10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第83页图图10.3.1图图G10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第84页定定理理10.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时，时，A l+1AlA，所以所以10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第85页依依据据邻邻接接矩矩阵阵定定义义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成立。成立。10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第86页 由定理由定理10.3.1可得出以下结论：可得出以下结论：1)假如对假如对l1，2，n-1，Al（i，j）项项元元素素（ij）都都为为零零，那那么么vi和和vj之之间间无无任任何何路路相相连连接接，即即vi和和vj不不连连通通。所以，所以，vi和和vj必属于必属于G不一样连通分支。不一样连通分支。10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第87页2)结点结点vi到到vj（ij）间距离）间距离d（vi，vj）是是使使Al（l1，2，n-1）（i，j）项项元元素不为零最小整数素不为零最小整数l。3)Al（i，i）项元素）项元素a(l)ii表示开始并结束于表示开始并结束于vi长度为长度为l回路数目。回路数目。10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第88页【例例10.3.1】图图GV,E图图形形如如图图10.3.2，求求邻邻接接矩矩阵阵A和和A2，A3，A4，并并分分析析其元素图论意义。其元素图论意义。10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)图图10.3.2第89页解解:10.3图矩阵表示图矩阵表示(MatrixNotationofGraph)第90页 1)由由A中中a(1)121知，知，v1和和v2是邻接；是邻接；由由A3中中a(3)122知，知，v1到到v2长度为长度为3路有两条，路有两条，从图中从图中可看出是可看出是v1v2v1v2和和v1v2v3v2。2)由由A2主主对对角角线线上上元元素素知知，每每个个结结点点都都有有长长度度为为回回路路，其其中中结结点点v2有有两两条条：v2v1v2和和v2v3v2，其余结点只有一条。其余结点只有一条。3)因因为为A3主主对对角角线线上上元元素素全全为为零零，所所以以G中中没有长度为回路。没有长度为回路。10.3图矩