离散数学图论基础知识

1、C CS S| |S SWWU US ST TXDCXDC程序设计领域里，每一个人都想飞。程序设计领域里，每一个人都想飞。但是，还没有学会走之前，连怕跑都别想！但是，还没有学会走之前，连怕跑都别想！勿在浮沙筑高台！勿在浮沙筑高台！20212021年年7 7月月1515日星期四日星期四C CS S| |S SWWU US ST TXDCXDC20212021年年7 7月月1515日星期四日星期四图论基础知识讲解图论基础知识讲解该材料用于图论第该材料用于图论第1 1讲课图论基础知识讲解环节讲课图论基础知识讲解环节C CS S| |S SWWU US ST TXDCXDC图图 论论 图论是组合和离散

2、数学最重要的分支之一图论是组合和离散数学最重要的分支之一,也是计算也是计算机基础理论科学的重要部分。它以图为研究对象。在机基础理论科学的重要部分。它以图为研究对象。在理论计算机科学、运筹学、系统科学和数学中都有重理论计算机科学、运筹学、系统科学和数学中都有重要的地位。要的地位。 而信息科学和生物科学已成为当今科学和经济发展的而信息科学和生物科学已成为当今科学和经济发展的核心和主要动力核心和主要动力,也因此大大推动了以研究离散和组也因此大大推动了以研究离散和组合问题为主要对象的图论的发展合问题为主要对象的图论的发展C CS S| |S SWWU US ST TXDCXDC图图 论论 一个图就是一

3、个离散的拓扑结构一个图就是一个离散的拓扑结构,经常用于描经常用于描述和研究许多领域中的各种问题。述和研究许多领域中的各种问题。 随着计算机科学的飞速发展随着计算机科学的飞速发展,图论组合和算法图论组合和算法的研究在近代也成为计算机科学和数学中发的研究在近代也成为计算机科学和数学中发展最快的基础学科之一展最快的基础学科之一,也受到国际上的学术也受到国际上的学术界和高新技术企业方面特别重视。界和高新技术企业方面特别重视。C CS S| |S SWWU US ST TXDCXDC图图 论论 理论计算机科学中的算法理论经典问题理论计算机科学中的算法理论经典问题(图中点对之图中点对之间最短路间最短路,货

4、郎担问题货郎担问题,图重抅问题图重抅问题,HAMILTON 问问题题,P-NP问题等问题等)，通信网络通讯，通信网络通讯(网络设计网络设计, 通讯速度通讯速度和容量和容量, 网络可靠性和容错性等网络可靠性和容错性等) ； 在基础理论方面的著名四色定理和各种染色问题在基础理论方面的著名四色定理和各种染色问题,极极值理论及树、路和圈问题，值理论及树、路和圈问题，HAMILTON理论等理论等)； 网络流、组合最优化等运筹学问题；任务人员安排等网络流、组合最优化等运筹学问题；任务人员安排等管理科学和系统科学的问题以及在物理管理科学和系统科学的问题以及在物理,化学化学,社会学社会学,语言学语言学,生物学

5、等领域的大量应用问题。生物学等领域的大量应用问题。C CS S| |S SWWU US ST TXDCXDC图图 论论图论中的图是由若干给定的点及连接两点的线所构成的图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字被好多位数学家各

6、自独立地建立过。关于图论的文字记载最早出现在欧拉记载最早出现在欧拉1736年的论着中，他所考虑的原年的论着中，他所考虑的原始问题有很强的实际背景始问题有很强的实际背景 C CS S| |S SWWU US ST TXDCXDC图图 论论图论起源于著名的哥尼斯堡七桥图论起源于著名的哥尼斯堡七桥问题。问题。欧拉证明了这个问题没有解，并欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于且推广了这个问题，给出了对于一个给定的图可以某种方式走遍一个给定的图可以某种方式走遍的判定法则。的判定法则。这项工作使欧拉成为图论这项工作使欧拉成为图论及拓及拓扑学扑学的创始人。的创始人。C CS S| |S S

7、WWU US ST TXDCXDC图图 论论 1859年，英国数学家哈米尔顿发明了一种游戏：用一年，英国数学家哈米尔顿发明了一种游戏：用一个规则的实心十二面体，它的个规则的实心十二面体，它的20个顶点标出世界著名个顶点标出世界著名的的20个城市，要求游戏者找一条沿着各边通过每个顶个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界。点刚好一次的闭回路，即绕行世界。 用图论的语言来说，游戏的目的是在十二面体的图中用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码

8、理论中的很多问题都由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。可以化为哈密顿问题，从而引起广泛的注意和研究。C CS S| |S SWWU US ST TXDCXDC图图 论论在图论的历史中，还有一个最著名的问题在图论的历史中，还有一个最著名的问题四色猜想。四色猜想。这个猜想说，在一个平面或球面上的任何地图这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们个单连通域构成

