1、有有 向向 图图应用离散数学第6章21世纪高等教育计算机规划教材目录6.1 有向图概述6.2 根 树6.3 网络流6.4 匹 配 很多应用问题涉及有向图。有向图除了（无向）图类似的性质之外，还有一些（无向）图所不具备的特殊性质。本章除介绍有向图的基本概念外，着重介绍根树、网络流及其应用等。6.1 有向图概述6.1.1 基本概念 在有向图中，若两个顶点之间有两条或两条以上的边，并且方向相同，则称它们为平行边，它强调了边的方向性。有向图中的其他一些概念，像图的阶、零图、平凡图、环、带环图、无环图、简单图、多重图、图、邻接、关联、孤立点、孤立边、二部图、赋权图、子图、真子图、导出子图、生成子图、奇点
2、、偶点、悬挂点、悬挂边等，都与（无向）图中相应概念的定义一样，这里不再重复。()pq，6.1.2 有向图的连通性 在有向图中，通路、回路、通路的长度、简单通路、简单回路、基本通路、基本回路等概念与无向图中相应概念非常类似，只要注意有向边方向的一致性即可。有向图中从一点到另一点的距离的定义与（无向）图中的定义类似，距离的记号为 ，不过它是有向的。（无向）图中的距离满足非负性、对称性和三角不等式，但有向图中距离只满足非负性和三角不等式，不满足对称性。有向图的连通性比（无向）图的连通性包含了更多的内容，下面我们来讨论它。duv，例6.1 图6.1所示的有向图中，（a）是强连通的，（b）是单向连通的，
3、（c）是弱连通的。图图6.1 有向图的连通性有向图的连通性例6.2 图6.2是一个单向连通图，当然也是弱连通图，但不是强连通图，它有两个强连通分图，分别为2，3，4，5，和 。1，图图6.2 单项连通有向图单项连通有向图 图图6.3 弱连通有向图弱连通有向图 图6.3是弱连通图，不是单向连通图，当然也就不是强连通图。它有2个单向连通分图，3个强连通分图。2个单向连通分图分别是4，5，和1，2，3，4，6，。3个强连通分图分别是1，2，3，6，和 。4，5，从例6.2还可以看到，有向图的每一个顶点都唯一地属于某一个强连通分图，这是因为相互可达 是有向图顶点集合上的等价关系。该等价关系将顶点集划分
4、成互不相交的几部分，每部分对应于一个强连通分图。不过，由于可达 仅仅是有向图顶点集合上的二元关系，而不是等价关系，所以“有向图的每一个顶点都唯一地属于某一个单向连通分图”并不成立，例如，图6.3中的顶点4就同时属于两个单向连通分图。对于有向图的有向边，则相反，即每条有向边都唯一地属于某一个单向连通分图，如图6.3所示，但“有向图的每一条有向边都唯一地属于某一个强连通分图”却不成立，例如，图6.2中的有向边和，以及图6.3中的有向边和。由于弱连通分图是根据有向图的底图的连通性定义的，所以有向图的每一个顶点都唯一地属于某一个弱连通分图，每一条有向边也唯一地属于某一弱连通分图。下面给出强连通图和单向
5、连通图的判别定理。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.2的结果一致。6.2 根 树6.2.1 基本概念 设D 是有向图，若 D 的底图是（无向）树，则称D 为有向树
6、。在所有的有向树中，根树最重要，所以我们这里只讨论根树。定义6.8 设T 为有向树，若T 中有一个顶点的入度为0，其余的顶点的入度均为1，则称 为根树。入度为0的顶点称为根结点，又称树根，入度为1的顶点称为子结点。出度为0的顶点称为树叶，出度不为0的顶点称为分支点。既不是树叶又不是树根的顶点称为内点。从树根到任意顶点 v 的路的长度称为v 的层数，层数最大的顶点的层数称为树高。将平凡图也看成根树，称为平凡树。在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方。图6.7所示的根树中，有8片树叶，6个内点，7个分支点，它的高度为5，在树叶u 或 v 处达
7、到。常将根树看成家族树，家族中成员之间的关系可由下面的定义给出。图图6.7 可以证明如果在一次单淘汰赛中，有 n 名选手，则一共要有n-1 场比赛。这是因为参赛选手的数目与树叶的数目一样多，比赛次数 与i分支点数目一样多，因此由定理6.4，i=n-1。图图6.8 单淘汰赛图（正则二叉树）单淘汰赛图（正则二叉树）6.2.2 二叉搜索树 设集合 S 是有序集合，例如，S 由数字组成，可以按照数的大小排序，如果 S 由字符串组成，可以按照字典序排序。二叉树可以用来存储有序集合的元素，比如数字集合或字符串集合。下面给出它的形式化定义。定义6.12 二叉搜索树是一种二叉树，它对应于某个有序集合。有序集合
8、里的数据都存放在二叉树的顶点之中，使得对于树中的任意顶点v，v 的左子树中的任意数据都比 v 中的数据小，而 v的右子树中的任意数据都比 v 中的数据大。例6.5 下面的一组词OLD PROGRAMMERS NEVER DIETHEY JUST LOSE THEIR MEMORIES 可以放在如图6.9所示的二叉搜索树上（根据字母表），对于任意顶点 v 来说，v 的左子树上的任意数据项都比v 中的数据项小，而 v 的右子树上的任意数据项都比v 中的数据项大。图图6.9 一棵二叉搜索树一棵二叉搜索树 一般来说，有很多方法将有序数据放入二叉搜索树中，图6.10展示了另一种存储例6.5中词的二叉搜索
9、树。图图6.10 例例6.5的另一种二叉搜索树的另一种二叉搜索树 用二叉搜索树存储有序数据后，查找数据非常方便。例如，查找数据data，我们从根结点查起，将data与当前顶点的数据不断进行比较，如果data与当前顶点的数据相等，则找到data，停止。如果小于当前顶点v 的数据，则移动到v 的左子结点，重复上述操作。如果data大于当前顶点v的数据，则移动到v 的右子结点，重复上述操作。如果要移动到的某个子结点不存在，则可以得出结论认为data不在该树中。当数据不在二叉搜索树上时，搜索的时间花费最多，此时要搜索从树根到树叶的整条路径，因此，二叉树的最大搜索时间与树高成正比。有许多方法可以尽可能地
10、降低二叉搜索树的高度。图图6.11 将二叉搜索树扩展到满二叉树将二叉搜索树扩展到满二叉树6.2.3 最优二叉树图图6.12 非最优二叉树非最优二叉树 以上三棵二叉树都不是带权2，2，3，3，5的最优二叉树，那应该如何求解带权w1，w2，wt（w1w2wt）的最优二叉树呢？下面介绍一种赫夫曼（Huffman）算法，其基本步骤如下。（1）连接权为w1，w2的两片树叶，得一个分支点，其权为w1+w2。（2）在w1+w2，w3，wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。（3）重复（2），直到形成t 1个分支点，t 片树叶为止。由于每一步选择两个最小的权的选法不唯
11、一，且两个最小的权对应的顶点所放左右位置的不同，画出的最优二叉树可能不同，但有一点是肯定的，就是它们的总权值应该相等而且最小，即它们都应该是最优二叉树。例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 出现的频率大体相
12、同，用等长码表示是很好的方法，但当它们出现的频率相差悬殊，为了节省二进制数位，以达到提高效率的目的，就要寻找非等长的编码，用短码表示常用的符号，用长码表示不常用的符号。这里只讨论二元前缀码（简称为前缀码）。例如，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编码为0
13、0100，解码就会产生歧义，可解为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 产生前缀码的二叉
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%求传输它们的最佳前缀码，并求传输 个按上述频率出现的八进制数字需要多少个二进制数字？若是用等长
15、的（长为3）码子传输，需要多少个二进制数字？10(2)nn解 用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
16、。8个码子的集合01，11，001，100，101，0001，00000，00001为前缀码，而且是最佳前缀码。将图6.16（a）表示的二叉树记为 T。易知，即为传输100个按题中给定频率出现的八进制数字所用二进制数字的个数。除了可用树的总权值定义计算 外，还等于各分支点权之和，所以，。()w T()w T()w T()102035601004020285w T 6.3 网络流6.3.1 基本概念 本节使用有向图来讨论网络模型。这里的网络可以是通过货物流的运输网、输送石油的输油管道网、传送数据流的计算机网络或许多其他可能的情况，即所谓的运输网络。我们重点关注的是如何最大化网络的流量，即如何求网
17、络最大流。其他许多表面上看来不是流的问题，也可以用网络流模型来解决。定义6.15 运输网络是一个简单的、赋权有向图G，满足：（1）有一个顶点没有入边，该顶点称为源点，并用 a 表示。（2）有一个顶点没有出边，该顶点称为收点，并用z 表示。（3）有向边(i，j)的权值Cij 是非负数，Cij 称为(i，j)的容量。在本节我们只讨论运输网络，不讨论其他有向网络，所以在本节有时将运输网络简称为网络。网络的流给网络的每条有向边赋予一个不超过这条边容量的流量，而且对于一个既不是源点也不是收点的顶点，流入 的流量等于流出 的流量。下面给出严格的定义。图图6.20 一个运输网络一个运输网络例6.11（泵送网
18、络）图6.21（a）表示一个泵送网络。在网络中，两个城市 A 和 B 的水由3口井w1，w2和w3供给。中间的容量表示在边上。顶点，和 表示中间泵站。为了将这个系统模型化为一个运输网络，需要给出源点和收点。为此，可以将所有的源点合并成一个超源点，将所有的收点合并成一个超收点，从而得到一个等价的运输网络，如图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。而路的最
19、大容量是A 到B 为3000辆车，B 到C 为2000辆车，A 到C 为4000辆车。请将下午6：00至7：00间从A 到C 的交通流表示为网络。网络流也被用在设计高效的计算机网络上。在计算机网络的模型中，顶点是信息中心或交换中心，边表示顶点间传送数据的信道。流表示信道上每秒钟传送的平均比特数，边的容量是对应信道的容量。图图6.22 一个交通流网络一个交通流网络6.3.2 最大流算法 如果图G 是运输网络，G 中的最大流是流量最大的流。在本小节中，给出一个寻求最大流的算法。基本思想很简单从某个初始流开始，反复地增加流的流量直到不能再增加为止，最后得到的流就是一个最大流。初始流可以取为每条边上的
20、流量都是零的流。为了增加一个已知流的流量，必须找出一条从源点到收点的路径，并沿着这条路径增加这个流。设P=(a，b，z)是运输网络G 的底图中一条从a到z的路径（本小节中，说运输网络的路径实际上都是关于底图的）。如果P 中的一条边e的方向是从vi1指向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）所示。图
21、图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=
22、v0，vn=z的网络和顶点数 n。输出：一个最大流 F。图图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，申请
23、人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 的最大匹配是包含了最多数量
24、的边的匹配M；G 的完全匹配是具有如下性质的匹配M：如果 ，则有某个 ，使得(v，w)M。例6.19 （1）在图6.32中，M1=，是一个匹配，表示一些人找到工作；M2=，是一个最大匹配，表示最大数量的人找到工作；例6.18已经说明不可能每个人都找到工作，所以，图6.32没有完全匹配。（2）在图6.33中，M=，是一个完全匹配。匹配问题可以归结为一个运输网络的最大流问题，下面的例子说明如何将匹配问题转化为运输网络的最大流问题。vVwW图图6.32 匹配问题匹配问题 图图6.33 具有完全匹配的例子具有完全匹配的例子例6.20（匹配网络）把有向二部图6.32转换为运输网络。图图6.34 匹配网络
25、匹配网络 下面的定理将匹配问题与匹配网络上的流联系起来，这样，有了匹配网络，就可以通过求解匹配网络上的流来求解匹配问题。例6.21 定理6.11指出，可以通过匹配网络的流来求解匹配，同样，根据匹配也可以求出匹配网络的流。比如，例6.19的匹配M2=，对应的匹配网络的流可以这样给定：指定匹配M2=，中边的流量为1，从顶点A，B，C，D 到顶点J1，J2，J3，J4其他边的流量为0。然后，根据流量守恒给出超源点 到顶点A，B，C，D 的边的流量以及顶点J1，J2，J3，J4到超收点 的流量，如图6.35所示。因为M2=，是最大匹配，所以，此时的流是也最大的。图图6.35 匹配网络的流匹配网络的流定理6.12（Hall婚配定理）设G 是一个匹配问题的相应有向二部图，V 和W 是相应的两个顶点集，所有边的方向都是从V 指向W，则G 存在完全匹配，当且仅当，()SR SSV 图图6.36 Hall婚配定理婚配定理谢 谢!应用离散数学
