运筹学一节图与网络的基本知识.pptVIP

-41 1 1 图的基本概念 树实际上是连通图，但没有圈。由所有节点(n)和相应的边(n-1)组成。 生成树与子图、生成子图的关系 （3）破圈法(深探法和广探法核心是避免成圈) 　　步骤：从图G任取一个圈,从圈中任舍弃一条边,将此圈破掉。重复以上步骤直至无圈为止。 练习2：分别使用深探法、广探法、破圈法找出下图的一个生成树 使用深探法找出下图的一个生成树 使用广探法找出下图的一个生成树 使用破圈法找出下图的一个生成树 另一种破圈法：找圈，擦除最大边以破圈。 思考题: 如何将实际应用与最小生成树的算法联系 起来？ 小结： 1、树的概念以及性质。 2、图的生成树：深探法、广探法和破圈法。 3、最小生成树：避圈法和破圈法。 4、根树及其应用。 证明：(1) T是一棵树 证明：(1) T是一棵树 V1 V0 V8 V2 V3 V4 V5 V6 V7 1 4 5 3 2 5 1 1 4 4 2 1 2 3 5 4 定理8:用避圈法(kruskal)算法得到的子图为一棵最小树 V1 V0 V8 V2 V3 V4 V5 V6 V7 1 3 2 1 1 2 1 2 使用电话线最小长度L=1+1+1+1+2+2+2+3=13 2、破圈法 步骤： (1)从图G中任选一棵树T1; (2)加上一条弦e1, T1+ e1中立即生成一个圈。去掉此圈中的最大权边，得到新树T2,以T2代替T1，继续重复检查剩余的弦，直到全部弦检查完毕。 定理9：图G的生成树T为最小树，当且仅当对任一弦e来讲，e是T+e中与之对应的圈ue中的最大权边。 V1 V0 V8 V2 V3 V4 V5 V6 V7 1 4 5 3 2 5 1 1 4 4 2 1 2 3 5 4 例：先求出一棵树T1，加以弦（v1,v2），得到圈{v1v2v0v1}, 去掉最大权边（ v1,v2 ）;再加上弦（ v2,v3 ），得到圈{v2v3v0v2}, 去掉最大权边（ v0,v3 ）……,全部弦。 2 1 3 4 1 4 2 5 4 4 1 5 2 3 5 1 V1 V0 V7 V6 V8 V2 V3 V4 V5 使用电话线最小长度L=1+1+1+1+2+2+2+3=13 赋权图G 1 5 4 2 4 5 3 1 3 4 4 2 1 5 1 2 生成最小树T 1 2 3 1 2 1 1 2 圈1 圈2 圈3 圈4 圈5 圈6 圈7 圈8 使用电话线最小长度L=1+1+1+1+2+2+2+3=13 V1 V6 V3 V4 V5 V2 V7 4 3 2 3 2 4 5 1 7 2 6 7 4 练习3： 破圈法求下图的最小树 最小树的权=3+3+2+2+1+2=13 9 3 17 4 1 23 20 15 16 25 28 36 练习4： 避圈法求下图的最小树 最小树的权=1+4+9+3+17+23=57 v2 v3 v4 v5 v6 v7 v1 根：根树入次=0的点； 叶:根树出次=0的点；其他的顶点为分枝点。 层次：由根到某一顶点的道路长度（假设每边的长度为1），称为点的层次。 四、根树及其应用 1、根树对有向图而言,根树在计算机科学、决策论有重要应用 定义17：如果一个有向图在不考虑边的方向时是一棵树， 此有向图为有向树。 定义18：有向树T,恰好有一个结点入次=0，其余各点入次=1， 树T为根树（外向树）。 V1:根 V1 V4 V9 V8 V7 V6 V5 V2 V10 V3 例 V5,V6,V4,V7,V9,V10：叶 V1,V2.V3,V8：分枝点 V2,V3,V4的层次：1 V5,V6,V7,V8,V9的层次：2 V10层次：3 v1入次=0 其它点入次=1 T 根树 v5,v6出次=0 v4出次=0 v7,v9出次=0 v10出次=0 根树应用:系统的传递关系;指挥系统的上下级关系; 计算机科学的应用 有向树 定义19：在根树中，如果每个顶点的出次等于m或零，称此树为完全m叉树。如每个顶点的出次小于或等于m称此树为m叉树。 当m=2时，为完全二叉树、二叉树。 完全三叉树 四叉树 出次=3 出次=3 出次=0 出次=3 出次=2 出次=4 出次=1 出次=0 算法步骤： （1）将s个叶子按照权大小排序。 （2）将二个具有最小权的叶子合并成一个分枝点，其权p1+p2;将新得到的分枝点作为一个叶子。令s=s-1,如果s=1，停止，否则转（1）。 实际问题中经常讨论叶子上带权的二叉树。有s个叶子的二叉树T各个叶子的权分别为pi,根到叶子的层次为Li(i=1,2,…s),这样叶子的二叉树的总权数 m(T)= 满足总权最小的二叉树为最优二叉树或霍夫曼树。 例：S=6,其权分别为4，3，3，2，2，1，求最优二叉树 1 2