当前位置: 首页 > 工学 >

离散数学 有向图 教学课件_图文

21世纪高等教育计算机规划教材
第6章 有向图
《应用离散数学(第2版)》
方景龙 周丽 编著

目录
6.1 有向图概述 6.2 根 树 6.3 网络流 6.4 匹 配

很多应用问题涉及有向图。 有向图除了(无向)图类似的性质之外,还有一些(无向)图所不具备的特殊性质。 本章除介绍有向图的基本概念外,着重介绍根树、网络流及其应用等。

6.1 有向图概述
6.1.1 基本概念

在有向图中,若两个顶点之间有两条或两条以上的边,并且方向相同,则称它们为平行边, 它强调了边的方向性。有向图中的其他一些概念,像图的阶、零图、平凡图、环、带环图、无环
图、简单图、多重图、 ( p,q) 图、邻接、关联、孤立点、孤立边、二部图、赋权图、子图、真
子图、导出子图、生成子图、奇点、偶点、悬挂点、悬挂边等,都与(无向)图中相应概念的定 义一样,这里不再重复。

6.1.2 有向图的连通性 在有向图中,通路、回路、通路的长度、简单通路、简单回路、基本通路、基本回路等概念与无
向图中相应概念非常类似,只要注意有向边方向的一致性即可。
有向图中从一点到另一点的距离的定义与(无向)图中的定义类似,距离的记号为d ? u,v ?,
不过它是有向的。(无向)图中的距离满足非负性、对称性和三角不等式,但有向图中距离只满足非 负性和三角不等式,不满足对称性。
有向图的连通性比(无向)图的连通性包含了更多的内容,下面我们来讨论它。

例6.1 图6.1所示的有向图中,(a)是强连通的,(b)是单向连通的,(c)是弱连通的。 图6.1 有向图的连通性

例6.2 图6.2是一个单向连通图,当然也是弱连通图,但不是强连通图,它有两个强连通分图,
分别为<{2,3,4,5},{<2,3>,<3,4>,<4,5>,<5,2>}>和 ? {1},? ? 。

图6.2 单项连通有向图

图6.3 弱连通有向图

图6.3是弱连通图,不是单向连通图,当然也就不是强连通图。它有2个单向连通分图,3个 强连通分图。
2个单向连通分图分别是<{4,5},{<5,4>}和<{1,2,3,4,6},{<1,2>,<2,3>, <1,3>,<3,6>,<6,1>,<3,4>}。3个强连通分图分别是<{1,2,3,6},{<1,2>,
<2,3>,<1,3>,<3,6>,<6,1>},? {4},? ? 和 ? {5},? ? 。

从例6.2还可以看到,有向图的每一个顶点都唯一地属于某一个强连通分图,这是因为相互
可达 ? 是有向图顶点集合上的等价关系。该等价关系将顶点集划分成互不相交的几部分,每部
分对应于一个强连通分图。不过,由于可达 仅仅是有向图顶点集合上的二元关系,而不是等价 关系,所以“有向图的每一个顶点都唯一地属于某一个单向连通分图”并不成立,例如,图6.3 中的顶点4就同时属于两个单向连通分图。
对于有向图的有向边,则相反,即每条有向边都唯一地属于某一个单向连通分图,如图6.3 所示,但“有向图的每一条有向边都唯一地属于某一个强连通分图”却不成立,例如,图6.2中 的有向边<2,1>和<5,1>,以及图6.3中的有向边<3,4>和<5,4>。
由于弱连通分图是根据有向图的底图的连通性定义的,所以有向图的每一个顶点都唯一地属 于某一个弱连通分图,每一条有向边也唯一地属于某一弱连通分图。
下面给出强连通图和单向连通图的判别定理。

6.1.3 有向图的矩阵表示 类似于无向图,有向图的邻接矩阵也可以定义如下。

例6.3 利用可达矩阵求有向图6.3的单向连通分图和强连通分图。 解 先给出有向图6.3的邻接矩阵,
然后求它的幂和,

由此得出可达矩阵和它的转置矩阵,

进一步得出它们的布尔和与布尔积,

由上面可达矩阵的的布尔和与布尔积可以看出,它有2个单向连通分图,3个强连通分图。2 个单向连通分图分别是顶点子集{4,5}和{1,2,3,4,6}的导出子图。3个强连通分图分别是顶 点子集{1,2,3,6},{4}和{5}的导出子图,与例6.3的结果一致。

