离散数学图论基础知识剖析

11十月2023图论基础知识讲解该材料用于图论第1讲课图论基础知识讲解环节第一页第二页，共63页。图论图论是组合和离散数学最重要的分支之一,也是计算机基础理论科学的重要部分。它以图为研究对象。在理论计算机科学、运筹学、系统科学和数学中都有重要的地位。而信息科学和生物科学已成为当今科学和经济发展的核心和主要动力,也因此大大推动了以研究离散和组合问题为主要对象的图论的发展第二页第三页，共63页。图论一个图就是一个离散的拓扑结构,经常用于描述和研究许多领域中的各种问题。随着计算机科学的飞速发展,图论组合和算法的研究在近代也成为计算机科学和数学中发展最快的基础学科之一,也受到国际上的学术界和高新技术企业方面特别重视。第三页第四页，共63页。图论理论计算机科学中的算法理论经典问题(图中点对之间最短路,货郎担问题,图重抅问题,HAMILTON问题,P-NP问题等)，通信网络通讯(网络设计,通讯速度和容量,网络可靠性和容错性等)；在基础理论方面的著名四色定理和各种染色问题,极值理论及树、路和圈问题，HAMILTON理论等)；网络流、组合最优化等运筹学问题；任务人员安排等管理科学和系统科学的问题以及在物理,化学,社会学,语言学,生物学等领域的大量应用问题。第四页第五页，共63页。图论图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景第五页第六页，共63页。图论图论起源于著名的哥尼斯堡七桥问题。欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。第六页第七页，共63页。图论1859年，英国数学家哈米尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。第七页第八页，共63页。图论在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。第八页第九页，共63页。图论每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。第九页第十页，共63页。图论1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。第十页第十一页，共63页。图论进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。第十一页第十二页，共63页。图论对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。第十二页第十三页，共63页。图8.1图的基本概念A、B、C、D四个班进行足球比赛，为了表示四个班之间比赛的情况，我们作出如右上图的图形。在该图中的4个小圆圈分别表示这四个班，称之为结点。如果两个班进行了比赛，则在两个结点之间用一条线连接起来，称之为边。这样，利用图形使得各班之间的比赛情况一目了然。第十三页第十四页，共63页。定义8.1

一个图是一个序偶<V,E>，记为图的定义G＝<V,E>，其中：V＝{v1,v2,v3,…,vn}是一个有限的非空集合，vi(i＝1,2,3,…,n)称为结点,简称点，V为结点集；E＝{e1,e2,e3,…,em}是一个有限的集合，ei(i＝1,2,3,…,m)称为边，E为边集，E中的每个元素都有V中的结点对与之对应。即对任意e∈E，都有e与<u,v>∈V

V或者(u,v)∈V&V相对应。第十四页第十五页，共63页。在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；几个概念关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；第十五页第十六页，共63页。若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e＝(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对<u，v>相对应，则称边e为有向边(或弧)，记为e＝<u，v>，这时称u是边e的始点(或弧尾).v是边e的终点(或弧头)，统称为e的端点；每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。图的分类－按边的方向用小圆圈表示V中的结点，用由u指向v的有向线段表示<u,v>，无向线段表示(u,v)。第十六页第十七页，共63页。图的分类－按边的方向上图所示的三个图分别表示为：G1＝<V1,E1>＝<{v1,v2,v3,v4}，{(v1,v2),(v2,v3), (v1,v3),(v2,v4),(v1,v4),(v3,v4)}>G2＝<V2,E2>＝<{a,b,c,d,e},{<a,b>,<c,b>, <c,a>,<d,e>}>G3＝<V3,E3>＝<{1,2,3,4,5},{<1,2>,(1,4),<4,3>, <3,5>,<4,5>}>G1是无向图，G2是有向图，G3是混合图。第十七页第十八页，共63页。图的分类－按边的方向设图G＝<V,E>如右图所示。这里V＝{v1,v2,v3,v4,v5}，E＝{e1,e2,e3,e4,e5,e6}，其中e1＝(v1,v2)，e2＝<v1,v3>，e3＝(v1,v4)，e4＝(v2,v3)，e5＝<v3,v2>，e6＝(v3,v3)。图中的e1、e3、e4是无向边，e2、e5是有向边。这是一个混合图。第十八页第十九页，共63页。在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边，在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；两结点vi，vj间相互平行的边的条数称为边(vi，vj)或<vi，vj>的重数；含有平行边的图称为多重图；非多重图称为线图；无自回路的线图称为简单图。图的分类－按边的重数G1、G2是多重图，G3,G4是线图，G4是简单图。第十九页第二十页，共63页。

赋权图G是一个三重组<V,E,g>或四重组<V,E,f,g>，其中V是结点集合，E是边的集合，f是从V到非负实数集合的函数，g是从E到非负实数集合的函数。非赋权图称为无权图。图的分类－按权第二十页第二十一页，共63页。在无向图G＝<V，E>中，与结点v(v

V)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；结点的度数（次数）在有向图G＝<V，E>中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)＝deg+(v)+deg-(v)；第二十一页第二十二页，共63页。对于图G＝<V，E>，度数为1的结点称为悬挂结点，它所关联的边称为悬挂边。在图G＝<V，E>中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。结点的度数（次数）v5是悬挂结点，<v1，v5>为悬挂边。第二十二页第二十三页，共63页。子图定义8.7