9、，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。点。四色猜想有一段有趣的历史。C CS S| |S SWWU US ST TXDCXDC图图 论论每个地图可以导出一个图，其中国家都是点，当相应的每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。图理论、代数拓扑图论等分支的发展起到推动作用。

10、四色猜想的提出来自英国。四色猜想的提出来自英国。1852年，毕业于伦敦大学的年，毕业于伦敦大学的弗南西斯弗南西斯.格思里来到一家科研单位搞地图着色工作格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：时，发现了一种有趣的现象：“看来，每幅地图都可看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。不同的颜色。 C CS S| |S SWWU US ST TXDCXDC图图 论论1872年，英国当时最著名的数学家凯利正式向伦敦数学年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数

11、学界学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。四色猜想的大会战。18781880年两年间，著名律师兼数学家肯普和泰勒两年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色人分别提交了证明四色猜想的论文，宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，了。于是

12、，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。其实是一个可与费马猜想相媲美的难题。 C CS S| |S SWWU US ST TXDCXDC图图 论论进入进入20世纪以来，科学家们对四色猜想的证明基本上是世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学年，美国数学家阿佩尔与哈肯在美国伊利诺斯

13、大学的两台不同的电子计算机上，用了的两台不同的电子计算机上，用了1200个小时，作了个小时，作了100亿判断，终于完成了四色定理的证明。亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。为应该有一种简捷明快的书面证明方法。C CS S| |S SWWU US ST TXDCXDC图图 论论对于网络的研究，最早是从数学家开始的，其基本的理对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。论就是图论，它也是目前组合数学领域最活跃的分支。我

14、们在复杂网络的研究中将要遇到的各种类型的网络，我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的无向的、有向的、加权的这些都可以用图论的语这些都可以用图论的语言和符号精确简洁地描述。言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。驾齐驱地成为研究复杂网络的两大解析方法之一。C C

15、S S| |S SWWU US ST TXDCXDC图图8.1 图的基本概念图的基本概念A A、B B、C C、D D四个四个班进行足球比赛，为了表示四个班进行足球比赛，为了表示四个班之间比赛的情况，我们作出如班之间比赛的情况，我们作出如右上图的图形。在该图中的右上图的图形。在该图中的4 4个小个小圆圈分别表示这四个班，称之为圆圈分别表示这四个班，称之为结点。如果两个班进行了比赛，结点。如果两个班进行了比赛，则在两个结点之间用一条线连接则在两个结点之间用一条线连接起来，称之为边。这样，利用图起来，称之为边。这样，利用图形使得各班之间的比赛情况一目形使得各班之间的比赛情况一目了然。了然。C CS

16、 S| |S SWWU US ST TXDCXDC定义定义8.1一个一个图图是一个序偶是一个序偶，记为，记为图的定义图的定义G G，其中：，其中： V Vvv1 1,v,v2 2,v,v3 3, ,v,vn n 是一个有限的非空集合，是一个有限的非空集合，v vi i(i(i1,2,3,1,2,3,n),n)称为称为结点结点, ,简称简称点点，V V为为结结点集点集； E Eee1 1,e,e2 2,e,e3 3, ,e,em m 是一个有限的集合，是一个有限的集合，e ei i(i(i1,2,3,1,2,3,m),m)称为称为边边，E E为为边集边集，E E中的中的每个元素都有每个元素都有V

17、 V中的结点对与之对应。即对任中的结点对与之对应。即对任意意eEeE，都有，都有e e与与VV V V或者或者(u,v)(u,v)V&VV&V相对应。相对应。 C CS S| |S SWWU US ST TXDCXDC在一个图中，关联结点在一个图中，关联结点vi和和vj的边的边e，无论是有向的还，无论是有向的还是无向的，均称边是无向的，均称边e与结点与结点vI和和vj相关联相关联，而，而vi和和vj称为称为邻接点邻接点，否则称为，否则称为不邻接的不邻接的；几个概念几个概念 关联于同一个结点的两条边称为关联于同一个结点的两条边称为邻接边邻接边； 图中关联同一个结点的边称为图中关联同一个结点的边称

18、为环环( (或或自回路自回路) )； 图中不与任何结点相邻接的结点称为图中不与任何结点相邻接的结点称为孤立结点孤立结点； 仅由孤立结点组成的图称为仅由孤立结点组成的图称为零图零图； 仅含一个结点的零图称为仅含一个结点的零图称为平凡图平凡图； 含有含有n n个结点、个结点、m m条边的图条边的图称为称为(n(n，m)m)图图；C CS S| |S SWWU US ST TXDCXDC若边若边e与无序结点对与无序结点对(u，v)相对应，则称边相对应，则称边e为为无向边无向边,记为记为e(u，v)，这时称，这时称u，v是边是边e的两个的两个端点端点；若边若边e与有序结点对与有序结点对相对应，则称边相

