离散数学-图论-课件

第第1010章章图论图论(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）第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论10.1.1图的基本概念图的基本概念10.1.2图的结点的度数及其计算图的结点的度数及其计算10.1.3子图和图的同构子图和图的同构第第1010章章图论图论(GraphTheory)图图10.1.1哥尼斯堡七桥问题离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论现现实实世世界界中中许许多多现现象象能能用用某某种种图图形形表表示示,这这种种图图形形是由一些点和一些连接两点间的连线所组成。是由一些点和一些连接两点间的连线所组成。【例例10.1.1】a，b，c，d4个个篮篮球球队队进进行行友友谊谊比比赛赛。为为了了表表示示个个队队之之间间比比赛赛的的情情况况，我我们们作作出出图图10.1.1的的图图形形。在在图图中中个个小小圆圆圈圈分分别别表表示示这这个个篮篮球球队队，称称之之为为结结点点。如如果果两两队队进进行行过过比比赛赛，则则在在表表示示该该队队的的两两个个结结点点之之间间用用一一条条线线连连接接起起来来，称称之之为为边边。这这样样利利用用一一个个图图形形使使各各队队之之间间的比赛情况一目了然。的比赛情况一目了然。1.图的定义图的定义10.1图的基本概念图的基本概念第第1010章章图论图论(GraphTheory)图图10.1.1如果图如果图10.1.1中的个中的个结点结点a，b，c，d分别分别表示个人，当某两个表示个人，当某两个人互相认识时，人互相认识时，则将则将其对应点之间用边连接其对应点之间用边连接起来。起来。这时的图又反这时的图又反映了这个人之间的认映了这个人之间的认识关系。识关系。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定定义义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互相关联。互相关联。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)【例例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可用一个图形来表示且表示是不唯一的。可用一个图形来表示且表示是不唯一的。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)图图10.1.2离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)图 10.1.2离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)2.图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点:同一条边的两个端点。同一条边的两个端点。孤立点孤立点:没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边:关联同一个结点的两条边。关联同一个结点的两条边。孤立边孤立边:不与任何边相邻接的边。不与任何边相邻接的边。自自回回路路（环环）：关关联联同同一一个个结结点点的的一一条条边边（v，v）或）或v，v）。）。平行边平行边(多重边多重边):关联同一对结点的多条边。关联同一对结点的多条边。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)如如例例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是邻接的。是邻接的。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)【例例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.3第第1010章章图论图论(GraphTheory)3.图图G的分类的分类(1)按按G的的结结点点个个数数和和边边数数分分为为(n,m)图图,即即n个个结结点点,m条边的图条边的图;(2)特别地特别地,(n,0)称为称为零图零图,(1,0)图称为图称为平凡图平凡图。(2)按按G中中关关联联于于同同一一对对结结点点的的边边数数分分为为多多重重图图和和简简单图单图;多重图多重图:含有平行边的图（如图含有平行边的图（如图10.1.3）；线线图图:非多重图称为线图；非多重图称为线图；简单图简单图:不含平行边和自环的图。不含平行边和自环的图。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)G1、G2是多重图是多重图G3是线图是线图G4是简单图是简单图第第1010章章图论图论(GraphTheory)(3)按按G的边有序、无序分为的边有序、无序分为有向图、无向图和混合图有向图、无向图和混合图;有向图：有向图：每条边都是有向边的图称为有向图每条边都是有向边的图称为有向图（图（图10.1.4(b)；无向图：无向图：每条边都是无向边的图称为无向图；每条边都是无向边的图称为无向图；混合图：混合图：既有无向边既有无向边,又有有向边的图称为混合图。又有有向边的图称为混合图。(4)按按G的的边边旁旁有有无无数数量量特特征征分分为为加加权权图图、无无权权图图(如如图图10.1.4);离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)图图10.1.4(5)按按G的任意两个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn(如图如图10.1.5)和和不完全图不完全图(如图如图10.1.6)。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)完完全全图图：任任意意两两个个不不同同的的结结点点都都邻邻接接的的简简单单图图称称为为完完全图。全图。n个结点的无向完全图记为个结点的无向完全图记为Kn。图图10.1.5给给出出了了K3和和K4。从从图图中中可可以以看看出出K3有有条边，条边，K4有条边。有条边。容易证明容易证明Kn有有条边。条边。离散数学离散数学图论图论图图10.1.6图图10.1.5K3与与K4示意图示意图第第1010章章图论图论(GraphTheory)例例213213有向完全图有向完全图无向完全图无向完全图第第1010章章图论图论(GraphTheory)给定任意一个含有给定任意一个含有n个结点的图个结点的图G,总可以把它补成一个总可以把它补成一个具有同样结点的完全图具有同样结点的完全图,方法是把那些缺少的边添上。方法是把那些缺少的边添上。定义定义10.1.2设设GV,E是一个具有是一个具有n个结点的简单个结点的简单图。以图。以V为结点集，以从完全图为结点集，以从完全图Kn中删去中删去G的所有边后的所有边后得到的图（或由得到的图（或由G中所有结点和所有能使中所有结点和所有能使G成为完全图成为完全图的添加边组成的图）称为的添加边组成的图）称为G的的补图补图，记为，记为 。例如，零图和完全图互为补图。例如，零图和完全图互为补图。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)G相对于相对于Kn的补图是下图中的的补图是下图中的第第1010章章图论图论(GraphTheory)第第1010章章图论图论(GraphTheory)互为补图互为补图互为补图互为补图互为补图互为补图第第1010章章图论图论(GraphTheory)【例例10.1.4】（拉拉姆姆齐齐问问题题）试试证证在在任任何何一一个个有有个个人人的的组组里里，存存在在个个人人互互相相认认识识，或或者者存存在在个个人人互互相不认识。相不认识。我我们们用用个个结结点点来来代代表表人人，并并用用邻邻接接性性来来代代表表认认识识关关系系。这这样样一一来来，该该例例就就是是要要证证明明：任任意意一一个个有有个个结结点点的的图图G中中，或或者者有有个个互互相相邻邻接接的的点点，或或者者有有个个互互相相不不邻邻接接的的点点。即即，对对任任何何一一个个有有个个结结点点的的图图G，G或或 中含有一个三角形（即中含有一个三角形（即K3）。）。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)证证明明:设设GV,E，|V|6，v是是G中中一一结结点点。因因为为v与与G的的其其余余个个结结点点或或者者在在 中中邻邻接接，或或者者在在G中中邻邻接接。故故不不失失一一般般性性可可假假定定，有有个个结结点点v1，v2，v3在在G中与中与v邻接。邻接。如如果果这这个个结结点点中中有有两两个个结结点点（如如v1，v2）邻邻接接，则则它它们们与与v就就是是G中中一一个个三三角角形形的的个个顶顶点点。如如果果这这3个个结结点点中中任任意意两两个个在在G中中均均不不邻邻接接，则则v1，v2，v3就就是是 中一个三角形的个顶点。中一个三角形的个顶点。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)10.1.2图的结点的度数及其计算图的结点的度数及其计算我们常常需要关心图中有多少条边与某一结点我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念关联，这就引出了图的一个重要概念结点的度数结点的度数。离散数学离散数学图论图论定定义义:在在有有向向图图中中,以以v为为终终点点的的边边数数称称为为结结点点v的的入入度度，记记为为 ;以以v为为始始点点的的边边数数称称为为结结点点v的的出出度度，记记为为 。结结点点v的的入入度度与与出出度度之之和和称称为为结结点点v的度数，记为的度数，记为 d(v)或或deg(v)。第第1010章章图论图论(GraphTheory)定义定义:在无向图中，图中结点在无向图中，图中结点v所关联的边数所关联的边数(有环时计算两次有环时计算两次)称为结点称为结点v的度数，记为的度数，记为d(v)或或deg(v)。第第1010章章图论图论(GraphTheory)例例245136G1顶点顶点2入度：入度：1出度：出度：3顶点顶点4入度：入度：1出度：出度：0例例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：4第第1010章章图论图论(GraphTheory)定定理理10.1.1无无向向图图GV,E中中结结点点度度数数的的总总和和等等于边数的两倍，于边数的两倍，即即证明证明:因为每条边都与两个结点关联，因为每条边都与两个结点关联，所以加上一条所以加上一条边就使得各结点度数的和增加边就使得各结点度数的和增加2，由此结论成立。由此结论成立。定义定义：无向图中，如果每个结点的度都是：无向图中，如果每个结点的度都是k,则称为则称为k-度正则图。度正则图。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)推论推论:无向图无向图G中度数为奇数的结点必为偶数个。中度数为奇数的结点必为偶数个。证证明明:设设V1和和V2分分别别是是G中中奇奇数数度度数数和和偶偶数数度度数数的的结结点集。点集。由定理由定理10.1.1知知由于由于是偶数之和，是偶数之和，必为偶数，必为偶数，而而2|E|也为偶数，也为偶数，故故是偶数。是偶数。由此由此|V1|必为偶数。必为偶数。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定理定理10.1.2在任何有向图在任何有向图GV,E中，中，有有图图10.1.4第第1010章章图论图论(GraphTheory)10.1.3子图和图的同构子图和图的同构1.子图子图在在研研究究和和描描述述图图的的性性质质时时，子子图图的的概概念念占占有有重要地位。重要地位。定义定义10.1.5设有图设有图G=V,E和图和图 G=V,E。1)若若VV，EE，则称则称G是是G的的子图子图。2)若若G是是G的子图，且的子图，且EE，则称，则称G是是G 的的真子图真子图。第第1010章章图论图论(GraphTheory)356例例245136图与子图图与子图第第1010章章图论图论(GraphTheory)3)若若V=V，EE，则称，则称G是是G的的生成子图生成子图。图图10.1.7给出了图给出了图G以及它的真子图以及它的真子图G1和生成子图和生成子图G2。图图10.1.7图图G以及其真子图以及其真子图G1和生成子图和生成子图G2离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)例例画出画出K4的所有非同构的生成子图。的所有非同构的生成子图。第第1010章章图论图论(GraphTheory)第第1010章章图论图论(GraphTheory)2.图的同构图的同构离散数学离散数学图论图论试观察下面各图有何异同？试观察下面各图有何异同？第第1010章章图论图论(GraphTheory)图图10.1.8同构的图同构的图图图10.1.9离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定义定义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。注注：由由同同构构的的定定义义可可知知，不不仅仅结结点点之之间间要要具具有有一一一一对对应应关关系系，而而且且要要求求这这种种对对应应关关系系保保持持结结点点间间的的邻邻接接关关系系。对对于于有有向向图图的的同同构构还还要要求求保保持持边边的的方向。方向。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)【例例10.1.5】考考察察图图10.1.9中中的的两两个个图图GV,E和和G=V,E。显显然然，定定义义：VV,(vi)v i,可可以以验验证证是是满足定义满足定义10.1.6的双射，所以的双射，所以G G。离散数学离散数学图论图论图图10.1.9第第1010章章图论图论(GraphTheory)一一般般说说来来，证证明明两两个个图图是是同同构构的的并并非非是是轻轻而而易易举举的的事事情情，往往往往需需要要花花些些气气力力。请请读者证明下图中两个图是同构的。读者证明下图中两个图是同构的。第第1010章章图论图论(GraphTheory)第第1010章章图论图论(GraphTheory)根据图的同构定义，可以给出图同构的必要条件根据图的同构定义，可以给出图同构的必要条件如下：如下：(1)结点数目相等；结点数目相等；(2)边数相等；边数相等；(3)度数相同的结点数目相等。度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。但这仅仅是必要条件而不是充分条件。第第1010章章图论图论(GraphTheory)下图中的下图中的(a)和和(b)满足上述三个条件，然而并不同满足上述三个条件，然而并不同构。构。因为在因为在(a)中度数为中度数为3的结点的结点x与两个度数为与两个度数为1的结点的结点邻接，而邻接，而(b)中度数为中度数为3的结点的结点y仅与一个度数为仅与一个度数为1的的结点邻接。结点邻接。寻找一种简单有效的方法来判定图的同构，至今寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。仍是图论中悬而未决的重要课题。第第1010章章图论图论(GraphTheory)第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论对对于于同同构构，形形象象地地说说，若若图图的的结结点点可可以以任任意意挪挪动动位位置置，而而边边是是完完全全弹弹性性的的，只只要要在在不不拉拉断断的的条条件件下下，这这个个图图可可以以变变形形为为另另一一个个图图，那那么么这这两两个个图图是是同同构构的的。故故同同构构的的两两个个图图从从外外形形上上看看可能不一样，但它们的可能不一样，但它们的拓扑结构拓扑结构是一样的。是一样的。第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论 10.2.1路与回路路与回路(WalksandCircuits)10.2.2 图图的的连连通通性性(The ConnectivityofGraphs)第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论定义定义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。第第1010章章图论图论(GraphTheory)定定义义10.2.2设设=v0e1v1e2ekvk是是图图G中中连连接接v0到到vk的的路。路。1)若若e1，e2，ek都都不不相相同同，则则称称路路为为简简单单路路或迹；或迹；2)若若v0，v1，vk都都不不相相同同，则则称称路路为为基基本本路路或通路；或通路；3)圈圈中中若若出出现现的的每每条条边边恰恰好好一一次次，称称简简单单圈圈。若若出出现的每个结点恰好一次，称基本圈。现的每个结点恰好一次，称基本圈。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)结点重复情况结点重复情况边重复情况边重复情况路路允许允许允许允许简单路简单路允许允许不允许不允许基本路基本路不允许不允许不允许不允许回路回路允许允许允许允许简单圈简单圈允许允许不允许不允许基本圈基本圈不允许不允许不允许不允许离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)注意：不同的教材定义不同！注意：不同的教材定义不同！途径途径(walk)：图：图G中一个点边交替出现的序列。中一个点边交替出现的序列。迹迹(trail)：边不重的途径。：边不重的途径。路路(path):顶点不重复的迹。顶点不重复的迹。闭途径（闭途径（closedwalk）：起点和终点相同的途径。）：起点和终点相同的途径。闭迹闭迹(closedtrail)：起点和终点相同的迹，也称为回：起点和终点相同的迹，也称为回路（路（circuit）。）。圈圈(cycle):起点和终点相同的路。起点和终点相同的路。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)例例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第第1010章章图论图论(GraphTheory)例如在图例如在图10.2.1中，中，有连接有连接v5到到v3的路的路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路这也是一条简单路；路 v1e1v2e3v3是一条基本路；是一条基本路；路路v1e1v2e3v3e4v2e1v1是一是一条回路，条回路，但不是基本圈；但不是基本圈；路路v1e1v2e3v3e2v1是一条是一条回路，回路，也是圈。也是圈。图图10.2.1离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定义定义10.2.3在图在图G中，中，若结点若结点vi到到vj有路连接有路连接（这时称（这时称vi和和vj是可达的），是可达的），其中长度最短的其中长度最短的路的长度称为路的长度称为vi到到vj的距离，的距离，用符号用符号d(vi,vj)表表示。若从示。若从vi到到vj不存在路径不存在路径,则则d(vi,vj)=。例如在图例如在图10.2.1中，中，（v1，v4）。）。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)注意注意:在有向图中在有向图中,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.1离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定定理理10.2.1设设G是是具具有有n个个结结点点的的图图，如如果果从从结结点点v1到到另另一一结结点点v2存存在在一一条条路路，则则从从结结点点v1到到v2必必存存在在一一条条长长度度不不大大于于n1的的基本路（通路）。基本路（通路）。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)证证明明:假假定定从从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。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)1.无向图的连通性无向图的连通性定定义义10.2.4在在无无向向图图如如果果一一个个图图的的任任何何两两个个结结点点之之间间都都有有一一条条路路，那那么么我我们们称称这这个个图图是是连连通通的的，否否则是不连通的。则是不连通的。定定义义10.2.5图图G的的一一个个连连通通的的子子图图G（称称为为连连通通子子图图）若若不不包包含含在在G的的任任何何更更大大的的连连通通子子图图中中，它它就就被被称称作作G的的连连通通分分支支。我我们们把把图图G的的连连通通分分支支个个数记作数记作（G）。）。10.2.2 图图 的的 连连 通通 性性(The Connectivity ofGraphs)第第1010章章图论图论(GraphTheory)图图10.2.3图图G与与G在图在图10.2.3中，中，G是不连通的，是不连通的，（G），），而而G是是连通的，连通的，（G）。）。任何一个图都可划分为若干个连通分支。任何一个图都可划分为若干个连通分支。显然，显然，仅当图仅当图G的连通分支数的连通分支数（G）时，）时，图图G是连通的。是连通的。10.2.2图的连通性图的连通性第第1010章章图论图论(GraphTheory)在在图图的的研研究究中中，常常常常需需要要考考虑虑删删去去与与增增加加结结点点、结结点点集集、边边和和边边集集（或或弧弧集集）的的问问题题。所所谓谓从从图图G=中中删删去去结结点点集集S，是是指指作作V-S以以及及从从E中中删删去去与与S中中的的全全部部结结点点相相联联结结的的边边而而得得到到的的子子图图，记记作作G-S；特特别别当当S=v时时，简简记记为为G-v；所所谓谓从从图图G=中中删删去去边边集集（或或弧弧集集）T，是是指指作作E-T，且且T中中的的全全部部边边所所关关联联的的结结点点仍仍在在V中中而而得得到到的的子子图图，记记为为G-T；特特别别当当T=e 时，简记作时，简记作G-e。第第1010章章图论图论(GraphTheory)所谓图所谓图G=增加结点集增加结点集S，是指作，是指作VS以以及向及向E中并入中并入S中、中、S与与V中所成的边而得到的中所成的边而得到的图，记作图，记作G+S；特别当；特别当S=v 时，简记为时，简记为G+v；图图G=增加边集（或弧集）增加边集（或弧集）T是指作是指作ET所得到的图，记作所得到的图，记作G+T，这里，这里T中全部边（或中全部边（或弧）的关联结点属于弧）的关联结点属于V。第第1010章章图论图论(GraphTheory)定义定义:给定连通无向图给定连通无向图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章章图论图论(GraphTheory)对对于于连连通通的的非非平平凡凡图图G，称称(G)=|S|S是是G的的分分离离结结点点集集 为为图图G的的结结点点连连通通度度，它它表表明明产产生生不不连连通通图图而而需需要要删删去去结结点点的的最最少少数数目目。于于是是，对对于于分分离离图图G，(G)=0；对对于于存存在在割割点点的的连连通通图图G，(G)=1。第第1010章章图论图论(GraphTheory)类似地定义边连通度类似地定义边连通度(G)=|T|T是是G的分离边的分离边集集，它，它表明产生不连通图而需要删去边的最少表明产生不连通图而需要删去边的最少数目数目。可见，对于分离图。可见，对于分离图G，(G)=0；对于平凡；对于平凡图图G，(G)=0；对于图；对于图K1，(K1)=0；对于存在割；对于存在割边的连通图边的连通图G，(G)=1；对于完全图；对于完全图Kn，(Kn)=n-1。第第1010章章图论图论(GraphTheory)下面是由惠特尼下面是由惠特尼(H.Whitney)于于1932年得到的关年得到的关于结点连通度、边连通度和最小度的不等式联系于结点连通度、边连通度和最小度的不等式联系的定理：的定理：定理定理:对于任何一个无向图对于任何一个无向图G，有，有(G)(G)(G)。定定理理:一一个个连连通通无无向向图图G中中的的结结点点v是是割割点点存存在在两两个结点个结点u和和w，使得联结，使得联结u和和w的每条链都经过的每条链都经过v。第第1010章章图论图论(GraphTheory)定定理理:一一个个连连通通无无向向图图G中中的的边边e是是割割边边存存在在两两个个结点结点u和和w，使得联结，使得联结u与与w的每条链都经过的每条链都经过e。下面再给出一个判定一条边是割边的充要条件。下面再给出一个判定一条边是割边的充要条件。定定理理:连连通通无无向向图图G中中的的一一条条边边e是是割割边边e不不包包含含在图的任何基本圈中。在图的任何基本圈中。第第1010章章图论图论(GraphTheory)2.有向图的连通性有向图的连通性定定义义10.2.6在在有有向向图图中中,若若从从结结点点u到到v有有一一条路，则称条路，则称u可达可达v。定义定义10.2.7设有有向图设有有向图G，1)若若G的的任任意意两两个个结结点点中中,至至少少从从一一个个结结点点可可达另一个结点达另一个结点,则称图则称图G是单向连通的是单向连通的;10.2.2图的连通性图的连通性第第1010章章图论图论(GraphTheory)2)如如果果G的的任任意意两两个个结结点点都都是是相相互互可可达达的的,则则称称图图G是是强连通的强连通的;3)如如果果略略去去边边的的方方向向后后，G成成为为连连通通的的无无向向图图，则则称图称图G是弱连通的。是弱连通的。从从定定义义可可知知：若若图图G是是单单向向连连通通的的，则则必必是是弱弱连连通通的的；若若图图G是是强强连连通通的的，则则必必是是单单向向连连通通的的，且且也也是是弱弱连连通通的的。但但反反之不真。之不真。第第1010章章图论图论(GraphTheory)定定理理10.2.2一一个个有有向向图图G是是强强连连通通的的，当当且且仅仅当当G中中有有一一个个（有有向向）回回路路，它它至至少少包含每个结点一次。包含每个结点一次。第第1010章章图论图论(GraphTheory)证证明明:必必要要性性：如如果果有有向向图图G是是强强连连通通的的，则则任任意意两两个个结结点点都都是是相相互互可可达达的的。故故必必可可作作一一回回路路经经过过图图中中所所有有各各结结点点。否否则则必必有有一一回回路路不不包包含含某某一一结结点点v。这这样样，v与与回回路路上上各各结结点点就就不不能能相相互互可可达达，这与这与G是强连通矛盾。是强连通矛盾。充充分分性性：如如果果G中中有有一一个个回回路路，它它至至少少包包含含每每个个结结点点一一次次，则则G中中任任意意两两个个结结点点是是相相互互可可达达的的，故故G是强连通的。是强连通的。10.2.2图的连通性图的连通性第第1010章章图论图论(GraphTheory)定义定义10.2.8在有向图在有向图G=V,E中中,G是是G的子的子图图,若若G是强连通的是强连通的(单向连通的单向连通的,弱连通的弱连通的),没没有包含有包含G的更大子图的更大子图G是强连通的是强连通的(单向连通单向连通的的,弱连通的弱连通的),则称则称G是是G的强分图的强分图(单向分图单向分图,弱弱分图分图)。10.2.2图的连通性图的连通性第第1010章章图论图论(GraphTheory)连通图连通图例例245136强连通图强连通图356例例非连通图非连通图连通分图连通分图例例245136第第1010章章图论图论(GraphTheory)图图10.2.510.2.2 图图 的的 连连 通通 性性(The Connectivity ofGraphs)第第1010章章图论图论(GraphTheory)在图在图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图的连通性图的连通性第第1010章章图论图论(GraphTheory)下面给出简单有向图的一个应用下面给出简单有向图的一个应用资源分配图。资源分配图。在多道程序的计算机系统中，可以同时执行多个在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、如磁带机、磁盘设备、CPU、主存贮器和编译程、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。操作系统必须保证这一请求得到满足。第第1010章章图论图论(GraphTheory)对资源的请求可能发生冲突。如程序对资源的请求可能发生冲突。如程序A控制着资控制着资源源r1，请求资源，请求资源r2；但程序；但程序B控制着资源控制着资源r2，请求，请求资源资源r1。这种情况称为处于死锁状态。然而冲突。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死的请求必须解决，资源分配图有助发现和纠正死锁。锁。假设某一程序对一些资源的请求，在该程序运行假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待。源，但对不可利用的资源则必须等待。第第1010章章图论图论(GraphTheory)令令Pt=p1，p2，pm 表示计算机系统在时刻表示计算机系统在时刻t的的程序集合，程序集合，Qt Pt是运行的程序集合，或者说在时是运行的程序集合，或者说在时刻刻t至少分配一部分所请求的资源的程序集合。至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn 是系统在时刻是系统在时刻t的资源集合。资源的资源集合。资源分配图分配图Gt=是有向图，它表示了时刻是有向图，它表示了时刻t系统系统中资源分配状态。把每个资源中资源分配状态。把每个资源ri看作图中一个结点，看作图中一个结点，其中其中i=1，2，n。表示有向边，表示有向边，E当且仅当程序当且仅当程序pkQt已分配到资源已分配到资源ri且等待且等待资源资源rj。第第1010章章图论图论(GraphTheory)例如，令例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资源。资源分配状态是：分配状态是：p1占用资源占用资源r4且请求资源且请求资源r1；p2占用资源占用资源r1且请求资源且请求资源r2和和r3；p3占用资源占用资源r2且请求资源且请求资源r3；p4占用资源占用资源r3且请求资源且请求资源r1和和r4。第第1010章章图论图论(GraphTheory)于是，可得到资源分配图于是，可得到资源分配图Gt=，如图，如图10.2.7所示。所示。能够证明，在时刻能够证明，在时刻t计算机系统处于死锁状态计算机系统处于死锁状态资资源分配图源分配图Gt中包含强分图。于是，对于图中包含强分图。于是，对于图10.2.7，Gt是强连通的，即处于死锁状态。是强连通的，即处于死锁状态。第第1010章章图论图论(GraphTheory)离散数学离散数学 图论图论第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论 10.3.1邻接矩阵邻接矩阵(AdjacencyMatrices)10.3.2可达性矩阵可达性矩阵(ReachabilityMatrices)第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论 上上面面我我们们介介绍绍了了图图的的一一种种表表示示方方法法，即即用用图图形形表表示示图图。它它的的优优点点是是形形象象直直观观，但但是是这这种种表表示示在在结结点点与与边边的的数数目目很很多多时时是是不不方方便便的的。下下面面我我们们提提供供另另一一种种用用矩矩阵阵表表示示图图的的方方法法。利利用用这这种种方方法法，我我们们能能把把图图用用矩矩阵阵存存储储在在计计算算机机中中，利利用用矩矩阵阵的的运运算算还还可可以以了了解解到到它它的的一一些些有有关性质。关性质。第第1010章章图论图论(GraphTheory)定定义义10.3.1设设GV,E是是有有n个个结结点点的的简简单单图图，则则n阶方阵（阶方阵（aij）称为）称为G的邻接矩阵。的邻接矩阵。其中其中否则否则如图如图10.3.1所示的图所示的图G，其邻接矩阵其邻接矩阵A为为离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)显然无向图的邻接矩阵必是对称的。显然无向图的邻接矩阵必是对称的。下下面面的的定定理理说说明明，在在邻邻接接矩矩阵阵A的的幂幂A2，A3，等矩阵中，等矩阵中，每个元素有特定的含义。每个元素有特定的含义。图图10.3.1G离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)图图10.3.1图图G离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定定理理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，所以所以离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)根根据据邻邻接接矩矩阵阵定定义义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成立。成立。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)由定理由定理10.3.1可得出以下结论：可得出以下结论：1)如果对如果对l1，2，n-1，Al的的（i，j）项项元元素素（ij）都都为为零零，那那么么vi和和vj之之间间无无任任何何路路相相连连接接，即即vi和和vj不不连连通通。因此，因此，vi和和vj必属于必属于G的不同的连通分支。的不同的连通分支。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)2)结点结点vi到到vj（ij）间的距离）间的距离d（vi，vj）是是使使Al（l1，2，n-1）的的（i，j）项项元素不为零的最小整数元素不为零的最小整数l。3)Al的（的（i，i）项元素）项元素a(l)ii表示开始并结束于表示开始并结束于vi长度为长度为l的回路的数目。的回路的数目。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)【例例10.3.1】图图GV,E的的图图形形如如图图10.3.2，求求邻邻接接矩矩阵阵A和和A2，A3，A4，并并分析其元素的图论意义。分析其元素的图论意义。离散数学离散数学图论图论图图10.3.2第第1010章章图论图论(GraphTheory)解解:离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)1)由由A中中a(1)121知，知，v1和和v2是邻接的；是邻接的；由由A3中中a(3)122知，知，v1到到v2长度为长度为3的路有两条，的路有两条，从图从图中可看出是中可看出是v1v2v1v2和和v1v2v3v2。2)由由A2的的主主对对角角线线上上元元素素知知，每每个个结结点点都都有有长长度度为为的的回回路路，其其中中结结点点v2有有两两条条：v2v1v2和和v2v3v2，其余结点只有一条。其余结点只有一条。3)由由于于A3的的主主对对角角线线上上元元素素全全为为零零，所所以以G中没有长度为的回路。中没有长度为的回路。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)4)由于由于 所以结点所以结点v3和和v4间无路，间无路，它们属于不同的连通它们属于不同的连通分支。分支。5)d（v1，v3）。）。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论下面用矩阵来研究有向图的可达性。下面用矩阵来研究有向图的可达性。与与无无向向图图一一样样，有有向向图图也也能能用用相相应应的的邻邻接接矩矩阵阵A（aij）表示，）表示，其中其中但注意这里但注意这里A不一定是对称的。不一定是对称的。第第1010章章图论图论(GraphTheory)定义定义10.3.2设设GV,E是一个有是一个有n个个结点的有向图，结点的有向图，则则n阶方阵阶方阵（pij）称）称为图为图G的可达性矩阵。的可达性矩阵。其中其中(vi到到vj可达可达)(否则否则)离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)根根据据可可达达性性矩矩阵阵，可可知知图图中中任任意意两两个个结结点点之之间间是是否否至至少少存存在在一一条条路路以以及及是是否否存存在回路。在回路。根根据据n个个结结点点的的图图中中，基基本本路路的的长长度度不不大大于于n-1，基基本本圈圈的的长长度度不不大大于于n。因因此此，分以下两步可得到可达性矩阵。分以下两步可得到可达性矩阵。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)1)令令BnAA2An,2)将将矩矩阵阵n中中不不为为零零的的元元素素均均改改为为，为为零零的的元元素素不不变变，所所得得的的矩矩阵阵P就就是是可可达达性性矩矩阵。阵。当当n很很大大时时，这这种种求求可可达达性性矩矩阵阵的的方方法法就就很很复复杂杂。下下面面再再介介绍绍一一种种更更简简便便的的求求可可达达性性矩矩阵的方法。阵的方法。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)因因可可达达性性矩矩阵阵是是一一个个元元素素仅仅为为或或的的矩矩阵阵（称称为为布布尔尔矩矩阵阵），而而在在研研究究可可达达性性问问题题时时，我我们们对对于于两两个个结结点点间间具具有有路路的的数数目目并并不不感感兴兴趣趣，所所关关心心的的只只是是两两结结点点间间是是否否有有路路存存在在。因因此此，我我们们可可将将矩矩阵阵A，A2,An,分分别别改改为为布布尔尔矩矩阵阵A(1)，A(2)，A(n)。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)由此有由此有 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)相应的矩阵加法和乘法称为矩阵的布尔加相应的矩阵加法和乘法称为矩阵的布尔加和和布尔乘布尔乘。离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论令令B和和C的布尔和、布尔积分别记为的布尔和、布尔积分别记为B C和和B C，其定义为，其定义为(B C)ij=bij cij(B C)ij=(bik ckj)i,j=1,2,n。其中。其中bij，cij分别是分别是B和和C的的i行行j列元素。列元素。第第1010章章图论图论(GraphTheory)特别地，对于邻接矩阵特别地，对于邻接矩阵A，记，记A A=A(2)，对任何，对任何r=2,3,有有A(r-1)A=A(r)要注意的是要注意的是Ar与与A(r)的差别。的差别。Ar中中表明从表明从vi到到vj长长度为度为r的链（或路）的数目，而的链（或路）的数目，而A(r)中中是指出：是指出：若若vi到到vj至少存在一条链（或路）时，至少存在一条链（或路）时，=1，否，否则，则，=0。由上说明，便得到可达矩阵由上说明，便得到可达矩阵P为：为：P=A A(2)A(3)A(n)=A(k)第第1010章章图论图论(GraphTheory)图图10.3.3离散数学离散数学图论图论 【例例10.3.2】求出图求出图10.3.3所示图的可达性矩阵。所示图的可达性矩阵。第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论解解:该图的邻接矩阵为该图的邻接矩阵为第第1010章章图论图论(GraphTheory)故故离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)定理定理10.3.2有向图有向图G是强连通的当且仅当其可是强连通的当且仅当其可达性矩阵达性矩阵P的元素均为。的元素均为。与求关系的传递闭包的关系矩阵相同！与求关系的传递闭包的关系矩阵相同！离散数学离散数学图论图论第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论 为了计算为了计算A+或或P，自然可先依次求得，自然可先依次求得A(2)，A(3)，A(n)，然后再计算，然后再计算A(k)，其结果即为所求，其结果即为所求，这是计算这是计算A+或或P的一种方法，还可介绍一种现有效的一种方法，还可介绍一种现有效的方法的方法Warshall算法，它由邻接矩阵算法，它由邻接矩阵A依下面给依下面给出的步骤便能计算出的步骤便能计算A+。其步骤如下：。其步骤如下：第第1010章章图论图论(GraphTheory)(1)PA(2)k1(3)i1(4)若若pik=1，对，对j=1,2,n作作pijpij pkj(5)ii+1，若，若in则转则转(4)(6)kk+1，若，若kn则转到则转到(3)，否则停止。，否则停止。该算法的关键的一步是该算法的关键的一步是(4)，它判定如果，它判定如果pik=1，将第将第i行和第行和第k行的各对应元素作布尔和或逻辑加行的各对应元素作布尔和或逻辑加后送到第后送到第i行中去。行中去。第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论10.5.1欧拉图欧拉图(EulerianGraph)10.5.2哈密尔顿图哈密尔顿图(Hamilton-ianGraph)第第1010章章图论图论(GraphTheory)离散数学离散数学图论图论历史上的哥尼斯堡七桥问题是著名的图论问题。历史上的哥尼斯堡七桥问题是著名的图论问题。问问题题是是这这样样的的：18世世纪纪的的东东普普鲁鲁士士有有个个哥哥尼尼斯斯堡堡城城，在在横横贯贯全全城城的的普普雷雷格格尔尔河河两两岸岸和和两两个个岛岛之之间间架架设设了了7座座桥桥，它它们们把把河河的的两两岸岸和和两两个个岛岛连连接接起起来来（如如图图10.4.1）。）。第第1010章章图论图论(GraphTheory)每每逢逢假假日日，城城中中居居民民进进行行环环城城游游玩玩，人人们们对对此此提提出出了了一一个个“遍遍游游”问问题题，即即能能否否有有这这样样一一种种走走法法，使使得得从从某某地地出出发发通通过过且且只只通过每座桥一次后又回到原地呢？通过每座桥一次后又回到原地呢？10.4欧拉图与哈密尔顿图欧拉图与哈密尔顿图第第1010章章图论图论(GraphTheory)我我们们将将图图10.4.1中中的的哥哥尼尼斯斯堡堡城城的的4块块陆陆地地部部分分分分别别标标以以A，B，D，将将陆陆地地设设想想为为图图的的结结点点，而而把把桥桥画画成成相相应应的的连连接接边边，这这