图论完整--最小生成树ppt课件

图论及其应用，应用数学学校，这一课的主要内容，最小生成树，(1)，krusker算法，(2)，guanmeigu的圆分裂法，(3)，Prim算法，(4)，计算机中的树的介绍，和(3)最小连接问题：在交通网络中，经常注意能够连接所有站的生成树，以便生成树的所有边权的和最小。例如，假设在某个地方要建五个工厂，并且要修建连接这五个工厂的道路。经过勘探，道路可如下图所示进行铺设。现在每条边的长度已经被测量并标记在地图的相应边上。如果我们要求铺设的道路总长度最短，这不仅可以节约成本，还可以缩短建设周期。如何铺路？不难发现，具有最小代价的连接模式是：最小连接问题的一般公式是：在连通边加权图g中找到一个具有最小总权的生成树。这种生成树称为最小生成树或最小代价树。(1)克鲁斯卡尔算法，(5)克鲁斯卡尔生于：1928。他的三个兄弟是数学家。他于1954年获得普林斯顿大学的博士学位。他的导师是埃尔德斯。他的大部分研究工作是数学和语言学，他主要在贝尔实验室工作。1956年，他发表了一篇包含Kruskar算法的论文，这让他出名了。1、算法思路，从g中的最小边开始，避免圆型扩张。2，算法，(1)，选择边e1以最小化其权重；(2)如果边缘E1，E2，ek已被选中，edge ek 1选自e-E1，E2，因此：(a)、E1、E2、ek 1是无环图，ek 1的权重w(ek 1)尽可能小。当(2)不能继续时，停止。对于示例1，krusker算法用于在下图中找到最小生成树。该算法证明了定理1:任何由krusker算法得到的生成树都必须是最小生成树。证明：设g是一个n阶连通加权图，并使用t *=g E1，E2，en-1来表示通过krusker算法获得的生成树。我们证明它是最小的生成树。设T是g的最小生成树，如果T*T，用krusker算法很容易知道：TT *。因此，让f(T)=k表示最小I值，其中T*中的边ei不在T中.让t=g e1，e2，ek-1、ek、en，考虑：Tek，那么根据树的性质，它一定是一个g的中间圆。当T1=Tek-e时，很容易知道T1也是g的生成树。设e是T中圆Tek的边，但不是T*中的边。这表明T1是最小的树，但这与f(T)的假设相矛盾！所以：T=T*。嘿。10，例2在边权重g中，以下算法可以生成权重最小的路径吗？为什么？算法：(1)选择边缘e1，使得w(e1)尽可能小；(2)如果边缘E1，E2，则从e E1，ei通过以下方法：(a) g E1，E2，ei，ei1是不相交路径的和；(b)w(ei 1)是满足(a)的最小可能权重。(3)当(2)不能继续时停止。解决方案：此方法无法获得最小生成路径。例如，在下图G中，我们使用算法来查找生成路径：算法找到的生成路径是：图中直接选择的生成路径之一是：后者的权重小于前者。(2)关美姑的断环方法基于Kruskar算法，我国著名数学家关美姑教授于1975年提出了最小生成树的断环方法。关美姑(1934-)。中国著名数学家，山东师范大学前任校长。中国运筹学协会第一届和第二届执行理事，第六届CPPCC全国委员会委员。从事运筹学及其应用的研究，最短投递路线问题的研究取得了成果，被命名为中国邮政路线问题，并被纳入经典图论教材和著作。关美姑教授于1957年至1990年在山东师范大学工作。1984年至1990年任山东师范大学校长，1990年至1995年任复旦大学运筹学系主任。自1995年以来，他一直是澳大利亚皇家墨尔本理工学院运输研究中心的高级研究员、国际项目办公室的高级顾问和复旦大学交通管理学院的兼职教授自1986年以来，关教授一直致力于城市交通规划的研究。他率先在中国引进加拿大的EMME型交通规划软件，并取得了一系列重要的研究成果。用断圆法求最小生成树的过程如下：从加权图g的任意一个圆开始，去掉圆中权重最大的边，称为断圆。继续破圆，直到g中没有圆，并且g的最后一个剩余子图是g的最小生成树。关于证明，见0103014，(1975)，38-41。例如，下面图g中的最小生成树是通过使用打圈法找到的。过程如下：Prim算法是Prim在1957年提出的一个著名算法。作者因此而出名。普里姆(1921 -)于1949年获得普林斯顿大学博士学位，是桑迪亚公司的副总裁。Prim算法：对于连通加权图g的任意顶点u，选择与权重值最低的点u相关的边作为最小生成树的第一条边E1；在接下来的边缘E2，E3，en-1，从所有边中选择权重最小的边，所选边只有一个公共端点。该算法可以通过反证法得到证明。也就是说，证明了由Prim算法得到的生成树是最小生成树。下图中的最小生成树是通过Prim算法找到的。过程如下：w(T)=10。示例5中的连通图g的树形图是指其顶点是生成树t1