19、对应，则称边e为为有向边有向边(或或弧弧)，记为，记为e，这时称，这时称u是边是边e的的始点始点(或或弧弧尾尾).v是边是边e的的终点终点(或或弧头弧头)，统称为，统称为e的的端点端点；每条边都是无向边的图称为每条边都是无向边的图称为无向图无向图；每条边都是有向边的图称为每条边都是有向边的图称为有向图有向图；有些边是无向边，而另一些是有向边的图称为有些边是无向边，而另一些是有向边的图称为混合图混合图。图的分类按边的方向图的分类按边的方向用用小圆圈小圆圈表示表示V V中的中的结点结点，用，用由由u u指向指向v v的的有向线段有向线段表示表示，无向线段无向线段表示表示(u,v)(u,v)。C C

20、S S| |S SWWU US ST TXDCXDC图的分类按边的方向图的分类按边的方向上图所示的三个图分别表示为：上图所示的三个图分别表示为：G G1 1V v)G G2 2V a,b,c,d,e,a,b,c,d,e,G G3 3V 1,2,3,4,5,(1,4),1,2,3,4,5,(1,4),G1G1是无向图，是无向图，G2G2是有向图，是有向图，G3G3是混合图。是混合图。C CS S| |S SWWU US ST TXDCXDC图的分类按边的方向图的分类按边的方向设图设图G如右图所示。如右图所示。这里这里Vv1,v2,v3,v4,v5，Ee1,e2,e3,e4,e5,e6，其中其中e

21、 e1 1(v(v1 1,v,v2 2) )，e e2 2v ，e e3 3(v(v1 1,v,v4 4) )，e e4 4(v(v2 2,v,v3 3) )，e e5 5v ，e e6 6(v(v3 3,v,v3 3) )。图中的图中的e1、e3、e4是无向边，是无向边，e2、e5是有向边。是有向边。 这是一个混合图。这是一个混合图。 C CS S| |S SWWU US ST TXDCXDC在有向图中，两个结点间在有向图中，两个结点间(包括结点自身间包括结点自身间)若有同始点和同终若有同始点和同终点的几条边，则这几条边称为点的几条边，则这几条边称为平行边平行边，在无向图中，两个结点，在无向

22、图中，两个结点间间(包括结点自身间包括结点自身间)若有几条边，则这几条边称为若有几条边，则这几条边称为平行边平行边；两结点两结点vi，vj间相互平行的边的条数称为边间相互平行的边的条数称为边(vi，vj)或或的的重数重数；含有平行边的图称为含有平行边的图称为多重图多重图；非多重图称为；非多重图称为线图线图；无自回路的线图称为无自回路的线图称为简单图简单图。图的分类按边的重数图的分类按边的重数G1G1、G2G2是多重图，是多重图，G3, G4G3, G4是线图，是线图，G4G4是简单图。是简单图。 C CS S| |S SWWU US ST TXDCXDC赋权图赋权图 G是一个三重组是一个三重组

23、或四重组或四重组，其中其中V是结点集合，是结点集合，E是边的集合，是边的集合，f是从是从V到非负到非负实数集合的函数，实数集合的函数，g是从是从E到非负实数集合的函数。到非负实数集合的函数。非赋权图称为非赋权图称为无权图无权图。图的分类按权图的分类按权C CS S| |S SWWU US ST TXDCXDC在无向图在无向图G中，与结点中，与结点v(v V)关联的边的条关联的边的条数（有环时计算两次），称为该结点的数（有环时计算两次），称为该结点的度数度数，记为，记为deg(v)；结点的度数结点的度数 （次数）（次数）在有向图在有向图G中，以结点中，以结点v为始点引出的边的条数，称为该为始点引

24、出的边的条数，称为该结点的结点的出度出度,记为记为deg+(v)；以结点；以结点v为终点引入的边的条数，称为该为终点引入的边的条数，称为该结点的结点的入度入度,记为记为deg-(v)；而结点；而结点的引出度数和引入度数之和称为的引出度数和引入度数之和称为该结点的该结点的度数度数，记为，记为deg(v)，即，即deg(v)deg+(v)+deg-(v)；C CS S| |S SWWU US ST TXDCXDC对于图对于图G，度数为，度数为1的结点称为的结点称为悬挂结点悬挂结点，它所关联的边称为它所关联的边称为悬挂边悬挂边。在图在图G中，称度数为奇数的结点为中，称度数为奇数的结点为奇度数结奇度数

