定义75:设图G的顶点非空真子集为VcV,在G 中一个端点在V1中,另一端点在v(G)V1中的所 有边组成的集合称为G的一个断集或称边割,记 为E(1×(V(G)V1),简记为(VV(G)-V) 当(V1,V(G-V1)=1时,(V1,V(G)-V1)中的那条 边称为割边或桥。 图72(b)中边集 ei.? 和 {e1,e2,e3,e4}都是 断集(边割)。 e8 e4 e3 割集是断集,反 之不一定。 图7.2
定义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,E,删去一个割集D,得 到两个分支, 顶点集分别为V1和v(G)-V1, 割集D是G中一个端点在v1中,另一端点 在ⅴ(G)V中的边的全体。 如果在连通图G中,删去一个断集而不是 一个割集,那么将得到多于两个分支
对于连通图G(V,E), 删去一个割集D, 得 到两个分支, 顶点集分别为V1和V(G)-V1 , 割集D是G中一个端点在V1中, 另一端点 在V(G)-V1中的边的全体。 如果在连通图G中, 删去一个断集而不是 一个割集, 那么将得到多于两个分支
三、割集与回路 定理74:任何一条回路和任何生成树的余树至 少有一条公共边。 证明:如果一条回路和一棵生成树的余树没有 公共边,则这回路含在该生成树中,这是不可能 的。 定理75:任何一个割集和任何生成树至少有一 条公共边。 证明:如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说,删去一个割集后,不能将图G分为两 个分支,这与割集的定义相矛盾
三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至 少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有 公共边, 则这回路含在该生成树中, 这是不可能 的。 定理7.5：任何一个割集和任何生成树至少有一 条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两 个分支, 这与割集的定义相矛盾
D 人玩何一个割集有 个割集D后,得 图7.3 v2)中,则C与D 没有公共边。 (2)如果C中顶点既有一些在V1中,又有一些 在V2中,先看D中任何一边, 它的一个端点在V1中,另一个端点在V2中, 且G中除D中边以外,不再有任何边连接V1 与V2中的顶点
定理7.6：任何一个回路和任何一个割集有 偶数条公共边。 证明：从连通图G中删去一个割集D后, 得 到两个顶点子集V1和V2 , 考察G中任一条回路C : (1) 如果C中所有顶点在V1 (或V2 )中, 则C与D 没有公共边。 (2)如果C中顶点既有一些在V1中, 又有一些 在V2中, 先看D中任何一边, 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1 与V2中的顶点
定义76:设连通图G中给定生成树T,对 于只包含T中一条枝的割集称此割集为 关于T的基本割集。 在连通图G中,对于给定的生成树T,每 枝恰对应唯一的一个基本割集。 因为从生成树T中删去一条枝,将T分为 两棵树,它将G的顶点集Ⅴ划分为V1和V V1,在G中这两个顶点集之间的连边,便 对应这一枝的唯一的基本割集
定义7.6：设连通图G中给定生成树T, 对 于只包含T中一条枝的割集,称此割集为 关于T的基本割集。 在连通图G中, 对于给定的生成树T, 每一 枝恰对应唯一的一个基本割集。 因为从生成树T中删去一条枝, 将T分为 两棵树, 它将G的顶点集V划分为V1和VV1 , 在G中这两个顶点集之间的连边, 便 对应这一枝的唯一的基本割集
给定的生成树T 基本割集,这些 基本割集组。 e 8 e成树T,在T中加 回路为关于T的 图72 例如图(a)中给定T={e1,e4,es,e6},关于T的基本割集 组 {e12e2,eg3,{e4,e3e2eg},{es,e3,e2,e7},{e6,e} 基本回路组: e2.e1.ene se3, e4, es,,e7, es, e6,,e4,)
设连通图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 ,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最小生成树 定义710:设G(V,E,w)是带权连通简单图,w是 从E到实数集的函数。又设T是G的一棵生成 树,T中所有枝的权之和称为T的权记为W(T)。 具有权minW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点 表示城市,G的边表示城市间的道路边的权 表示对应道路的长度,现在沿着道路架设通讯 线路,将这些城市联系起来,要求架设的线路 最短,这个问题就是求一棵最小生成树的问题
7.3最小生成树 定义7.10:设G(V,E,w)是带权连通简单图, w是 从E到实数集的函数。又设T是G的一棵生成 树,T中所有枝的权之和称为T的权,记为W(T)。 具有权 minTW(T)的生成树称为最小生成树。 这个问题是具有实际意义的。例如G的顶点 表示城市, G的边表示城市间的道路,边的权 表示对应道路的长度, 现在沿着道路架设通讯 线路, 将这些城市联系起来, 要求架设的线路 最短,这个问题就是求一棵最小生成树的问题
克鲁斯科尔算法的步骤,通俗地说,就是先将G 中的边按权从小到大顺序排列,再从小到大依 次取出每一边作检查。 开始取权最小的边{v1,6}为e1,且w(e1)=,由e1 导出一个部分子图,然后依次每取一边加入已得 部分子图。 若保持无回路,将该边与原有部分子图中边导 出一个新的部分子图;若得到回路,将该边放弃。 上述过程继续进行,直到所有边均检查完,得到 的部分子图就是所求的一棵最小生成树, 如图(b)所示,这里e1={v1b}和e2={v7,2}取出后, 取e3为{v 25V3j5…9
克鲁斯科尔算法的步骤, 通俗地说, 就是先将G 中的边按权从小到大顺序排列, 再从小到大依 次取出每一边作检查。 一开始取权最小的边{v1 ,v6 }为e1 ,且w(e1 )=l,由e1 导出一个部分子图,然后依次每取一边加入已得 部分子图。 若保持无回路, 将该边与原有部分子图中边导 出一个新的部分子图;若得到回路, 将该边放弃。 上述过程继续进行, 直到所有边均检查完, 得到 的部分子图就是所求的一棵最小生成树, 如图(b)所示, 这里e1={v1 ,v6 }和e2={v7 ,v2 }取出后, 取e3为{v2 ,v3 },;
6 5 2 22 5 yi Di 若改取e为{v3y,可得到另一棵最小生成树 求最小生成树的克鲁斯科尔 Kruskal算法
若改取e3为{v3 ,v7 },可得到另一棵最小生成树 求最小生成树的克鲁斯科尔(Kruskal)算法
克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带 权连通简单图。 (1)选取G的一边e,使w(e1)最小,令E1={e1},1-i (2)若已选E={e1,e2,,},那么从EE中选取 边e1满足: 1)E;∪{e+}的导出子图中不含有回路;同时 2)w(e+1)为满足1)EE中的最小; 3)若e+1存在,则令E计=E1U{et计1→>i转(2) 若e不存在则停,此时E导出的子图就是所求 的最小生成树,记为T
克鲁斯科尔算法:设G(V,E,w)是有n个顶点的带 权连通简单图。 (1)选取G的一边e1 ,使w(e1 )最小,令E1={e1 },1→i。 (2)若已选Ei={e1 ,e2 ,,ei },那么从E-Ei中选取一 边ei+1 ,满足: 1)Ei∪{ei+1 }的导出子图中不含有回路; 同时 2)w(ei+1 )为满足1)E-Ei中的最小; 3)若ei+1存在,则令Ei+1=Ei∪{ei+1 },i+1→i,转(2); 若ei+1不存在,则停,此时Ei导出的子图就是所求 的最小生成树,记为T