《定义7.5设图g的顶点非空真子集为v1v,在g中一个端》由会员分享，可在线阅读，更多相关《定义7.5设图g的顶点非空真子集为v1v,在g中一个端（36页珍藏版）》请在金锄头文库上搜索。
1、 定义7.5:设图G的顶点非空真子集为V1V, 在G 中一个端点在V1中, 另一端点在V(G)-V1中的所 有边组成的集合称为G的一个断集或称边割,记 为 E(V1(V(G)-V1), 简记为(V1, V(G)-V1)。 当|(V1, V(G)-V1)|=1时, (V1, V(G)-V1)中的那条 边称为割边或 桥。 图 7.2(b) 中边集 e1,e2和 e1,e2,e3,e4都是 断集(边割)。 割集是断集, 反 之不一定。 对于连通图G(V,E), 删去一个割集D, 得到 两个分支, 顶点集分别为V1和V(G)-V1, 割集D是G中一个端点在V1中, 另一端点 在V(G)-V1中的边的全
2、体。 如果在连通图G中, 删去一个断集而不是 一个割集, 那么将得到多于两个分支。 三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至 少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有 公共边, 则这回路含在该生成树中, 这是不可能 的。 定理7.5：任何一个割集和任何生成树至少有一 条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两 个分支, 这与割集的定义相矛盾。 定理7.6：任何一个回路和任何一个割集有 偶数条公共边。 证明：从连通图G中删去一个割集D后, 得到 两个顶点子集V1
3、和V2, 考察G中任一条回路C : (1) 如果C中所有顶点在V1(或V2)中, 则C与D 没有公共边。 (2)如果C中顶点既有一些在V1中, 又有一些 在V2中, 先看D中任何一边, 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1 与V2中的顶点。 定义7.6：设连通图G中给定生成树T, 对 于只包含T中一条枝的割集,称此割集为 关于T的基本割集。 在连通图G中, 对于给定的生成树T, 每一 枝恰对应唯一的一个基本割集。 因为从生成树T中删去一条枝, 将T分为 两棵树, 它将G的顶点集V划分为V1和V- V1, 在G中这两个顶点集之间的连边, 便对
4、应这一枝的唯一的基本割集。 设连通图G有e条边, n个顶点, 给定的生成树T 应有n-1条枝, 所以恰有n-1个基本割集, 这些基 本割集的全体称为生成树T基本割集组。 定义7.7:设连通图G中给定生成树T, 在T中加 一条弦, 恰产生一条回路, 称此回路为关于T的 基本回路。 由定理 7.1 的等价定义 (4) , 可知在T中加一 弦, 产生唯一的回路。 设连通图G有e条边, n个顶点, 给定的生成树 应有n-1条枝, e-n+1条弦, 所以恰有e-n+1条基 本回路, 这些基本回路的全体称为生成树T的 基本回路组。例如图(a)中给定T=e1,e4,e5,e6, 关于T的基本割集 组: e1
5、,e2,e8,e4,e3,e2,e8,e5,e3, e2, e7, e6,e7 基本回路组: e2,e1,e4,e5,e3, e4, e5,e7,e5,e6,e8,e1,e4,7.3最小生成树 定义7.10:设G(V,E,w)是带权连通简单图, w是 从E到实数集的函数。又设T是G的一棵生成 树,T中所有枝的权之和称为T的权,记为W(T) 。具有权 minTW(T)的生成树称为最小生成 树。 这个问题是具有实际意义的。例如G的顶点 表示城市, G的边表示城市间的道路,边的权 表示对应道路的长度, 现在沿着道路架设通讯 线路, 将这些城市联系起来, 要求架设的线路 最短, 这个问题就是求一棵最小
6、生成树的问题 克鲁斯科尔算法的步骤, 通俗地说, 就是先将G 中的边按权从小到大顺序排列, 再从小到大依 次取出每一边作检查。 一开始取权最小的边v1,v6为e1,且w(e1)=l,由e1 导出一个部分子图,然后依次每取一边加入已得 部分子图。 若保持无回路, 将该边与原有部分子图中边导 出一个新的部分子图;若得到回路, 将该边放弃 。 上述过程继续进行, 直到所有边均检查完, 得到 的部分子图就是所求的一棵最小生成树, 如图(b)所示, 这里e1=v1,v6和e2=v7,v2取出后, 取e3为v2,v3,;若改取e3为v3,v7,可得到另一棵最小生成树求最小生成树的克鲁斯科尔(Kruskal
7、)算法 克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带 权连通简单图。 (1)选取G的一边e1,使w(e1)最小,令E1=e1,1i 。 (2)若已选Ei=e1,e2,ei,那么从E-Ei中选取一 边ei+1,满足: 1)Eiei+1的导出子图中不含有回路; 同时 2)w(ei+1)为满足1)E-Ei中的最小; 3)若ei+1存在,则令Ei+1=Eiei+1,i+1i,转(2); 若ei+1不存在,则停,此时Ei导出的子图就是所求 的最小生成树,记为T。 定理7.8:克鲁斯科尔算法所得到的图T是 最小生成树。 证明:首先由定理7.1等价定义(4)(T是无回 路图,且在T的任两个不相邻的顶点
8、之间 添加一边,恰得到一条回路)知T是G的一 棵子树。 并由等价定义(2)可知边数为n-1(T是无回 路图,且e=n-1)，所以为G的生成树。 下面证明T是最小生成树即可。 用反证法证明, 假设T不是G的最小生成树,而S是 G的生成树, 并且 W(S)W(T)。 在生成树T中有n-1条边。 按权从小到大的顺序排列为e1,e2,ek,en-1。 若ek是不在S中的第一条边, 也就是说e1,e2,ek-1 是S和T的公共边。 现在对S进行变换,在S上加边ek得到一条回路, 记 为C ,在C中必有一边eS, 但eT,否则T中有回 路,导致矛盾。 但因为e1,e2,ek-1是S和T的公共边, eS,所
9、以 e1,e2,ek-1和e不构成回路, 根据克鲁斯科尔算法知w(ek)w(e)(否则T应选e) 。 现从Sek中删去e,得到生成树S,由于 w(ek)w(e),所以W(S)W(S),并且S与T 的公共边比S与T的公共边多一条 重复上述过程,每一步作一次树的变换, 使 总权数减少, 最后生成树S变换到生成树T,W(T)W(S), 与假设 W(S)W(T)相矛盾。7.5有根树与二分树 定义7.11：有向图在不考虑弧的方向时是一棵 树, 称该有向图为有向树。 显然有向树是弱连通的。现在将讨论一类重要 的有向树, 即有根树, 定义如下: 定义7.12：若一棵有向树恰有一个顶点的入度 为 0 ,其余所
10、有顶点的入度均为1,则称该有向树 为有根树。入度为 0 的顶点称为有根树的根。 出度为0的顶点称为有根树的树叶。出度非零 的顶点称为分枝点或内点。 在有根树中,从根v到其余每个顶点有唯一的 一条有向路。这一性质由定义 7.12 即可得 出。有根树中还有一些专门术语, 现在介绍 如下: 定义7.13：设u是有根树的分枝点, 若从u到 w有一条弧 (u,w),则称w为u的儿子,或u为w 的父亲。若一个顶点有两个儿子, 则称它们 为兄弟。若从u到z有一条有向路, 则称z是u 的子孙,或称u是z的祖辈。从根到某一顶点v 的路长度称为顶点v的层数。从根到树叶的 最大层数, 称为有根树的高。 如图是有根树
11、, 顶点标号写在圆圈中。顶点 1 是根, 顶点 6, 8, 9, 10, 11, 12 都是树叶, 顶点 1, 2, 3, 4, 5, 7 都是分枝点, 顶点 1 的层数为 0 , 顶 点 2, 3的层数为 1 , 顶点 4, 5, 6, 7, 8 的层数为 2 , 顶点 9, 10, 11, 12 的层数为 3 。 有根树的概念非常重要, 原因在于它描述 了一个离散结构的层次关系, 而层次结构 是一种重要的数据结构, 所以有根树结构 在相当广泛的领域中有它的应用。有时 只要考虑某一层次上某分枝点为根的局 部层次关系, 因此引入下面的概念: 定义7.14：设u是有根树T的任一顶点,以u 为根,
12、u及其所有子孙所组成的顶点集记为 V,u到这些子孙的有向路上所有弧组成的 弧集记为E,称T的子图T(V,E)为以u为 根的子树。 前面讨论有根树时, 没有考虑同一分枝点连出 的弧的次序, 例如图 所示的有根树就是这样, 它 们是相同的有根树。但是在计算机科学中的许 多具体问题(如编码理论和程序语言等)一定要 考虑这种弧的次序。为此,现在引进有序树的概 念。 定义7.15：有根树的每个分枝点连出的弧(或者 有根树的每一个顶点)从左到右用正整数 1,2,i,标上标号,称该有根树为有序树。 在确定树或画树的方式中,这些标号如果清楚的话, 那么 标号可以省略。 如下面2个图中的有序树是不同构的, 对应
13、的有根树却相 同, 即如上图(a)、(b)所示。 (c)可表示一个人的长子有三个孩子, 次子没有孩子; (d)可表示一个人的长子没有孩子,而次子有三个孩子 。 定义7.16:在有序树中,每个分枝点v至多 有m个儿子,称该有序树为m分树。如果 每个分枝点恰有m个儿子,称该有序树为 正则m分树。 一类重要的m分树是二分树和正则二分 树。对于二分树, 一个分枝点的左右两个 儿子为根的子树分别称左子树和右子树 在画有序树时,如果规定将一个分枝点的 儿子放在它下面, 那么弧的箭头就可以省 略, 因为箭头总是朝下的。如前面例子中 的图。 例:算术表达式a-(b+(c/d)+(e/f)可以用图中的二 分树来
14、表示。所有运算对象都处于树叶的位置, 所有运算符处于分枝点的位置。如果将分枝点 连出的弧的次序改变一下, 那么所得到的二分 树对应的算术表达式也就改变了。 定理7.10:在正则二分树中,它的分枝点数i和树 叶数t满足:i=t-1。 证明:因为分枝点儿子的总数为2i等于树的顶点 数减1(这是因为除了根外每个点都是儿子), 而树的顶点可分成两类：分枝点和树叶：即顶 点数=i+t, 因此有2i=i+t-1, 所以i=t-1。 类似可证在正则m分树中有(m-1)i=t-1。 定理7.11：设T是正则二分树,I表示所有分枝点 的路长度之总和,E表示所有树叶的路长度之总 和, 则E=I+2i,其中i是分枝
15、点数。 证明：对分枝点数i进行归纳证明,当i=1时 E=2,I=0,所以E=I+2i。 假设i=k-1时结论成立。 现考察分枝点数i=k的情况,设分枝点v的两 个儿子是树叶,删去v连出的边及其儿子,v的 路长度为l, 由归纳假设知, 在T中,E=I+2(k-1)。 类似可证在正则m分树中有E=(m-1)I+mi, 具体证明作为习题。7.6最优树 考虑远距离通讯中的一个问题,一篇英文字母组 成的短文如何从发送端发出信息, 通过远距离 传输送到接收端。 通常的电报是用长度为5的0和1序列来表示英 文字母和标点符号的, 这种长度为5的0和1序列 组成的集合称为5单位编码。 为了传输一篇短文,将对应的0和1序列组成的信 息串发送出去以后, 在接收端就将此信息串划 分成长度为 5 的序列, 这样就得到对应的短文 。 但在一篇短文中每个字母出现的频率是 不同的, 如表所示。例如e,t的频率要比j,z的频率大很多。为了使短文对应 的信息串的总长度缩短, 首先要求出现次数多的字母用 较短的 0 和 1 序列表示, 出现次数少的字母用较长的 0 和 1 序列表示; 其次要求在接收端能从一个信息串中明确地分 辨出字母所对应的序列。例如字母 a,b,c,d,e分 别用下列 0 和 1 序列表示, 对应关系如下: a