25、结点点，度数为偶数的结点为，度数为偶数的结点为偶度数结点偶度数结点。结点的度数结点的度数 （次数）（次数）v5v5是悬挂结点，是悬挂结点，v1v5为悬挂边。为悬挂边。C CS S| |S SWWU US ST TXDCXDC子图子图定义定义8.7 设有图设有图G和图和图G。若若V V，E E，则称，则称G是是G的的子图子图，记为，记为G G。若若G G，且，且GG（即（即V V或或E E），则称），则称G是是G的的真子图真子图，记为，记为G G。若若V=V，E E，则称，则称G是是G的的生成子图生成子图。1) 设设V V且且V ，以，以V为结点集，以两个端为结点集，以两个端点均在点均在V中的边

26、的全体为边集的中的边的全体为边集的G的子图的子图称为称为V导出的导出的G的子图的子图，简称，简称V的的导出子图导出子图。 C CS S| |S SWWU US ST TXDCXDC在如图中，给出了图在如图中，给出了图G以及它的真子图以及它的真子图G和和生成子图生成子图G G 。GG是结点集是结点集vv1 1，v v2 2，v v3 3，v v4 4，v v5 5 的导出子图。的导出子图。显然，每个图都是它自身的子图。显然，每个图都是它自身的子图。 子图子图C CS S| |S SWWU US ST TXDCXDC完全图完全图设设G为一个具有为一个具有n个结点的无向简单个结点的无向简单图，如果图

27、，如果G中任一个结点都与其余中任一个结点都与其余n-1个结点个结点相邻接，则称相邻接，则称G为为无向完全图无向完全图，简称，简称G为为完全完全图图，记为，记为Kn。设设G为一个具有为一个具有n个结点的有向简单个结点的有向简单图，若对于任意图，若对于任意u,v V(u v)，既有有向边，既有有向边，又有有向边，又有有向边，则称，则称G为为有向完全有向完全图图，在不发生误解的情况下，也记为，在不发生误解的情况下，也记为Kn。C CS S| |S SWWU US ST TXDCXDC完全图完全图无向的简单完全图无向的简单完全图K3，K4，K5和有向的简单和有向的简单完全图完全图K3。无向完全图无向完

28、全图K Kn n的的边数边数为为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的的边数边数为为= n(n-1)= n(n-1)。 2nP2nC21C CS S| |S SWWU US ST TXDCXDC图的同构图的同构图的同构：设两个图图的同构：设两个图G=和和G=，如果，如果存 在 双 射 函 数存 在 双 射 函 数 g ： V V ， 使 得 对 于 任 意 的， 使 得 对 于 任 意 的 e = ( vi, vj) （ 或 者（ 或 者 ） E 当 且 仅 当当 且 仅 当 e =( g ( vi) , g ( vj) ) （ 或 者（ 或 者 ） E ，并 且

29、并 且 e 与与 e 的 重 数 相 同 ， 则 称的 重 数 相 同 ， 则 称 G 与与 G 同 构同 构 ，记为记为G G。 C CS S| |S SWWU US ST TXDCXDC图的同构图的同构容易验证：容易验证：G1 G2，结点之间的对应关系为：，结点之间的对应关系为：av1，bv2，cv3，dv4，ev5；G3 G4；G5 G6；但；但G7与与G8不同构。图不同构。图G5称为彼得森图。称为彼得森图。 C CS S| |S SWWU US ST TXDCXDC图的操作图的操作 定义定义 设图设图G。设设eE，用，用G-e表示从表示从G中去掉边中去掉边e得到的图，称为删除得到的图，

30、称为删除e。又设。又设E E，用，用G-E 表示从表示从G中删除中删除E 中所有边得到的中所有边得到的图，称为图，称为删除删除E 。设设vV，用，用G-v表示从表示从G中去掉结点中去掉结点v及及v关联的所有边关联的所有边得到的图，称为删除结点得到的图，称为删除结点v。又设。又设V V，用，用G-V 表示从表示从G中删除中删除V 中所有结点及关联的所有边得到的图，称为中所有结点及关联的所有边得到的图，称为删除删除V 。设设e(u,v)E，用，用Ge表示从表示从G中删除中删除e，将，将e的两个端的两个端点点u,v用一个新的结点用一个新的结点w代替，使代替，使w关联除关联除e外的外的u和和v关关联的

31、一切边，称为联的一切边，称为边边e的收缩的收缩。一个图。一个图G可以收缩为图可以收缩为图H，是指，是指H可以从可以从G经过若干次边的收缩而得到。经过若干次边的收缩而得到。1) 设设u,vV（u,v可能相邻，也可能不相邻），用可能相邻，也可能不相邻），用G(u,v)表示在表示在u,v之间加一条边之间加一条边(u,v)，称为，称为加新边加新边。 C CS S| |S SWWU US ST TXDCXDC路径与回路路径与回路 v图图G中结点和边相继交错出现的中结点和边相继交错出现的序列序列=v0e1v1e2v2ekvk，若，若中边中边ei的两端的两端点是点是vi-1和和vi（G是有向图时要求是有向图

