离散数学图论基础知识

1、程序设计领域里，每一个人都想飞。 但是，还没有学会走之前，连怕跑都别想！,勿在浮沙筑高台！,2020年7月23日星期四,2020年7月23日星期四,图论基础知识讲解,该材料用于图论第1讲课图论基础知识讲解环节,图 论,图论是组合和离散数学最重要的分支之一,也是计算机基础理论科学的重要部分。它以图为研究对象。在理论计算机科学、运筹学、系统科学和数学中都有重要的地位。 而信息科学和生物科学已成为当今科学和经济发展的核心和主要动力,也因此大大推动了以研究离散和组合问题为主要对象的图论的发展,图 论,一个图就是一个离散的拓扑结构,经常用于描述和研究许多领域中的各种问题。 随着计算机科学的飞速发展,图论

2、组合和算法的研究在近代也成为计算机科学和数学中发展最快的基础学科之一,也受到国际上的学术界和高新技术企业方面特别重视。,图 论,理论计算机科学中的算法理论经典问题(图中点对之间最短路,货郎担问题,图重抅问题,hamilton 问题,p-np问题等)，通信网络通讯(网络设计, 通讯速度和容量, 网络可靠性和容错性等) ； 在基础理论方面的著名四色定理和各种染色问题,极值理论及树、路和圈问题，hamilton理论等)； 网络流、组合最优化等运筹学问题；任务人员安排等管理科学和系统科学的问题以及在物理,化学,社会学,语言学,生物学等领域的大量应用问题。,图 论,图论中的图是由若干给定的点及连接两点的

3、线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景,图 论,图论起源于著名的哥尼斯堡七桥问题。,欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。 这项工作使欧拉成为图论及拓扑学的创始人。,图 论,1859年，英国数学家哈米尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要

4、求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界。 用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。,图 论,在图论的历史中，还有一个最著名的问题四色猜想。 这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。,图 论,每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻

5、时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。 四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。,图 论,1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。 18781880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了

6、四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。,图 论,进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。 1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。 不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。,图 论,对于网

7、络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的这些都可以用图论的语言和符号精确简洁地描述。 图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。,图,8.1 图的基本概念,a、b、c、d四个 班进行足球比赛，为了表示四个班之间比赛的情况，我们作出如右上图的图形。在该图中的4个小圆圈分别表示这四个班，称之为结点。如果两个班进行了比赛，则在两个结点之间用一

8、条线连接起来，称之为边。这样，利用图形使得各班之间的比赛情况一目了然。,定义8.1一个图是一个序偶，记为,图的定义,g，其中： vv1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，v为结点集； ee1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，e为边集，e中的每个元素都有v中的结点对与之对应。即对任意ee，都有e与vv或者(u,v) v&v相对应。,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vi和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,几个概念,关联于同一个结点的两条边称为邻接边； 图

9、中关联同一个结点的边称为环(或自回路)； 图中不与任何结点相邻接的结点称为孤立结点； 仅由孤立结点组成的图称为零图； 仅含一个结点的零图称为平凡图； 含有n个结点、m条边的图 称为(n，m)图；,若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点； 若边e与有序结点对相对应，则称边e为有向边(或弧)，记为e，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点； 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。,图的分类按边的方向,用小圆圈表示v中的结点，用

10、由u指向v的有向线段表示，无向线段表示(u,v)。,图的分类按边的方向,上图所示的三个图分别表示为：,g1 g2, , g3,(1,4), ,g1是无向图，g2是有向图，g3是混合图。,图的分类按边的方向,设图g如右图所示。这里 vv1,v2,v3,v4,v5， ee1,e2,e3,e4,e5,e6， 其中,e1(v1,v2)，e2，e3(v1,v4)， e4(v2,v3)，e5，e6(v3,v3)。,图中的e1、e3、e4是无向边，e2、e5是有向边。,这是一个混合图。,在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点

