图论与代数系统.ppt

5.6 树-根树 原则：左小右大、组合优先、左0右1、不足补0 1000101110100101111” ，每次从根结点开始，100(和)0101(上) 110(的)100(和)1011(是)110(不足补0，凑成110，译为“的”) 此处右边5下方的2，3应画在左边，它违反了组合优先 最大分枝 上节讨论无向图的最短树和最长树,最小权根树等问题.由于有的图并不存在根树,所以也不可能存在最大权根树. 根树是一棵有向树,从树根出发向叶子结点出发,能走到每个结点.有时并不成功. 它没有根树,当然也不存在最大权根树了. 分枝:对任何有向图都存在由外向树组成的生成子图(支撑子图)的子图，这种子图称为G的分枝。 在赋权图中，其权值和最大的为最大权分枝。外向树即根树若不能包括所有的点，那你最多能包括多少个点呢？若点数相同，是否存在权值最大？生成树的权和≠权和最大分枝 V1 V2 V3 V4 10 20 15 5 V1 V2 V3 V4 10 20 V1 V2 V3 V4 15 5 最大分枝问题的要求： a)不能产生回路 b)每个结点的负度最多为1,即最大分支中的每个结点最多只有一条入边, 想组成根树。 c)在满足以上两个条件的前提下，使分支各边的权值之和最大。前二者都是根树的要求,但不要求包括所有的点. Edmonds提出的算法： 首先得到一个满足前两个条件的分枝， 然后逐步回扩得到结果。 Edmonds提出的算法： 1) BV=权值最大边端点,边集BE=权值最大边。 2)对未入选结点集V-BV中的v,在形如e=(x,v)的边(入v边即从BV中出去最大边且要保证入度为1)中寻找权最大者, BV=BV+v,　BE=BE+e。 3)如果新添入e后构成回路，则新此回路压缩成一个新点ui，原来与此回路有关的边变成与ui邻接，原来进入此回路的边的权值发生变化=原权值-回路中入原点的边权+回路中最小权 4)针对此新图重复(1)—(3)直到BV=V’(成根树) 5)依次将每次得到的BE中所含的回路回展。回展时上步生成树要保证,入度为1，据此舍弃回路中的边. 即若ui是某棵子树的树根，则去对应回路中的最小边，否则去回路中入“前步生成树”连接点的边。 BV={V5,V7}，BE={v7,v5} 先取边权最大的边 从BV出去的最大边，只有V5,V6 BV={V5,V7,V6},BE={v7,v5,v5,v6} 从BV出去的最大边,只有v6,v7 ，构成回路，将其打扁为u1.入回路的边v8,v7,v3,v5权值改变。 入回边V3-V5的权变为=4-5(回中入V5)+2(回路最小)=1 入回边V8-V7的权变为=1-2(回中入V7)+2((回路最小)=1 V4 V3 V5 V2 V1 V8 V7 V6 1 4 3 4 2 4 5 2 1 1 2 V4 V3 V2 V1 V8 u1 1 3 4 2 1 1 2 BV={v3,v1} BE={v3,v1} BV出去的最大边,v1,v2,若选v1,v8下步仍 BV={v3,v1,v2},BE={v3,v1,v1,v2} BV出去的最大边 BV={v3,v1,v2},BE={v3,v1,v1,v2,v2,v3} 成回路 入回V4-u2权=1-3(回路入原端点V3)+2(回路最小)=0 入回u1-u2权=1-4(回路入原点V1)+2(回路最小)=-1 V4 V3 V2 V1 V8 u1 1 3 4 2 1 1 2 V4 u2 V8 u1 1 1 1 0 2 -1 BV={v8,u2},BE={u2,v8} BV出去最大边 BV={v8,u2,u1},BE={u2,v8,u2,u1} BV出去且保持入度为1的边没有了，只能选择进入BV的边v4,u2,BV={v8,u2,u1,v4}即BV=V 循环结束,下面开始展开汇聚点. V4 u2 V8 u1 1 1 0 2 -1 逆序展开汇点, 前生成树边{u2,v8, u2,u1, V4, u2}， 展后为{v1,v8,v3,u1, v4,v3}， 这些边仍要保存， 而每点的入度只能为1， 故回路中的v2,v3只能舍弃。这时生成树为{v1,v8,v3,u1, v4,v3,v1,v2,v3,v1} V4 u2 V8 u1 1 1 0 2 -1 V4 V3 V2 V1 V8 u1 1 3 4 2 1 1 2 1 x 5.5 平面图与染色问题 有6货物需要堆放，两种货物之间若不能放在同一个仓库，则用一条线相连，其相互关系如下图所示，请问共需要几个仓库。 (1)排序：B(4)、D(4)、A(3)、C(3)、E(3)、F(3) (2)用红色着B，与B不相邻的点是A，故A着成红色。 (3)用兰色着D，与D不相邻的点