6.2 根 树
6.2.1 基本概念
设D 是有向图,若 D 的底图是(无向)树,则称D 为有向树。在所有的有向树中,根树最
重要,所以我们这里只讨论根树。
定义6.8 设T 为有向树,若T 中有一个顶点的入度为0,其余的顶点的入度均为1,则称 为根树。
入度为0的顶点称为根结点,又称树根,入度为1的顶点称为子结点。出度为0的顶点称为树叶,
出度不为0的顶点称为分支点。既不是树叶又不是树根的顶点称为内点。从树根到任意顶点 v 的 路的长度称为v 的层数,层数最大的顶点的层数称为树高。将平凡图也看成根树,称为平凡树。
(1,0)图 称为平凡图

在根树中,由于各有向边的方向是一致的,所以画根树时可以省去各边上的所有箭头,并将 树根画在最上方。图6.7所示的根树中,有8片树叶,6个内点,7个分支点,它的高度为5,在树
叶u 或 v 处达到。
常将根树看成家族树,家族中成员之间的关系可由下面的定义给出。
图6.7

图6.8 单淘汰赛图(正则二叉树)
可以证明如果在一次单淘汰赛中,有 n 名选手,则一共要有n -1 场比赛。这是因为参赛选 手的数目与树叶的数目一样多,比赛次数 与i分支点数目一样多,因此由定理6.4,i=n-1。

6.2.2 二叉搜索树
设集合 S 是有序集合,例如, S 由数字组成,可以按照数的大小排序,如果 S 由字符串组
成,可以按照字典序排序。二叉树可以用来存储有序集合的元素,比如数字集合或字符串集合。 下面给出它的形式化定义。 定义6.12 二叉搜索树是一种二叉树,它对应于某个有序集合。有序集合里的数据都存放在二叉
树的顶点之中,使得对于树中的任意顶点v ,v 的左子树中的任意数据都比 v 中的数据小,而 v 的右子树中的任意数据都比 v 中的数据大。

例6.5 下面的一组词 OLD PROGRAMMERS NEVER DIE
THEY JUST LOSE THEIR MEMORIES
可以放在如图6.9所示的二叉搜索树上(根据字母表),对于任意顶点 v 来说, v 的左子树 上的任意数据项都比v 中的数据项小,而 v 的右子树上的任意数据项都比v 中的数据项大。
图6.9 一棵二叉搜索树

一般来说,有很多方法将有序数据放入二叉搜索树中,图6.10展示了另一种存储例6.5中词 的二叉搜索树。
图6.10 例6.5的另一种二叉搜索树

用二叉搜索树存储有序数据后,查找数据非常方便。例如,查找数据data,我们从根结点 查起,将data与当前顶点的数据不断进行比较,如果data与当前顶点的数据相等,则找到data,
停止。如果小于当前顶点v 的数据,则移动到v 的左子结点,重复上述操作。如果data大于当前 顶点v的数据,则移动到v 的右子结点,重复上述操作。如果要移动到的某个子结点不存在,则
可以得出结论认为data不在该树中。 当数据不在二叉搜索树上时,搜索的时间花费最多,此时要搜索从树根到树叶的整条路径,
因此,二叉树的最大搜索时间与树高成正比。有许多方法可以尽可能地降低二叉搜索树的高度。

图6.11 将二叉搜索树扩展到满二叉树

6.2.3 最优二叉树

图6.12 非最优二叉树

以上三棵二叉树都不是带权2,2,3,3,5的最优二叉树,那应该如何求解带权w1,w2,…, wt(w1≤w2≤…≤wt)的最优二叉树呢?下面介绍一种赫夫曼(Huffman)算法,其基本步骤如
下。
(1)连接权为w1,w2的两片树叶,得一个分支点,其权为w1+w2。 (2)在w1+w2,w3,…,wt中选出两个最小的权,连接它们对应的顶点(不一定是树叶),得
新分支点及所带的权。
(3)重复(2),直到形成t – 1个分支点,t 片树叶为止。
由于每一步选择两个最小的权的选法不唯一,且两个最小的权对应的顶点所放左右位置的不 同,画出的最优二叉树可能不同,但有一点是肯定的,就是它们的总权值应该相等而且最小,即 它们都应该是最优二叉树。