32、时要求vi-1与与vi分分别是别是ei的始点和终点），则称的始点和终点），则称为结点为结点v0到到结点结点vk的的路径路径。vv0和和vk分别称为此路径的分别称为此路径的始点始点和和终点终点，统，统称为路径的称为路径的端点端点。v路径中边的数目路径中边的数目k称为此称为此路径的长度路径的长度。v当当v0vR时，此路径称为时，此路径称为回路回路。C CS S| |S SWWU US ST TXDCXDC 若路径中的所有边若路径中的所有边e1，e2，ek互不相同，则称此路互不相同，则称此路径为径为简单路径简单路径或一条或一条迹迹；若回路中的所有边；若回路中的所有边e1，e2，ek互不相同，则称此回

33、路为互不相同，则称此回路为简单回路简单回路或一条或一条闭迹闭迹； 若路径中的所有结点若路径中的所有结点v0，v1，vk互不相同（从而所互不相同（从而所有边互不相同），则称此路径为有边互不相同），则称此路径为基本路径基本路径或者或者初级路径初级路径、路径路径；若回路中除；若回路中除v0vk外的所有结点外的所有结点v0，v1，vk-1互不相同（从而所有边互不相同），则称此回路为互不相同（从而所有边互不相同），则称此回路为基本基本回路回路或者或者初级回路初级回路、圈圈。 基本路径基本路径(或基本回路或基本回路)一定是简单路径一定是简单路径(或简单回路或简单回路)，但反之则不一定。但反之则不一定。简单

34、路径与基本路径简单路径与基本路径 C CS S| |S SWWU US ST TXDCXDC注意：注意：在 不 会 引 起 误 解 的 情 况 下 ， 一 条 路 径在 不 会 引 起 误 解 的 情 况 下 ， 一 条 路 径v0e1v1e2v2envn也可以用边的序列也可以用边的序列e1e2en来表来表示，这种表示方法对于有向图来说较为方便。示，这种表示方法对于有向图来说较为方便。在简单图中，一条路径在简单图中，一条路径v0e1v1e2v2envn也可以也可以用结点的序列用结点的序列v0v1v2vn来表示。来表示。在路径与回路的定义中，我们将回路定义为路在路径与回路的定义中，我们将回路定义

35、为路径的特殊情况。因而，我们说某条路径，它可径的特殊情况。因而，我们说某条路径，它可能是回路。但当我们说一基本路径时，一般是能是回路。但当我们说一基本路径时，一般是指它不是基本回路的情况。指它不是基本回路的情况。C CS S| |S SWWU US ST TXDCXDC在图在图G中，对中，对 vi，vj V，如果从，如果从短程线、距离短程线、距离v vi i到到v vj j存在路径，则称长度最短的路径为从存在路径，则称长度最短的路径为从v vi i到到v vj j的的短程线短程线，从，从v vi i到到v vj j的短程线的长度称为从的短程线的长度称为从v vi i到到v vj j的的距离距离

36、，记为，记为d(vd(vi i,v,vj j) )。d(vd(vi i，v vj j) )满足下列性质：满足下列性质：d(vd(vi i,v,vj j) )0 0；d(vd(vi i,v,vi i) )0 0；d(vd(vi i,v,vk k)+d(v)+d(vk k，v vj j) )d(vd(vi i，v vj j) )；( (三角不等式三角不等式) )d(vd(vi i,v,vj j) ) ( (当当v vi i到到v vj j不存在路径时不存在路径时) )。C CS S| |S SWWU US ST TXDCXDC在在(a)中有：中有：d(vd(v2 2,v,v1 1) )1 1， d

37、(vd(v3 3,v,v1 1) )2 2，d(vd(v1 1,v,v4 4) )3 3， d(vd(v1 1,v,v2 2) )2 2， d(vd(v1 1,v,v3 3) )4 4，d(vd(v4 4,v,v1 1) )3 3；在在(b)(b)中有：中有：d(vd(v1 1,v,v3 3) )2 2， d(vd(v3 3,v,v7 7) )3 3，d(vd(v1 1,v,v7 7) )4 4。短程线、距离短程线、距离C CS S| |S SWWU US ST TXDCXDC可达可达定义定义设设u,v为图为图G中的两个结点，若存在从结点中的两个结点，若存在从结点u到到结点结点v的路径，则称从

38、结点的路径，则称从结点u到结点到结点v是是可达的可达的，记为，记为uv。对任意结点。对任意结点u，规定，规定uu。定理定理无向图中结点之间的连通关系是等价关系。无向图中结点之间的连通关系是等价关系。证明证明 1 1）自反性：自反性：2 2）对称性：对称性：3 3）传递性：传递性：由由1 1）、）、2 2）、）、3 3）知，结点之间的连通关系是等）知，结点之间的连通关系是等价关系。价关系。 C CS S| |S SWWU US ST TXDCXDC有向图结点之间的可达关系具有向图结点之间的可达关系具有有自反性自反性和和传递性传递性，但一般说来，但一般说来，可达关系可达关系没有对称性没有对称性。例