设有图G＝<V,E>和图G'＝<V',E'>。若V'

V，E'

E，则称G'是G的子图，记为G'

G。若G'

G，且G'≠G（即V'

V或E'

E），则称G'是G的真子图，记为G'

G。若V'=V，E'

E，则称G'是G的生成子图。设V"

V且V"≠

，以V"为结点集，以两个端点均在V"中的边的全体为边集的G的子图称为V"导出的G的子图，简称V"的导出子图。第二十三页第二十四页，共63页。

在如图中，给出了图G以及它的真子图G'和生成子图G"。G'是结点集{v1，v2，v3，v4，v5}的导出子图。显然，每个图都是它自身的子图。子图第二十四页第二十五页，共63页。完全图设G＝<V,E>为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G＝<V,E>为一个具有n个结点的有向简单图，若对于任意u,v

V(u

v)，既有有向边<u,v>，又有有向边<v,u>，则称G为有向完全图，在不发生误解的情况下，也记为Kn。第二十五页第二十六页，共63页。完全图无向的简单完全图K3，K4，K5和有向的简单完全图K3。无向完全图Kn的边数为=

n(n-1)，有向完全图Kn的边数为=n(n-1)。第二十六页第二十七页，共63页。图的同构图的同构：设两个图G=<V,E>和G'=<V',E'>，如果存在双射函数g：V→V'，使得对于任意的e=(vi,vj)（或者<vi,vj>）∈E当且仅当e'=(g(vi),g(vj))（或者<g(vi),g(vj)>）∈E'，并且e与e'的重数相同，则称G与G'同构，记为G≌G'。第二十七页第二十八页，共63页。图的同构

容易验证：G1≌G2，结点之间的对应关系为：a→v1，b→v2，c→v3，d→v4，e→v5；G3≌G4；G5≌G6；但G7与G8不同构。图G5称为彼得森图。第二十八页第二十九页，共63页。图的操作定义

设图G＝<V,E>。设e∈E，用G-e表示从G中去掉边e得到的图，称为删除e。又设E

E，用G-E

表示从G中删除E

中所有边得到的图，称为删除E

。设v∈V，用G-v表示从G中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设V

V，用G-V

表示从G中删除V

中所有结点及关联的所有边得到的图，称为删除V

。设e＝(u,v)∈E，用G\e表示从G中删除e，将e的两个端点u,v用一个新的结点w代替，使w关联除e外的u和v关联的一切边，称为边e的收缩。一个图G可以收缩为图H，是指H可以从G经过若干次边的收缩而得到。设u,v∈V（u,v可能相邻，也可能不相邻），用G∪(u,v)表示在u,v之间加一条边(u,v)，称为加新边。第二十九页第三十页，共63页。路径与回路图G＝<V,E>中结点和边相继交错出现的序列Γ=v0e1v1e2v2…ekvk，若Γ中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点），则称Γ为结点v0到结点vk的路径。v0和vk分别称为此路径的始点和终点，统称为路径的端点。路径中边的数目k称为此路径的长度。当v0＝vR时，此路径称为回路。第三十页第三十一页，共63页。若路径中的所有边e1，e2，…，ek互不相同，则称此路径为简单路径或一条迹；若回路中的所有边e1，e2，…，ek互不相同，则称此回路为简单回路或一条闭迹；若路径中的所有结点v0，v1，…，vk互不相同（从而所有边互不相同），则称此路径为基本路径或者初级路径、路径；若回路中除v0＝vk外的所有结点v0，v1，…，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者初级回路、圈。基本路径(或基本回路)一定是简单路径(或简单回路)，但反之则不一定。简单路径与基本路径第三十一页第三十二页，共63页。注意：在不会引起误解的情况下，一条路径v0e1v1e2v2…envn也可以用边的序列e1e2…en来表示，这种表示方法对于有向图来说较为方便。在简单图中，一条路径v0e1v1e2v2…envn也可以用结点的序列v0v1v2…vn来表示。在路径与回路的定义中，我们将回路定义为路径的特殊情况。因而，我们说某条路径，它可能是回路。但当我们说一基本路径时，一般是指它不是基本回路的情况。第三十二页第三十三页，共63页。在图G＝<V，E>中，对

