第 章图论 图论(graphtheory)是数学的一个分支。众所周知,图论起源于一个非常经典的问 题———哥尼斯堡(Konigsberg)问题。1738 年,瑞士数学家欧拉(LeonhardEuler)解决了 哥尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。 1859 年,英国数学家哈密顿发明了一种游戏:用一个规则的实心十二面体,它的20 个顶点标出世界著名的20 个城市,要求游戏者找出一条沿着各边通过每个顶点刚好一次 的闭回路,即“绕行世界”。用图论的语言来说,游戏的目的是在十二面体的图中找出一个 生成圈。这个生成圈后来被称为哈密顿回路。这个问题后来就叫作哈密顿问题。由于运 筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题,从而引起广泛的注意 和研究。特别在运筹学、控制论、博弈论等研究中,图论成为解决实际问题的基本工具 之一。 5.图的概念 1 从本节开始介绍离散数学中应用最为重要的图论,首先对于图论这两个字的理解不 同于我们日常生活中的图,数学中的图是指由简单线条或者闭曲线等组合的形状这种图 并不是由马赛克或者照片组成的。........................................, 图论中主要的研究内容是基于两点之间的关系而建立的。在第4章中给出了关系图 和偏序关系,这种关系也可以直接应用到图论的理解和应用上。我们首先给出图的数学 定义。 1( 图是指由三元组 其中V(是指一个非空 集合,称为结点集,其中的元素是图中出现的所有的顶点或结点;E(G)是指一个将所有 的边作为元素的集合,简称边集;是指将边集与结点集关联起来的有序或者无序的函 φG 数或者关系。 定义中V(vertex)表示顶点;E(edge)表示连接两个结点的边;G(graphic)表示图,或 者这个图的名称为G。 可以从定义中看到一个图至少需要一个结点和一个边集与结点的函数,也就是说一 个图可能没有边,但是必定至少有一个结点,还有一个定义在上面的关系,这如同第4章 所讲的那样,我们可以把有序关系和无序关系加到结点上。同样也可以将图按照关系画 离散数学(第2 版) 出它的关系图和关系矩阵,只是这里图与关系图在名称、有序及无序上有点差别,我们以 例5-1作说明。 【例5-1】(图) 一个图已知结点V (G)={a,b,c,d},E (G)={e1,e2,e3,e4,e5},其 中定义在边上的关系为 φG (e1)=(a,b),φG (e2)=,φG (e3)=,φG (e4)=,φG (e5)= 作出它的图和图矩阵。 解 根据结点我们首先画出它散开的结点,然后按照关系连接各结点,最后再根据关 系在它的边上标注边的名称,如图5-1所示。 图5-1 作图过程 在作图中我们特别需要注意以下两点: 第一,φG (e1)=(a,b)的括号是一对圆括号,这表示e1 是没有给定方向的或无向的, 或者说它们两个可以由a→b 或者b→a。因而可以表示成 φG (e1)=∧φG (e1)= 对于其他的序偶,由于是有序的所以是带箭头的。 第二,φG (e5)=表示边e5 上的环或者环路,由于自身指向自身在图中相当于一 个无向的路,因为它的方向没有任何实际意义,因此可以看作是一个φG (e5)=(c,c)。 显然对于它的图的矩阵,完全可以参照关系矩阵来设置: MG = 0 e1 e4 0 e1 0 0 e2 0 0 0 0 e3 0 0 e5 é . êêêêê ù . úúúúú= 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1 é . êêêêê ù . úúúúú 用矩阵表示时,在有关系的序列的位置上直接填上了它的边,或者直接填成数字,特 别需要注意的是e1 边,由于是无向的,所以它可以理解为双向的。另外在矩阵表示时,目 前我们将“存在关系”记为数字1。但是,在下面的内容中会发现有时候边是有长度的,因 此,用矩阵表示时,有长度的边可以填上它的边的长度。 从上面的例子可以看出,一个图可以由两种不同的边组成:一种是有向的;另一种是 无向的。一般把只有由无向边组成的图称之为无向图,把全部由有向边组成的图称为有 向图,如果既有无向边又有有向边,那么这个图称为混合图。 下面再看图5-2,在这个图上介绍关于图的另外一些概念。 图5-2中,A 图只有一些点,没有任何边连接它们;B 图中有三个点是连接的,但是 有一个点是单独的,我们把这种单独的,没有和其他结点连接的点称之为孤立点。例如两 个图中的c 点都是这样的,因而两个图中的C 点都是孤立点。如果像图A 一样整个图全 76 图5-2 零图与孤立点 部是由孤立点组成的,那么这个图称为零图。更特别的,如果图中仅由一个孤立点组成, 那么这个图称之为平凡图。 有一些图不用边来表示,那么这种图就可以完全使用第4章的关系图来表示,这样更 能突出结点的作用,此时的图就简化成G=, 其中 V 依旧是结点, E 依旧是边,只 是这个边没有像e1 这样的名称,取而代之的是 实际 上它将原来定义中的φG 整合到了 E 中。 a,。这是一种简化图的表示方式, 现在,我们用这种简化的表达方式来介绍关于图的一些性质。 定义5-度) V,中, 2( 在给定的图G= 与结点v∈ V 直接连接的边数称之为结点 的度,记作dg()。其中, nD()。 记作otD(由 ev 由结点 v 指向别的结点的边数称之为出度,uv); 其他结点指向结点 v 的边数称之为入度,记作iv 从这个定义可以知道一个结点的度等于结点的出度加上入度,换而言之就是 dev)otD(nD( g(=uv)+iv) 如果将每个结点的度按照大小排列,那么最大的度称之为最大度,同理,最小的度称 之为最小度。 定理5-1(握手定理) 任何图中,结点的度数的总和等于边数的2倍,记作 Σdev)2|E| g(= v∈ V 证明由于每条边必定有2个结点与之相连,那么每一条边给结点的贡献量就是度。 因为在计算总的度数时,重复计算了一次共同拥有的边,所以图中的结点度数必然是边的 2倍。需要说明的是对于环,它相当于一个边两端连接的都是同一个点,所以环路对于一 个结点贡献两次度。 在这个定理之上又可以得到另外一个关于结点度的定理: 定理5-2(奇度结点总数偶化) 任何图中度数为奇数的结点的个数必定为偶数。 因为定理5-1限制了总度数为偶数,那么贡献为奇数的结点只有偶化才能满足定 理5-1。这个定理我们可以用公式表示,设度数为奇数的结点集合为V1,度数为偶数的 结点集合为V2,那么就存在 g(dev)2|E| Σdev) + Σ g(= v∈V1 v∈V2 所有图的结点的度都有上面的性质,不论是不是有向图。下面则是有向图的结点特 有的性质。 第 5 章图论 有9个人在一起打乒乓球,已知他们每人至少和其中另外3个人各打过一场球,则一 定有一个人不止和3个人打过球。用图论语言解释这件事。设v1,v9代表这9个 v2,…, 人,建立顶点集V={v2,…,对于其中的任意两个人vi 和vj (若vi v1,v9}, i≠j), 和vj vi,vj}∈E, V, 打过一场球,则{得到边集E,则我们有了一个无向图G=(E)。若每一个 人仅和其余3个人各打过一场球,则d(=3, vi)≥4 。 即是 vi)而此时图 G 的奇数度的顶点是9个, 奇数个,与推论矛盾。矛盾说明,至少有一个人vi,d( 定理5-3(出入度恒等性) 在任何有向图中,所有结点的出度之和等于所有结点的 入度之和。(证略) 这个理论很显然是成立的,有输出贡献,那么必然就有结点接受贡献。 现在再介绍一些有关图的名称和定义。 定义5-3(平行边) 若图中任意两个结点v1 和v2 之间存在多条直接连接且同向的 边,那么这些边之间称之为平行边。特别的,如果v1=v2,那么每一条边就是一个环,这 些环叫平行环。 这个定义可以解释为,如果两个结点之间是无向边,显然不用区分方向,只要它们的 端点都是相同的,那么这些无向边就是平行边。显然在同一个结点上的多个环可被看作 无向边,那么叫作平行环。在有向图中,只有相同方向的边才能称之为平行边。如图5-3 所示,存在几组平行边。 图5-3 平行边、环 -端点 a 上有两个平行环, b 之间有两条平行边; 图53的 A 中, 端点a,图 B 中,端点 c, d 之间的两条边e1,e2 为平行边, e2方向不同, 个基础上我们又定义: 而边e3 与边e1,所以不是平行边。在这 定义5-4(完全图) 既不含平行边也不含环的图称为简单图。含平行边的图称为多 重图。若在简单图上的每一对结点都有边相连,那么这个图称之为完全图。 如果一个完全图是无向图,且有 n 个结点,那么这个图可以记作Kn ,这个图一般运 用在对边的计数上,例如定理5-4。 ,定理5-4(无向图的边计数) 若有 n 个结点的无向完全图Kn 那么这个图的边数为 1 n-1)。 2n( 图5-4中,(1)是K5,(2)是3阶有向完全图,(3)是4阶竞赛图。 有些图并不是完全图,所以需要使用一些其他的方法使得它是一个完全图,这种方法 叫作补图,有点类似中学阶段学习的添加辅助线。 定义5-5(补图) 已知图 G 不含平行边和平行环,但图 G 并不是完全图,如果添加边 使得 G 成为完全图,那么, 并记作G。 添加的部分称之为图 G 的补图, .. 87 离散数学(第 2 版) 图5-4 几种完全图 下面介绍具体的补图概念和方法。 如图5-5所示,看到虚线上面一共有三个图,如果把第一个图称之为G,那么第二个 图就是它的补图,因为这两个图重合后就形成了最右边的完全图Kn 。同样,如果把第二 个图作为G,那么第一个图就是它的补图,显然也能得到Kn ,从这个例子来说补图是相对 而言的。 图5-5 补图 除补图之外,离散数学中还定义了另外一个称之为子图的概念,它等同于给出了一个 边和顶点集合的子集,下面给出具体定义。 -6( V,E>'.V,E'.E, '= 定义5子图) 设图G=<,若有V若存在图G,则 称G'为图 G 的子图,也称 G 为图G'的母图。 为了便于了解子图概念,可以用图5-6说明。 图5-6 子图与母图 对于图 G 自身来说, G 是它自己的子图,另外,G' ,G″ ,G.均是 G 的子图。我们发现 GV,E>V ' 包含了 G 的所有结点,那么我们称G'为图 G 的生成子图。设图G=<,'. V 且 V'≠.,称以V'为顶点集,以 G 中两个端点都在V'中的边组成边集E'的图为 G 的V'导出 子图,记作G[']。图G″是 G 的导出子图,而G.不是 G 的导出子图。通过子图的概念, 我们还能知道 V,如果对于图5-5中的Kn 作为全图,那么 G 与 G 称之为相对补图。我们 .. 第 5 章图论 对这个概念推广到一般情况: 定义5-相对补图) V,中有两子图G=< ' ,'>,″VE,它们存 7( 若图G= 'VEG=< ″ ,″> 在E″=E-E'且限定V″ 为E″中的边的端点,那么称这两个子图互为相对 G 的补图。 相对补图的概念需要注意的是边点的约束情况,它首先是限定了一个给定的图G,然 后是边是补的,最后在剩余的边中找点。 下面介绍图论中的另外一个跟映射相关的概念———同构。从字面上理解可以把同构 理解为具有相同的结构,可能在具体的位置排列上有一定的差别。 -8( V,E>G'=< ' ,E'> 定义5同构) 设图G=<,,其中点vi,组成 G 的一条边e= 或e=(vj vi →vi, '中存在一条对应的边e '=('vj), G i, ' 或evi, ' 那么称G,'同构。 从同构的定义可以知道两个图同构,应该具有相同数量的结点和边,同样也应该具有 相同的结点度分布。如果将同构的图进行结点排列,最终的两个图应该是相似的。下面 举例来说两个图的同构。 对于同构的图可以将一个结点与这个结点相连的边移动到别的地方,如图5-7所示, 可以将左边的图G1 的 c 移动到右边,这样G1,G2,G3 是相似的,但是我们也发现G2,G3 不同,因为边的方向不同,根据同构定义,我们知道边的方向也应该一致,所以G1 在移动 c 时不能改变边的方向,那么G1,G1,因为c→ad→cb→da→b'。 同构的本质是画法不同,实质相同 G 。 2 同构,G3 不同构, ' , ' , ' , 图5-7 图同构 思考K4 的所有的生成子图有多少个? 共有64 个。K4 所有互不同构的生成子图有 多少个? 有11 个。请你画一画。 5.路与回路 2 在生活中,有一类图是用来指导路径和范围的,这类图生活中称之为导航图或者地 图,数学中我们只对不同分布的结点间的路径感兴趣,最典型的就是从一个城市到另外一 个城市该怎样安排自己的出行路线,下面具体介绍关于这方面的知识。 定义5-9(路) 图G=中设vei=1,3,…, 其中边ei 连接两 V, i ∈V, i ∈E,0,2, 点vi-1和vi,由结点和边交替链接组成的,且由v0 可通往vn 的链路v0e1v1e2v2…vn-1envn 称之为v0 到vn 的路, vn n=|E|为路的长度。 其中v0 称之为起点,为终点, 80离散数学(第 2 版) 首先,定义中特别需要注意的是这个链路必须是可以到达的,例如在一些有向图中虽 然是连接的,但是不能到达,好比马路上单向行驶路段一样,只能一个点到另外一个点,而 不是双向的。 对于路根据不同的结点和边由不同名称表示方式: (1)若路中直接略去结点,只写出边e1e2…en ,且不存在重复边,那么这种表示称之 为迹,或称为简单通路。 (2)若路中只用不同结点表示路,那么称之为通路,或称为初等通路。 (3)若路中的起始结点和终点均为同一个结点, 那么这个路称之为回路。 (4)若回路中除了起点、终点外的所有结点均不 同,那么这个回路称之为圈。 通俗理解:边不重复为简单通路,点不重复为初 等通路。边不重复的回路为简单回路,除起点和终 点外,点不重复的回路为初等回路。 为了便于理解,图5-8给出了一些示例。图5-8 各种 路 在图5-8中,e6v4e4v3 或 表 v5→v3 有一条路v5 示成迹e6e4,当然从v5→v3 的路并不是唯一的,显然还有通路v5v4v1v2v3。我们发现这 个图是有向图和无向图的混合,那么对于从v4→v2 的路来说可以是单向的也可以是双向 的,例如单向v4e5v2 或表示成无向(双向)的v4e7v1e2v2。若是表示回路v2→v2 只能是 选择v2e2v1e7v4e5v2 或v2e2v1e7v4e4v3e3v2,当然还有其他方法,同时这里的回路是一个 圈,而且是一个单向圈,但是v1→v1 的e1 是一个双向圈。 无向图中若任意一对结点之间均有通路,那么就称该无向图是连通的。若一个图 G 的不同子图G1,G2,…,Gn ,它们各自都是连通的,若G1,G2,…,Gn 没有公共的结点, 么称这些子图为一个连通分支,其中连通分支的数量记作 W (G)。若这个无向图中只有(那) 一个连通分支,那么这个图就称之为连通图。 图5-9中左边虚框内为图G,它的两个子图为G1 和G2。由于G1 和G2 没有公共 点,所以它有两个连通分支。对于右边的图 G 它只有一个连通分支,所以它是一个连 通图。 图5-9 连通分支图 第 5 章图论 18 由连通图的特点容易得到:如果删除一些特定结点,那么图的连通性就不能得到保 证。这衍生出一个问题,对于连通图中的结点重要性问题,例如古代攻城时通常会选择切 断敌方后路,而这个后路就是通过占取重要结点完成,这样在敌方看来就不能保证自己的 部队的联络连通性。 图论的割集与强连通图等就是研究这个方面的。 定义5-10(割点、割边) 若删除图 G 某一个结点与它所关联的边,使得图的连通分 支变多,那么这个点称之为割点或结点;若删除图 G 中某一条边使得图的连通分支变多, 那么这条边称之为割边或桥①。 显然想要得到割点和割边,只要找到必经之路或必经之结点即可。 定义5-11(点割集、设无向图G=为连通图,点集V'.V, 边割集) V,若在图 G 中删除V' 中所有点后得到的所有子图是不连通的,那么称V'为点割集;同理边集E'. E,若在图 G 中删除E' 中所有边后得到的所有子图是不连通的,那么称E'为边割集。 可以看到,定义5-10 与定义5-11 的差别在于割点、割边是单个点和单个边,只要一 个就可以使得图的连通性发生改变,而点割集和边割集是集合中所有的点或边同时作用 才能使得图的连通性发生改变。 我们还发现若点割集和边割集中只有一个元素时,它就退化为割点和割边。这就是 说点割集和边割集的大小有时不是确定的,它们的大小取决于怎样选择结点。为了研究 方便我们定义: 最小点割集大小:k(G)=min{|V'||V'是 G 的点割集 } 最小边割集大小:λ(G)=min{|E'||E'是 G 的边割集 } 另外我们重复列出,最小度和最大度 : δ(G)=min{degv|v∈G}, Δ(G)=max{degv|v∈G} 这些最小量之间存在这样的关系:k(G)≤λ(G)≤δ(G)≤Δ(G) 有向图的连通性不同于无向图,这是因为有向图不像无向图那样有传递性和对称性。 也就是说,有时候有向图的路是一个单向的路,因此在有向图中研究连通性时常用可达性 来说明。 由于在有向图中从结点 u 到达结点 v 可能不止一条路径,我们把两个点之间最短长 度的路表示成距离d,显然我们可以得到 u, d u,≥0 d=0 u, dv,u, +d≥d 对于任何图,若 u 不可以达到v,那么记为d=∞ 或在计算机网络中常用 u,1表示。d=- 那么d v,这是由于有 对于有向图,若 u 与 v 可以互相到达, u,不一定等于d, 向图的单向性决定的。 对于任何图,我们把D=mau,xd称之为图的直径。 v∈ V ① 计算机网络中使用桥来表示一个重要的边路。 82离散数学(第 2 版) 在简单的有向图中,关于连通性还有另外一些定义。 定义5-12(强弱连通图) 在简单有向图 G 中,任何一对结点间至少有一个结点到另 外一个结点是可达的,那么称这个有向图为单向连通的;若这个图的任何一对结点之间是 相互可达的,那么称这个图是强连通的;若有向图 G 中忽略边的有向性,把它看成无向 图,这时才是连通的,那么这个图是弱连通的。 我们可以看到若一个图是强连通的,必然也是单侧可达的;若一个图是单侧可达的, 必然是弱连通的。反过来则没有这个结论。 图5-10 中,G1 是强连通的,因为每个结点都可以到达任意其他结点;G2 是单向连通 的,因为它的每对结点至少有一个结点可以到另外一个。G3 只是弱连通的,因为负对角 线无法可达,所以只有把它当作无向图时才能连通,因而是弱连通的。 图5-10 强弱连通与单侧可达 定理5-5(强连通图判定) 若一个有向图 G 为强连通图,当且仅当图 G 中有一个至 少包含各个结点一次的回路。 定义5-13(连通分图) 若简单有向图的生成子图中,具有最大强连通性的子图称为 强分图;具有单向连通性的最大子图为单向分图;具有弱连通性的最大子图为弱分图。 在图5-11 中, G 的强连通分图为G1,G2,因为它们各自可以组成一个最大的强连通 分量。需要特别注意的是,单个结点也可被看作一个强连通分量。而原先的图 G 本身是 一个单向连通的。 图5-11 连通分图 5.图的矩阵形式 3 在5.本节将简短介绍有关图 1节中我们描述了一个关系矩阵可以用来表示一个图, 的矩阵表示的一些运算和概念。 第 5 章图论 离散数学(第2 版) 定义5-14(邻接矩阵①) 设G=是一个简单图,它有n 个结点,那么用n 阶方 阵来表示A(G)=(aij),这个矩阵称之为邻接矩阵。矩阵中 aij= 1, viadjvj 0, vi nadjvj∨i=j { 其中,adj表示邻接或两个结点有一直接相连的边相连;同样nadj表示不邻接。 显然图的邻接矩阵完全可以被看作关系矩阵的一个扩展,那么根据第4章所给: 无向图的邻接矩阵是对称的,有向图的邻接矩阵不一定是对称的。另外,如果我们把 每行作为一个结点,显然交换任意两行之后,同时对调与行数对应的两列并不改变原来图 的形式,这一种邻接矩阵的调换称之为等价置换,如图5-12所示。 A(G1)= 0 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 é . êêêêê ù . úúúúú . 0 1 0 0 1 1 0 1 0 0 1 1 1 0 0 0 é . êêêêê ù . úúúúú .A(G2)= 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 é . êêêêê ù . úúúúú 图5-12 等价置换 我们把等价置换归结为:给定行i,j,那么交换A(G)的i,j 行得到A'(G),然后再交 换A'(G)的i,j 列,得到A(G')。若作图,那么直接交换原来图中的对应的两个位置的 结点。根 据第4章中的关系矩阵的传递性,我们还可以得到邻接矩阵是可以直接计算vi→ vj 长度为l 的通路的数目a(l) ( ij )n×n 。 (1)如果vi→vj 需要走长度为1的路,在邻接矩阵中直接看aij=1即可。 发现若l=1,那么vi→vj 间长度为1的路的总数为 a(1) ( ij )n×n =aij 由矩阵知道这正好是A(G)的第i 行第j 列的元素。 (2)如果vi→vj 需要走长度为2的路,那么应该有aik =1且akj =1,这样才能使得 vi→vk →vj 成立,那么也就有aik ·akj=1。 若l=2,那么vi→vj 间长度为2的路的总数为 a(2) ( ij ) n×n =ai1·a1j +ai2·a2j + … +ain ·anj =Σn k=1 aik ·akj 84 ① adjacencymatrix。