39、如右图中。例如右图中v v3 3到到v v2 2可达，但可达，但v v2 2到到v v3 3不可达。因不可达。因此，可达关系此，可达关系不是等价关系不是等价关系。可达可达C CS S| |S SWWU US ST TXDCXDC定义定义若无向图若无向图G中任意两个结点都是连通的，中任意两个结点都是连通的，则称则称G是是连通图连通图，否则则称，否则则称G是非连通图是非连通图(或或分离图分离图)。无向完全图无向完全图Kn（n1）都是连通图，而多于一个结点的零）都是连通图，而多于一个结点的零图都是非连通图。图都是非连通图。定义定义无向图无向图G中的每个连通的划分块称为中的每个连通的划分块称为G的一个

40、的一个连通连通分支分支，用，用p(G)表示表示G中的中的连通分支个数连通分支个数。无向图无向图G是连通图当且仅当是连通图当且仅当p(G)1。无向图的连通图无向图的连通图C CS S| |S SWWU US ST TXDCXDC有向图的连通性有向图的连通性 定义定义 设设G是一个有向图，略去是一个有向图，略去G中所有中所有有向边的方向得无向图有向边的方向得无向图G，如果无向图，如果无向图G是连是连通图，则称有向图通图，则称有向图G是是连通图连通图或称为或称为弱连通图弱连通图。否则称否则称G是非连通图是非连通图。G G1 1、G G2 2、G G3 3是连通的有向图是连通的有向图G G4 4是非连

41、通的有向图是非连通的有向图C CS S| |S SWWU US ST TXDCXDC定义定义 设有向图设有向图G是连通图，是连通图，若若G中任何一对结点之间至少有一个结点到另中任何一对结点之间至少有一个结点到另一个结点是可达的，则称一个结点是可达的，则称G是是单向连通图单向连通图；1) 若若G中任何一对结点之间都是相互可达的，则中任何一对结点之间都是相互可达的，则称称G是是强连通图强连通图。 有向图的连通性有向图的连通性v若有向图若有向图G G是强连通图，则它必是单向连通图；是强连通图，则它必是单向连通图；v若有向图若有向图G G是单向连通图，则它必是（弱）连通是单向连通图，则它必是（弱）连通

42、图。图。v但是上述二命题的逆均不成立。但是上述二命题的逆均不成立。 C CS S| |S SWWU US ST TXDCXDC有向图的连通性有向图的连通性 G3是强连通图（当然它也是单向连通图和弱连是强连通图（当然它也是单向连通图和弱连通图）；通图）； G2是单向连通图（当然它也是弱连通图）；是单向连通图（当然它也是弱连通图）； G1是弱连通图。是弱连通图。 C CS S| |S SWWU US ST TXDCXDC定义定义 在有向图在有向图G中，设中，设G是是G的的弱分图、单向分图、强分图弱分图、单向分图、强分图子图，如果子图，如果1 1）GG是是强连通的强连通的（单向连通的单向连通的、弱连

43、通的弱连通的）；）；2 2）对任意）对任意G G“ G G，若，若G G G G”，则，则G G“不是不是强连通强连通 的的（单向连通的单向连通的、弱连通的弱连通的）。）。那么称那么称GG为为G G的的强连通分支强连通分支（单向连通分支单向连通分支、弱弱连通分支连通分支），或称为），或称为强分图强分图（单向分图单向分图、弱分弱分图图）。）。显然，如果不考虑边的方向，弱连通分支对显然，如果不考虑边的方向，弱连通分支对应相应的无向图的连通分支。应相应的无向图的连通分支。C CS S| |S SWWU US ST TXDCXDC在图在图G1中，中，弱分图、单向分图、强分图弱分图、单向分图、强分图 由

44、由vv2 2 ，vv6 6 和和vv1 1,v,v3 3,v,v4 4,v,v5 5,v,v7 7 导出的子图导出的子图都是强连通分支；都是强连通分支； 由由vv1 1,v,v2 2,v,v3 3,v,v4 4,v,v5 5,v,v7 7 和和vv1 1,v,v3 3,v,v4 4,v,v5 5,v,v6 6,v,v7 7 导出的子图都是单向连通分支；导出的子图都是单向连通分支； G G1 1本身为弱连通分支。本身为弱连通分支。在图在图G G2 2中，中， 由由vv1 1 ，vv2 2 ，vv3 3 ，vv4 4 和和vv5 5,v,v6 6,v,v7 7 导出导出的子图都是强连通分支；的子图