例6.7 利用Huffman算法求带权2,2,3,3,5的最优二叉树。 解 为了熟悉Huffman算法,在图6.13中给出了计算最优二叉树的过程。最优二叉树为图6.13
(d),其总权值为W (T )=34。
图6.13 用Huffman算法求最优二叉树

在通信中,常用二进制编码表示符号。例如,可用长为2的二进制编码00,01,10,11分别表
示A,B,C,D。这种表示法叫做等长码表示法。若在传输中,A,B,C,D 出现的频率大体相同,
用等长码表示是很好的方法,但当它们出现的频率相差悬殊,为了节省二进制数位,以达到提高效 率的目的,就要寻找非等长的编码,用短码表示常用的符号,用长码表示不常用的符号。

这里只讨论二元前缀码(简称为前缀码)。例如,{00,010,011,1}为前缀码,而{00,001, 011,1}不是前缀码,因为00是001的前缀。采用前缀码可以对数据进行编解码。如把a,b,c,d分 别用上述前缀码中的码子00,010,011,1来表示,则字符串ba就可编码为01000,当接收到该串 符号,通过查找码子可解码为ba。由于要解码,必须要求码子互不为前缀。例如,若用00,001, 011,1分别表示a,b,c,d,则ba编码为00100,解码就会产生歧义,可解为ada或ba。因此,前 缀码定义中要求码子互不为前缀。
下面给出用二叉树产生前缀码的方法。

例6.8 求如图6.14所示两棵二叉树所产生的前缀码。 解 图6.14(a)为二叉树,将每个分支点引出的两条边分别标上0和1,如图6.15(a)所示,产 生的前缀码为{11,01,000,0010,0011}。若将其中只有一个儿子的那个分支点引出的边标 上0,则产生的前缀码为{10,01,000,0010,0011}。
图6.14(b)是正则二叉树,它产生唯一的前缀码。它标定后的正则二叉树为图6.15(b), 前缀码为{01,10,11,000,0010,0011}。
图6.14 产生前缀码的二叉树

图6.15 用二叉树产生前缀码

例6.8中的任一个前缀码都可以传输5个符号,比如A,B,C,D,E,都不会传错。现在要问
的是,当字母出现频率不同时,用哪个符号串传输哪个字母最有效率呢?这就要用各符号出现的 频率为权,利用Huffman算法求最优二叉树。由最优二叉树产生的前缀码称为最佳前缀码。用最 佳前缀码传输对应的各符号能使传输的二进制数位最省。

例6.9 在通信中,八进制数字出现的频率如下:

0:25%

1:20%

2:15%

3:10%

4:10%

5:10%

6:5%

7:5%

求传输它们的最佳前缀码,并求传输 10n (n ≥ 2) 个按上述频率出现的八进制数字需要多

少个二进制数字?若是用等长的(长为3)码子传输,需要多少个二进制数字?

解 用100个八进制数字中各数字出现的个数,即以100乘频率得到的积为权,并将各权由小到
大排列,得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,wg=25(记住它们各
自对应哪个数字),用Huffman算法求最优二叉树,然后根据此最优二叉树用上面介绍的方法 求前缀码,即为最佳前缀码,如图6.16(a)所示。
图6.16 用最优二叉树产生最佳前缀码

图中矩形框中的符号串为对应数字的码子:01传0,11传1,001传2,100传3, 101传4 , 0001传5,00000传6,00001传7。8个码子的集合
{01,11,001,100,101,0001,00000,00001} 为前缀码,而且是最佳前缀码。
将图6.16(a)表示的二叉树记为 T。易知, w(T ) 即为传输100个按题中给定频率出现的 八进制数字所用二进制数字的个数。除了可用树的总权值定义计算 w(T ) 外,w(T ) 还等于各
分支点权之和,所以,
w(T) ?10 ? 20 ? 35 ? 60 ?100 ? 40 ? 20 ? 285 。

6.3 网络流
6.3.1 基本概念 本节使用有向图来讨论网络模型。这里的网络可以是通过货物流的运输网、输送石油的输油
管道网、传送数据流的计算机网络或许多其他可能的情况,即所谓的运输网络。我们重点关注的 是如何最大化网络的流量,即如何求网络最大流。其他许多表面上看来不是流的问题,也可以用 网络流模型来解决。
定义6.15 运输网络是一个简单的、赋权有向图G,满足: (1)有一个顶点没有入边,该顶点称为源点,并用 a 表示。 (2)有一个顶点没有出边,该顶点称为收点,并用z 表示。 (3)有向边(i,j )的权值Cij 是非负数,Cij 称为(i,j )的容量。
在本节我们只讨论运输网络,不讨论其他有向网络,所以在本节有时将运输网络简称为网络。 网络的流给网络的每条有向边赋予一个不超过这条边容量的流量,而且对于一个既不是源点也不 是收点的顶点 ,流入 的流量等于流出 的流量。下面给出严格的定义。