11、自身间)若有几条边，则这几条边称为平行边； 两结点vi，vj间相互平行的边的条数称为边(vi，vj)或的重数； 含有平行边的图称为多重图；非多重图称为线图； 无自回路的线图称为简单图。,图的分类按边的重数,g1、g2是多重图，g3, g4是线图，g4是简单图。,赋权图 g是一个三重组或四重组，其中v是结点集合，e是边的集合，f是从v到非负实数集合的函数，g是从e到非负实数集合的函数。非赋权图称为无权图。,图的分类按权,在无向图g中，与结点v(vv)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；,结点的度数 （次数）,在有向图g中，以结点v为始点引出的边的条数，称为该结点

12、的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；,对于图g，度数为1的结点称为悬挂结点，它所关联的边称为悬挂边。 在图g中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。,结点的度数 （次数）,v5是悬挂结点，为悬挂边。,子图,定义8.7 设有图g和图g。 若vv，ee，则称g是g的子图，记为gg。 若gg，且gg（即vv或ee），则称g是g的真子图，记为gg。 若v=v，ee，则称g是g的生成子图。 设vv且v，以v为

13、结点集，以两个端点均在v中的边的全体为边集的g的子图称为v导出的g的子图，简称v的导出子图。,在如图中，给出了图g以及它的真子图g和,生成子图g 。g是结点集v1，v2，v3，v4，v5 的导出子图。 显然，每个图都是它自身的子图。,子图,完全图,设g为一个具有n个结点的无向简单图，如果g中任一个结点都与其余n-1个结点相邻接，则称g为无向完全图，简称g为完全图，记为kn。 设g为一个具有n个结点的有向简单图，若对于任意u,vv(uv)，既有有向边，又有有向边，则称g为有向完全图，在不发生误解的情况下，也记为kn。,完全图,无向的简单完全图k3，k4，k5和有向的简单完全图k3。,无向完全图k