45、都是强连通分支； 由由vv1 1,v,v2 2,v,v4 4 ，vv1 1,v,v3 3,v,v4 4 和和vv5 5,v,v6 6,v,v7 7 导出的导出的子图都是单向连通分支；子图都是单向连通分支； 由由vv1 1,v,v2 2,v,v3 3,v,v4 4 和和vv5 5,v,v6 6,v,v7 7 导出的子图都是导出的子图都是弱连通分支。弱连通分支。 C CS S| |S SWWU US ST TXDCXDC在图在图(a)中，结点中，结点v1，v2，v3，v4-仅位于强分图仅位于强分图 v1，v2，v3，v4弱分图、单向分图、强分图弱分图、单向分图、强分图中，结点中，结点v v5 5-

46、仅位于强分图仅位于强分图 v v5 5 中，但边中，但边v 、v 都不位都不位于强分图中；于强分图中； 结点结点v v1 1，v v2 2，v v3 3，v v4 4，v v5 5-仅位于单向分图仅位于单向分图 v v1 1，v v2 2，v v3 3，v v4 4，v v5 5 ，所有的边也都仅位于单向分图中；，所有的边也都仅位于单向分图中； 结点结点v v1 1，v v2 2，v v3 3，v v4 4，v v5 5-仅位于弱分图仅位于弱分图 v v1 1，v v2 2，v v3 3，v v4 4，v v5 5 ；所有的边也都仅位于弱分图；所有的边也都仅位于弱分图中。中。在图在图(b)(b

47、)中，结点中，结点v v2 2，v v3 3-和边和边v 同时位于两个单向分图同时位于两个单向分图 v v1 1，v v2 2，v v3 3 和和vv2 2，v v3 3，v v4 4 中。中。C CS S| |S SWWU US ST TXDCXDC一个等价关系一个等价关系若在有向图若在有向图G的结点集的结点集V上定义二元关上定义二元关系系R R为：为：vRR当且仅当当且仅当v vi i和和v vj j在同一强（弱）连通分支中，在同一强（弱）连通分支中， v vi i,v,vj jVV。显然，显然，R是一个是一个等价关系等价关系。因为每一个结点因为每一个结点v vi i和自身总在在同一强（弱

48、）连通分支中，和自身总在在同一强（弱）连通分支中，所以所以R R是是自反自反的；的；若结点若结点v vi i和和v vj j在同一强（弱）连通分支中，显然在同一强（弱）连通分支中，显然v vj j和和v vi i也在也在同一强（弱）连通分支中，所以同一强（弱）连通分支中，所以R R是是对称对称的；的；又若结点又若结点v vi i和和v vj j在同一强（弱）连通分支中，结点在同一强（弱）连通分支中，结点v vj j和和v vk k在同一强（弱）连通分支中，则在同一强（弱）连通分支中，则v vi i和和v vj j相互可达，相互可达，v vj j和和v vk k相互可达，因而相互可达，因而v v

49、i i和和v vk k相互可达，故相互可达，故v vi i和和v vk k在同一强（弱）在同一强（弱）连通分支中，所以连通分支中，所以R R是是传递传递的。的。C CS S| |S SWWU US ST TXDCXDC图的矩阵表示图的矩阵表示定义定义设设G G是一个线图，是一个线图，V Vvv1 1, ,v v2 2, ,v,vn n ，E Eee1 1,e,e2 2, ,e,en n ，则，则n n阶方阵阶方阵A A(a(aijij) )n n n n称为称为G G的的邻接矩阵邻接矩阵。其中：。其中：v邻接矩阵是一个邻接矩阵是一个布尔矩阵布尔矩阵v无向线图的邻接矩阵是对称的无向线图的邻接矩阵