图6.20 一个运输网络

例6.11(泵送网络)图6.21(a)表示一个泵送网络。在网络中,两个城市 A 和 B 的水由3口 井w1,w2和w3供给。中间的容量表示在边上。顶点 b,d 和c 表示中间泵站。为了将这个系统
模型化为一个运输网络,需要给出源点和收点。为此,可以将所有的源点合并成一个超源点,将 所有的收点合并成一个超收点,从而得到一个等价的运输网络,如图6.21(b)所示。在图6.21 (b)中,∞表示无限的容量。
图6.21 一个泵送网络

例6.12 (交通流网络)从城市A 到城市C 可以直达,也可以经过城市B。在下午6:00至7: 00间,平均行驶时间是A 到B 需15min,B 到C 需30min,A 到C 需30min。而路的最大容量 是A 到B 为3000辆车,B 到C 为2000辆车,A 到C 为4000辆车。请将下午6:00至7:00间 从A 到C 的交通流表示为网络。

图6.22 一个交通流网络 网络流也被用在设计高效的计算机网络上。在计算机网络的模型中,顶点是信息中心或交换 中心,边表示顶点间传送数据的信道。流表示信道上每秒钟传送的平均比特数,边的容量是对应 信道的容量。

6.3.2 最大流算法
如果图G 是运输网络,G 中的最大流是流量最大的流。在本小节中,给出一个寻求最大流
的算法。 基本思想很简单—从某个初始流开始,反复地增加流的流量直到不能再增加为止,最后得
到的流就是一个最大流。 初始流可以取为每条边上的流量都是零的流。为了增加一个已知流的流量,必须找出一条
从源点到收点的路径,并沿着这条路径增加这个流。

设P = (a,b,…,z )是运输网络G 的底图中一条从a到z的路径(本小节中,说运输网络的 路径实际上都是关于底图的)。如果P 中的一条边e的方向是从vi?1指向vi,就称e(相对于P)是 正向的;否则,称e(相对于P)是反向的。例如,在图6.20(b)中,路径(a,b,c,z )中的每 条边都是正向的,路径(a,b,c,d,e,z) 中的边(c,d )是反向的,其他的边都是正向的。 例6.13 考虑图6.23(a)中从a 到z 的路径P,它的所有边都是正向的。这个网络中流的流量可
以增加1,如图6.23(b)所示。
图6.23 所有边都是正向边的路径

图6.24 含有反向边的路径

可将例6.13和例6.14的方法总结为定理6.7。
流量小于容量

下一节将说明如果没有路径满足定理6.7的条件,则流是最大的。这样,可以以定理6.7为基 础构造一个算法,称为标号算法。其基本步骤如下。 (1)从一个流开始(例如,每条边上的流量都是0的流)。 (2)寻找一条满足定理6.7条件的路径。如果这样的路径不存在,停止;流是最大流。
(3)将流过这条路径的流量增加 ? ,其中, ? 如定理6.7中所定义,转(2)。
标号算法:用来求运输网络的最大流,其中运输网络每条边的容量是非负数。
输入:源点 a、收点z 、容量C 、顶点a = v0,…,vn = z的网络和顶点数 n。 输出:一个最大流 F。

【例】求下图v1 到v6 的最大流及最大流量 【解】1. 通过观察得到初始可行流

2.标号 3. 得到增广链

∞①

64 82

2

42

6

42 10
22 22

2020年2月12日星期三

67


60

1

74 92

⑥7

4.求调整量

2


? ? min ??,6,2,1,7?? 1 ∞



64

42

5.调整可行流

82

去掉所有标号,重新标号


6

42 10
22 22

2020年2月12日星期三



74

60
92 ⑤
1

得到增广链

64

2


42 11

2
④ 74

∞①

83

41

22

60

⑥3 93



22



Cij-fij=0为不 可调整

68
⑥7

求调整量 ? ? min ??,2,2,3?? 2
调整可行流
去掉所有标号,重新标号
标号不能继续进行,说明不存在从发点到收点的增广链,得到最大流.

