《运筹学课件第一节图与网络的基本知识》课件.pptVIP

1 1 * * 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 2 3 4 3 1 2 2 3 4 3 3 5 6 * 1 2 2 3 4 3 3 5 6 9 15 总权为m（T）= 4×2+1 × 4+2×4 +2 ×3+3 ×2+3 ×2=38 绿色为叶子; 黑色为层次。 * 例:使用计算机进行图书分类。 现有5类图书共100万册，其中有A类50万册，有B类20万册，有C类5万册，有D类10万册，有E类15万册。问如何安排分拣过程，可使总的运算（比较）次数最小？ 2、最优二叉树的应用 解： 先构造一棵具有5个叶子的最优二叉树，令其叶子的权 分别为50，20，5，10，15，然后构造最优二叉树。 * 5 10 15 20 50 15 30