给定的生成树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