2020年2月12日星期三

69

66





83

1

41

5

44 11
22 22

④ 76

60



93 ⑤

最大流量 v=6+3=9

图6.26 用标号算法求最大流

6.3.3 最大流最小割定理 本小节将说明标号算法停止时,网络的流是最大的。为此,先介绍网络的割和割的容量。

图6.27 割与最小割

图6.28 割与最小割

下面的定理6.8说明任意一个割的容量总是大于或等于任意一个流的流量。

6.4 匹 配
在本节中,考虑将一个集合中的元素与另一个集合中的元素匹配的问题。
例6.18 假设4个人A,B,C 和D 申请5个工作岗位J1,J2,J3,J4和J5。如果申请人A 能胜任工 作J 2和J 5,申请人B 能胜任工作J 2和J 5,申请人C 能胜任工作J 1,J 3,J 4和J 5,申请人D 能 胜任工作J2和J5,问可能为每个申请人都找到一份工作吗?
这种匹配问题可以用图6.32所示的有向二部图来建立模型。顶点代表申请人和工作。一条边
把一个申请人连接到这个申请人所能胜任的一个工作上。通过考虑胜任工作J2和J5的申请人A,B 和D,就可以说明不可能为每个申请人匹配一个工作。如果A 和B 被分配了工作,则没有剩余的 工作分配给D。所以,不存在A,B,C 和D 的工作分配。

定义6.18 设G是有向二部图,V 和W 是相应的两个顶点集,所有边的方向都是从V 指向W。G 的一个匹配是一个没有公共顶点的边的集合M;G 的最大匹配是包含了最多数量的边的匹配M;
G 的完全匹配是具有如下性质的匹配M:如果 v ?V,则有某个 w?W,使得(v,w )∈M。
例6.19 (1)在图6.32中,M1={<B,J5>,<C,J3>}是一个匹配,表示一些人找到工作; M2={<A,J2>,<B,J5>,<C,J3>}是一个最大匹配,表示最大数量的人找到工作;例6.18
已经说明不可能每个人都找到工作,所以,图6.32没有完全匹配。
(2)在图6.33中,M = {<A,X>,<B,Z>,<C,W>}是一个完全匹配。
匹配问题可以归结为一个运输网络的最大流问题,下面的例子说明如何将匹配问题转化为运 输网络的最大流问题。

图6.32 匹配问题

图6.33 具有完全匹配的例子

例6.20(匹配网络) 把有向二部图6.32转换为运输网络。 图6.34 匹配网络

下面的定理将匹配问题与匹配网络上的流联系起来,这样,有了匹配网络,就可以通过求解 匹配网络上的流来求解匹配问题。

例6.21 定理6.11指出,可以通过匹配网络的流来求解 匹配,同样,根据匹配也可以求出匹配网络的流。比如,
例6.19的匹配M2={<A,J2>,<B,J5>,<C,J3>}对 应的匹配网络的流可以这样给定:指定匹配M2={<A, J2>,<B,J5>,<C,J3>}中边的流量为1,从顶点A, B,C,D 到顶点J1,J2,J3,J4其他边的流量为0。然 后,根据流量守恒给出超源点 到顶点A,B,C,D 的边 的流量以及顶点J1,J2,J3,J4到超收点 的流量,如图 6.35所示。因为M2={<A,J2>,<B,J5>,<C,J3>}
是最大匹配,所以,此时的流是也最大的。

图6.35 匹配网络的流

定理6.12(Hall婚配定理) 设G 是一个匹配问题的相应有向二部图,V 和W 是相应的两个顶点 集,所有边的方向都是从V 指向W,则G 存在完全匹配,当且仅当
S ≤ R(S) ,?S ? V
图6.36 Hall婚配定理

谢 谢!
——《应用离散数学(第2版)》

更多样书申请和资源下载需求,请登录人邮教育社区 (www.ryjiaoyu.com)

海量图书方便查询
囊括各大品类,您想要的应有尽有
免费申请样书
教师免费申请样书, 我们将安排快递迅速送达
下载配套资源
教学视频、PPT课件、教学案例、 习题答案、模拟试卷等丰富资源 免费下载

优惠购书
教师可以申请最低折扣 学生直接优惠购买图书
成为作者
欢迎写文章/投稿,我们强大 的编辑团队将为您提供专业和
高效的编辑出版服务




友情链接: 高中资料网 职业教育网 成人教育网 理学 大学工学资料