50、是对称的v而有向线图的邻接矩阵不一定对称而有向线图的邻接矩阵不一定对称 E)v,v(Ev,v, 0E)v,v(Ev,v, 1ajijijijiij或或或或C CS S| |S SWWU US ST TXDCXDC邻接矩阵：邻接矩阵：， 0011011011011010)G(A1。 1000000101010110)G(A2图的矩阵表示图的矩阵表示C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质设设G是一个线图，则有：是一个线图，则有： 当有向线图代表关系时，其邻接矩阵就是前当有向线图代表关系时，其邻接矩阵就是前面讲过的关系矩阵。面讲过的关系矩阵。 零图的邻

51、接矩阵的元素全为零，并称它为零零图的邻接矩阵的元素全为零，并称它为零矩阵。矩阵。 图的每一结点都有自回路而再无其他边时，图的每一结点都有自回路而再无其他边时，则该图的邻接矩阵是单位矩阵。则该图的邻接矩阵是单位矩阵。 简单图的邻接矩阵主对角元全为零。简单图的邻接矩阵主对角元全为零。C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质设无向图设无向图G，Vv1,v2,vn的邻接的邻接矩阵矩阵A(aij)nn，则，则，iin1kkiiin1kikiaaaa)vdeg( n1in1iiin1kikn1in1iiin1kikiaa)aa()vdeg(；， 0011011

52、011011010)G(A1C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质 设有向图设有向图G G，V Vvv1 1,v,v2 2, ,v,vn n 的邻接的邻接矩阵矩阵A A(a(aijij) )n nn n，则，则 n1kkiin1kikia)v(dega)v(deg，。 1000000101010110)G(A2C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质设图设图G，Vv1,v2,vn的邻接矩阵的邻接矩阵A(aij)nn，则则aij表示从结点表示从结点vi到结点到结点vj长度为长度为1的路径数目，而的路径数

53、目，而A中所有元素之中所有元素之和为和为A中长度为中长度为1的路径（包括回路）数目（若的路径（包括回路）数目（若G是有向图，它也是有向图，它也是边的数目；是边的数目；若若G是无向图，它是边的数目的二倍减去是无向图，它是边的数目的二倍减去G中自回路的数目，因为中自回路的数目，因为当当aii=1时，一条边时，一条边(vi,vj)即是一条从即是一条从vi到到vj的长度为的长度为1的路径，也是的路径，也是一条从一条从vj到到vi的长度为的长度为1的路径，而的路径，而(vi,vi)只是一条长度为只是一条长度为1的路径，的路径，而不能再看作两条）。而不能再看作两条）。 ， 0011011011011010

54、)G(A1C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质 令令B(bij)A AA(aij(2)n n，则有：，则有： n1kkjik)2(ijijaaab此时，此时，b bijij表示从表示从v vi i到到v vj j长度为长度为2 2的路径数目，如的路径数目，如b bijij0 0，则无长度为则无长度为2 2的路径，而的路径，而b biiii表示经过表示经过v vi i的长度为的长度为2 2的回路的回路数目；数目； 为为G G中长度为中长度为2 2的路径（含回路）总数，主对的路径（含回路）总数，主对角线上元素之和角线上元素之和 为为G G中长度为中

55、长度为2 2的回路总数。的回路总数。 nn(2)iji 1j 1a n(2)iii 1a C CS S| |S SWWU US ST TXDCXDC邻接矩阵的性质邻接矩阵的性质10)令令C(cij)AmAAA(aij(m)n n，则，则有：有： n1kkj)1m(n1k)1m(ik)m(ijaaaaacikkjij此时，此时，c cijij表示从表示从v vi i到到v vj j长度为长度为m m的路径数目，如的路径数目，如c cijij0 0，则无长度为则无长度为m m的路径，而的路径，而c ciiii给出了经过给出了经过v vi i的长度为的长度为m m的回的回路数目。路数目。 为为G G

56、中长度为中长度为m m的路径（含回路）总数，主对角的路径（含回路）总数，主对角线上元素之和线上元素之和 为为G G中长度为中长度为m m的回路总数。的回路总数。 nn(m)iji 1j 1a n(m)iii 1a C CS S| |S SWWU US ST TXDCXDC例例G1中长度为中长度为2的路径（含回路）总数为的路径（含回路）总数为21，其中，其中9条为回路。条为回路。G1中长度为中长度为3的路径（含回路）总数为的路径（含回路）总数为48，其中，其中10条为回路。条为回路。2121111311(A(G )11211112 44(2)iji 1j 1a21 4(2)iii=1a= 910

57、1011011A(G ) =011011003124234344A G=2432342244(3)iji=1j=1a= 48 4(3)iii=1a=10C CS S| |S SWWU US ST TXDCXDC例例G2中长度为中长度为2的路径（含回路）总数为的路径（含回路）总数为11，其中，其中5条为回路。条为回路。G2中长度为中长度为3的路径（含回路）总数为的路径（含回路）总数为16，其中，其中3条为回路。条为回路。 201101011A(G ) =100000012220111111(A(G ) =0110000144(2)iji=1j=1a=11 4(2)iii=1a= 53212212

58、012(A(G ) =2011000144(3)iji=1j=1a=16 4(3)iii=1a= 3C CS S| |S SWWU US ST TXDCXDC可达性矩阵可达性矩阵定义定义 设设G是一个线图，其中是一个线图，其中Vv1,v2,vn，并假定结点已经有了从，并假定结点已经有了从v1到到vn的的次序，定义相应的次序，定义相应的n阶方阵阶方阵P(pij)nn，其中，其中 ，否否则则的的通通路路至至少少存存在在一一条条非非零零长长度度到到，0vv1pjiij(i(i，j j1 1，2 2，3 3，n)n)称矩阵称矩阵P P为图为图G G的的可达性矩阵可达性矩阵。无向图的可达性矩阵是对称的，而有向图的无向图的可达性矩阵是对称的，而有向图的可达性矩阵则不一定对