vi，vj

V，如果从短程线、距离vi到vj存在路径，则称长度最短的路径为从vi到vj的短程线，从vi到vj的短程线的长度称为从vi到vj的距离，记为d(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不存在路径时)。第三十三页第三十四页，共63页。在(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。短程线、距离第三十四页第三十五页，共63页。可达定义设u,v为图G＝<V,E>中的两个结点，若存在从结点u到结点v的路径，则称从结点u到结点v是可达的，记为u→v。对任意结点u，规定u→u。定理

无向图中结点之间的连通关系是等价关系。证明 1）自反性：……

2）对称性：……

3）传递性：……由1）、2）、3）知，结点之间的连通关系是等价关系。第三十五页第三十六页，共63页。有向图结点之间的可达关系具有自反性和传递性，但一般说来，可达关系没有对称性。例如右图中v3到v2可达，但v2到v3不可达。因此，可达关系不是等价关系。可达第三十六页第三十七页，共63页。定义若无向图G＝<V，E>中任意两个结点都是连通的，则称G是连通图，否则则称G是非连通图(或分离图)。无向完全图Kn（n≥1）都是连通图，而多于一个结点的零图都是非连通图。定义无向图G中的每个连通的划分块称为G的一个连通分支，用p(G)表示G中的连通分支个数。无向图G＝<V，E>是连通图当且仅当p(G)＝1。无向图的连通图第三十七页第三十八页，共63页。有向图的连通性定义

设G＝<V,E>是一个有向图，略去G中所有有向边的方向得无向图G'，如果无向图G'是连通图，则称有向图G是连通图或称为弱连通图。否则称G是非连通图。G1、G2、G3是连通的有向图G4是非连通的有向图第三十八页第三十九页，共63页。定义

设有向图G＝<V,E>是连通图，若G中任何一对结点之间至少有一个结点到另一个结点是可达的，则称G是单向连通图；若G中任何一对结点之间都是相互可达的，则称G是强连通图。有向图的连通性若有向图G是强连通图，则它必是单向连通图；若有向图G是单向连通图，则它必是（弱）连通图。但是上述二命题的逆均不成立。第三十九页第四十页，共63页。有向图的连通性G3是强连通图（当然它也是单向连通图和弱连通图）；G2是单向连通图（当然它也是弱连通图）；G1是弱连通图。第四十页第四十一页，共63页。定义

在有向图G＝<V,E>中，设G'是G的弱分图、单向分图、强分图子图，如果

1）G'是强连通的（单向连通的、弱连通的）；

2）对任意G“

G，若G‘

G”，则G“不是强连通

的（单向连通的、弱连通的）。那么称G'为G的强连通分支（单向连通分支、弱连通分支），或称为强分图（单向分图、弱分图）。显然，如果不考虑边的方向，弱连通分支对应相应的无向图的连通分支。第四十一页第四十二页，共63页。在图G1中，弱分图、单向分图、强分图由{v2}，{v6}和{v1,v3,v4,v5,v7}导出的子图都是强连通分支；由{v1,v2,v3,v4,v5,v7}和{v1,v3,v4,v5,v6,v7}导出的子图都是单向连通分支；G1本身为弱连通分支。在图G2中，由{v1}，{v2}，{v3}，{v4}和{v5,v6,v7}导出的子图都是强连通分支；由{v1,v2,v4}，{v1,v3,v4}和{v5,v6,v7}导出的子图都是单向连通分支；由{v1,v2,v3,v4}和{v5,v6,v7}导出的子图都是弱连通分支。第四十二页第四十三页，共63页。在图(a)中，结点v1，v2，v3，v4­仅位于强分图{v1，v2，v3，v4}弱分图、单向分图、强分图中，结点v5­仅位于强分图{v5}中，但边<v4，v5>、<v3，v5>都不位于强分图中；结点v1，v2，v3，v4，v5­仅位于单向分图{v1，v2，v3，v4，v5}，所有的边也都仅位于单向分图中；结点v1，v2，v3，v4，v5­仅位于弱分图{v1，v2，v3，v4，v5}；所有的边也都仅位于弱分图中。在图(b)中，结点v2，v3­和边<v2，v3>同时位于两个单向分图{v1，v2，v3}和{v2，v3，v4}中。第四十三页第四十四页，共63页。一个等价关系若在有向图G＝<V,E>的结点集V上定义二元关系R为：<vi,vj>∈R当且仅当vi和vj在同一强（弱）连通分支中，

vi,vj∈V。显然，R是一个等价关系。因为每一个结点vi和自身总在在同一强（弱）连通分支中，所以R是自反的；若结点vi和vj在同一强（弱）连通分支中，显然vj和vi也在同一强（弱）连通分支中，所以R是对称的；又若结点vi和vj在同一强（弱）连通分支中，结点vj和vk在同一强（弱）连通分支中，则vi和vj相互可达，vj和vk相互可达，因而vi和vk相互可达，故vi和vk在同一强（弱）连通分支中，所以R是传递的。第四十四页第四十五页，共63页。图的矩阵表示定义

设G＝<V,E>是一个线图，V＝{v1,v2,…,vn}，E＝{e1,e2,…,en}，则n阶方阵A＝(aij)n

n称为G的邻接矩阵。其中：邻接矩阵是一个布尔矩阵无向线图的邻接矩阵是对称的而有向线图的邻接矩阵不一定对称第四十五页第四十六页，共63页。邻接矩阵：图的矩阵表示第四十六页第四十七页，共63页。邻接矩阵的性质设G＝<V，E>是一个线图，则有：当有向线图代表关系时，其邻接矩阵就是前面讲过的关系矩阵。零图的邻接矩阵的元素全为零，并称它为零矩阵。图的每一结点都有自回路而再无其他边时，则该图的邻接矩阵是单位矩阵。简单图的邻接矩阵主对角元全为零。第四十七页第四十八页，共63页。邻接矩阵的性质设无向图G＝<V,E>，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则第四十八页第四十九页，共63页。邻接矩阵的性质设有向图G＝<V,E>，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则第四十九页第五十页，共63页。邻接矩阵的性质设图G＝<V,E>，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n， 则aij表示从结点vi到结点vj长度为1的路径数目，而A中所有元素之和为A中长度为1的路径（包括回路）数目（若G是有向图，它也是边的数目； 若G是无向图，它是边的数目的二倍减去G中自回路的数目，因为当aii=1时，一条边(vi,vj)即是一条从vi到vj的长度为1的路径，也是一条从vj到vi的长度为1的路径，而(vi,vi)只是一条长度为1的路径，而不能再看作两条）。第五十页第五十一页，共63页。邻接矩阵的性质令B＝(bij)＝A²＝A×A＝(aij(2))n

n，则有：此时，bij表示从vi到vj长度为2的路径数目，如bij＝0，则无长度为2的路径，而bii表示经过vi的长度为2的回路数目；为G中长度为2的路径（含回路）总数，主对角线上元素之和 为G中长度为2的回路总数。第五十一页第五十二页，共63页。邻接矩阵的性质10)令C＝(cij)＝Am＝A×A×…×A＝(aij(m))n

n，则有：此时，cij表示从vi到vj长度为m的路径数目，如cij＝0，则无长度为m的路径，而cii给出了经过vi的长度为m的回路数目。

为G中长度为m的路径（含回路）总数，主对角线上元素之和 为G中长度为m的回路总数。第五十二页第五十三页，共63页。例G1中长度为2的路径（含回路）总数为21，其中9条为回路。G1中长度为3的路径（含回路）总数为48，其中10条为回路。第五十三页第五十四页，共63页。例G2中长度为2的路径（含回