欢迎来到天天文库
浏览记录
ID：50738433
大小：556.50 KB
页数：9页
时间：2020-03-13
《《运筹》教学课件图论与网络第六章（二）树和最小支撑树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§6.2树一、树的概念(Tree)无圈的连通图称为树二、树的性质性质1如果树T的点数不小于2，那么至少有两个悬挂点性质2如果一个图G具有n个顶点，那么图G是一个树的充分必要条件是图G不含圈且恰有n-1条边。性质3如果一个图G具有n个顶点，那么图G是一个树的充分必要条件是图G是连通图且恰有n-1条边性质4图G是一个树的充分必要条件是任意两个顶点恰有一条链二、树的性质设T是一个点数大于3的树，则下列六个定义是等价的：（1）T连通且无回路；（2）T有条边且无回路；（3）T连通且有条边；（4）T连通且每条边都是割
2、边；（5）T的任两点间都有唯一的路相连；（6）T无回路，但在任一对不相邻的点间加连一条边，则构成唯一的一个回路。三、图的支撑树(minimumspanningtree)三、图的支撑树(minimumspanningtree)三、图的最小支撑树图G权最小的支撑树称为最小支撑树算法1(避圈法，Kruskal法)将边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止(n为顶点数)。154233.5三、图的最小支撑树算法2(破圈法)在图中找圈，并删除其中最大边.如此进行下去,直至图中没有
3、圈止.154233.55.57.5三、图的最小支撑树算法3(Prim法)一点一点加入最小支撑树，加入的原则是该点与已加入点中的某一点形成的边是连接已加入点和未加入点的所有边中权重最小的。145233.5
此文档下载收益归作者所有