14、n的边数为=n(n-1)，有向完全图kn的边数为= n(n-1)。,图的同构,图的同构：设两个图g=和g=，如果 存在双射函数g：vv，使得对于任意的e =(vi,vj)（或者）e当且仅当e= (g(vi),g(vj)（或者）e， 并且e与e的重数相同，则称g与g同构， 记为gg。,图的同构,容易验证：g1g2，结点之间的对应关系为：av1，bv2，cv3，dv4，ev5；g3g4；g5g6；但g7与g8不同构。图g5称为彼得森图。,图的操作,定义 设图g。 设ee，用g-e表示从g中去掉边e得到的图，称为删除e。又设ee，用g-e表示从g中删除e中所有边得到的图，称为删除e。 设vv，用g-

15、v表示从g中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设vv，用g-v 表示从g中删除v中所有结点及关联的所有边得到的图，称为删除v。 设e(u,v)e，用ge表示从g中删除e，将e的两个端点u,v用一个新的结点w代替，使w关联除e外的u和v关联的一切边，称为边e的收缩。一个图g可以收缩为图h，是指h可以从g经过若干次边的收缩而得到。 设u,vv（u,v可能相邻，也可能不相邻），用g(u,v)表示在u,v之间加一条边(u,v)，称为加新边。,路径与回路,图g中结点和边相继交错出现的序列=v0e1v1e2v2ekvk，若中边ei的两端点是vi-1和vi（g是有向图时要求vi-1与vi

16、分别是ei的始点和终点），则称为结点v0到结点vk的路径。 v0和vk分别称为此路径的始点和终点，统称为路径的端点。 路径中边的数目k称为此路径的长度。 当v0vr时，此路径称为回路。,若路径中的所有边e1，e2，ek互不相同，则称此路径为简单路径或一条迹；若回路中的所有边e1，e2，ek互不相同，则称此回路为简单回路或一条闭迹； 若路径中的所有结点v0，v1，vk互不相同（从而所有边互不相同），则称此路径为基本路径或者初级路径、路径；若回路中除v0vk外的所有结点v0，v1，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者初级回路、圈。 基本路径(或基本回路)一定是简单路径(

17、或简单回路)，但反之则不一定。,简单路径与基本路径,注意：,在不会引起误解的情况下，一条路径v0e1v1e2v2envn也可以用边的序列e1e2en来表示，这种表示方法对于有向图来说较为方便。 在简单图中，一条路径v0e1v1e2v2envn也可以用结点的序列v0v1v2vn来表示。 在路径与回路的定义中，我们将回路定义为路径的特殊情况。因而，我们说某条路径，它可能是回路。但当我们说一基本路径时，一般是指它不是基本回路的情况。,在图g中，对vi，vjv，如果从,短程线、距离,vi到vj存在路径，则称长度最短的路径为从vi到vj的短程线，从vi到vj的短程线的长度称为从vi到vj的距离，记为d(

18、vi,vj)。,d(vi，vj)满足下列性质：,d(vi,vj)0； d(vi,vi)0； d(vi,vk)+d(vk，vj)d(vi，vj)；(三角不等式) d(vi,vj)(当vi到vj不存在路径时)。,在(a)中有：,d(v2,v1)1，d(v3,v1)2，d(v1,v4)3， d(v1,v2)2，d(v1,v3)4，d(v4,v1)3； 在(b)中有： d(v1,v3)2，d(v3,v7)3，d(v1,v7)4。,短程线、距离,可达,定义设u,v为图g中的两个结点，若存在从结点u到结点v的路径，则称从结点u到结点v是可达的，记为uv。对任意结点u，规定uu。,定理无向图中结点之间的连通

19、关系是等价关系。,证明1）自反性： 2）对称性： 3）传递性： 由1）、2）、3）知，结点之间的连通关系是等价关系。,有向图结点之间的可达关系具有自反性和传递性，但一般说来，可达关系没有对称性。例如右图中v3到v2可达，但v2到v3不可达。因此，可达关系不是等价关系。,可达,定义若无向图g中任意两个结点都是连通的，则称g是连通图，否则则称g是非连通图(或分离图)。 无向完全图kn（n1）都是连通图，而多于一个结点的零图都是非连通图。 定义无向图g中的每个连通的划分块称为g的一个连通分支，用p(g)表示g中的连通分支个数。 无向图g是连通图当且仅当p(g)1。,无向图的连通图,有向图的连通性,定

20、义 设g是一个有向图，略去g中所有有向边的方向得无向图g，如果无向图g是连通图，则称有向图g是连通图或称为弱连通图。否则称g是非连通图。,g1、g2、g3是连通的有向图 g4是非连通的有向图,定义 设有向图g是连通图， 若g中任何一对结点之间至少有一个结点到另一个结点是可达的，则称g是单向连通图； 若g中任何一对结点之间都是相互可达的，则称g是强连通图。,有向图的连通性,若有向图g是强连通图，则它必是单向连通图； 若有向图g是单向连通图，则它必是（弱）连通图。 但是上述二命题的逆均不成立。,有向图的连通性,g3是强连通图（当然它也是单向连通图和弱连通图）； g2是单向连通图（当然它也是弱连通图

21、）； g1是弱连通图。,定义 在有向图g中，设g是g的,弱分图、单向分图、强分图,子图，如果 1）g是强连通的（单向连通的、弱连通的）； 2）对任意g“g，若gg”，则g“不是强连通 的（单向连通的、弱连通的）。 那么称g为g的强连通分支（单向连通分支、弱连通分支），或称为强分图（单向分图、弱分图）。,显然，如果不考虑边的方向，弱连通分支对应相应的无向图的连通分支。,在图g1中，,弱分图、单向分图、强分图,由v2，v6和v1,v3,v4,v5,v7导出的子图都是强连通分支； 由v1,v2,v3,v4,v5,v7和v1,v3,v4,v5,v6,v7导出的子图都是单向连通分支； g1本身为弱连通分

22、支。,在图g2中，,由v1，v2，v3，v4和v5,v6,v7导出的子图都是强连通分支； 由v1,v2,v4，v1,v3,v4和v5,v6,v7导出的子图都是单向连通分支； 由v1,v2,v3,v4和v5,v6,v7导出的子图都是弱连通分支。,在图(a)中，结点v1，v2，v3，v4仅位于强分图 v1，v2，v3，v4,弱分图、单向分图、强分图,中，结点v5仅位于强分图 v5 中，但边、都不位于强分图中； 结点v1，v2，v3，v4，v5仅位于单向分图 v1，v2，v3，v4，v5，所有的边也都仅位于单向分图中； 结点v1，v2，v3，v4，v5仅位于弱分图 v1，v2，v3，v4，v5；所有

23、的边也都仅位于弱分图中。 在图(b)中，结点v2，v3和边同时位于两个单向分图 v1，v2，v3和v2，v3，v4中。,一个等价关系,若在有向图g的结点集v上定义二元关系r为：r当且仅当vi和vj在同一强（弱）连通分支中，vi,vjv。显然，r是一个等价关系。,因为每一个结点vi和自身总在在同一强（弱）连通分支中，所以r是自反的；,若结点vi和vj在同一强（弱）连通分支中，显然vj和vi也在同一强（弱）连通分支中，所以r是对称的；,又若结点vi和vj在同一强（弱）连通分支中，结点vj和vk在同一强（弱）连通分支中，则vi和vj相互可达，vj和vk相互可达，因而vi和vk相互可达，故vi和vk在

24、同一强（弱）连通分支中，所以r是传递的。,图的矩阵表示,定义设g是一个线图，vv1, v2,vn，ee1,e2,en，则n阶方阵a(aij)nn称为g的邻接矩阵。其中：,邻接矩阵是一个布尔矩阵 无向线图的邻接矩阵是对称的 而有向线图的邻接矩阵不一定对称,邻接矩阵：,图的矩阵表示,邻接矩阵的性质,设g是一个线图，则有：,当有向线图代表关系时，其邻接矩阵就是前面讲过的关系矩阵。 零图的邻接矩阵的元素全为零，并称它为零矩阵。 图的每一结点都有自回路而再无其他边时，则该图的邻接矩阵是单位矩阵。 简单图的邻接矩阵主对角元全为零。,邻接矩阵的性质,设无向图g，vv1,v2,vn的邻接矩阵a(aij)nn，

25、则,邻接矩阵的性质,设有向图g，vv1,v2,vn的邻接矩阵a(aij)nn，则,邻接矩阵的性质,设图g，vv1,v2,vn的邻接矩阵a(aij)nn， 则aij表示从结点vi到结点vj长度为1的路径数目，而a中所有元素之和为a中长度为1的路径（包括回路）数目（若g是有向图，它也是边的数目； 若g是无向图，它是边的数目的二倍减去g中自回路的数目，因为当aii=1时，一条边(vi,vj)即是一条从vi到vj的长度为1的路径，也是一条从vj到vi的长度为1的路径，而(vi,vi)只是一条长度为1的路径，而不能再看作两条）。,邻接矩阵的性质,令b(bij)aaa(aij(2)nn，则有：,此时，bi

26、j表示从vi到vj长度为2的路径数目，如bij0，则无长度为2的路径，而bii表示经过vi的长度为2的回路数目； 为g中长度为2的路径（含回路）总数，主对角线上元素之和 为g中长度为2的回路总数。,邻接矩阵的性质,10)令c(cij)amaaa(aij(m)nn，则有：,此时，cij表示从vi到vj长度为m的路径数目，如cij0，则无长度为m的路径，而cii给出了经过vi的长度为m的回路数目。 为g中长度为m的路径（含回路）总数，主对角线上元素之和 为g中长度为m的回路总数。,例,g1中长度为2的路径（含回路）总数为21，其中9条为回路。 g1中长度为3的路径（含回路）总数为48，其中10条为回路。,例,g2中长度为2的路径（含回路）总数为11，其中5条