02最小生成树.ppt

《02最小生成树.ppt》由会员分享，可在线阅读，更多相关《02最小生成树.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树一些常见的树形结构无向树的定义无向树无向树:连通无回路的无向图连通无回路的无向图平凡树平凡树:平凡图平凡图森林森林:每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶:树中度数为树中度数为1的顶点的顶点分支点分支点:树中度数树中度数 2的顶点的顶点例如例如(a)(b)子图定定义义设设G=,G=是是2个个图图(同同为为无无向向图图,或同为有向图或同为有向图)若若VV且且EE,则则称称G 为为G的的子子图图,G为为G 的的母母图图,记作记作GG若若GG 且且V=V,则称则称G 为为G的的生成子图生成子图设设VV且且V,以以V 为为顶顶点点集集,以以两两端端点点都

2、都在在V 中的所有中的所有边为边集的边为边集的G的子图称作的子图称作V 的导出子图的导出子图,记作记作GV 设设EE且且E,以以E 为边集为边集,以以E 中边关联的所中边关联的所有顶点为有顶点为顶点集的顶点集的G的子图称作的子图称作E 的导出子图的导出子图,记作记作GE 例子(1),(2),(3)是是(1)的子图的子图,(2),(3)是真子图是真子图,(1)是母图是母图.(1),(3)是是(1)的生成子图的生成子图.(2)是是d,e,f 的导出子图的导出子图,也是也是e5,e6,e7导出子图导出子图.(3)是是e1,e3,e5,e7的导出子图的导出子图aabbccdddeee f f f e1

3、 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)生成树定义定义 设设G是无向连通图是无向连通图,若若G的生成子图的生成子图T是一棵树是一棵树,则则称称T是是G的的生成树生成树.G在在T中的边称作中的边称作T的的树枝树枝,不在不在T中的中的边称作边称作T的的弦弦.T的所有弦的集合的导出子图称作的所有弦的集合的导出子图称作T的的余树余树例如例如 图中黑边构成生成树图中黑边构成生成树红边构成余树红边构成余树最小生成树H是是G的子图的子图,H所有边的权的和称作所有边的权的和称作H的权的权,记作记作W(H).最小生成树最小生成树:带权图权最小的生成树。带权

4、图权最小的生成树。最小生成树的意义：最小生成树的意义：例如城市的通讯系统，网络的顶例如城市的通讯系统，网络的顶点代表城市，网络的边的权重代表架设通讯线路的造点代表城市，网络的边的权重代表架设通讯线路的造价，求构建一个连接所有城市的通讯网络所需的最低价，求构建一个连接所有城市的通讯网络所需的最低造价。造价。求最小生成树的算法vPrim算法vKruskal算法Prim算法特点算法特点:将顶点归并，与边数无关，适于将顶点归并，与边数无关，适于稠密网稠密网。Kruskal算法特点：算法特点：将边归并，适于求将边归并，适于求稀疏网稀疏网。Prim算法Prim算法的matlab程序例子V1V2V3V5V4

5、V6V7237981056124456117243645T=v1R=空集，w=0S=v2,v3,v4,v5,v6,v7T=v1,v2R=v1v2,w=2T=v1,v2,v3R=v1v2,v1v3,w=5T=v1,v2,v3,v5T=v1,v2,v3,v5,v6T=v1,v2,v3,v5,v6T=v1,v2,v3,v5,v6T=v1,v2,v3,v5,v6T=v1,v2,v3,v5,v6,v7T=v1,v2,v3,v5,v6,v7T=v1,v2,v3,v5,v6,v7T=v1,v2,v3,v5,v6,v7T=v1,v2,v3,v5,v6,v7,v4T=v1,v2,v3,v5,v6,v7,v4T=

6、v1,v2,v3,v5,v6,v7,v4T=v1,v2,v3,v5,v6,v7,v4R=v1v2,v1v3,v2v5,w=9R=v1v2,v1v3,v2v5,v5v6,w=13R=v1v2,v1v3,v2v5,v5v6,v6v7,w=18R=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,w=24Kruskal算法用用KruskalKruskal算法算法(避圈法避圈法)求赋权连通图求赋权连通图G G的的最小树最小树V1V2V3V5V4V6V723798105612445611723644565最小树的权为最小树的权为24，最小树为，最小树为T=v1v2,v1v3,v2v5,v5v6

7、,v6v7,v6v4数学规划方法，用Lingo解决根至少有一条边连接到其他点除根外,每个点只有一条边进入1表示结点i和j连接，0表示不连接实例：机器蛇 在未来的某次战争中，我军计划了一次军事行动，目的是劫持敌人的航母。由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整个

8、系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌。请你设计一个程序，根据以上信息构造通讯网络，要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短v【输入】v输入数据的第一行是一个整数n（n200）表示参战的机器蛇总数。v以下n行，每行两个整数xi，yi，为第i支机器蛇的战斗位置。v接下来一行是一个整数m（m100）表示航母内部可能产生屏蔽的位置。v最后m行，每行四个整数ai，bi，ci，di，表示线段(ai，bi)-(ci，di)处可能有屏蔽，也就是说通讯网络不能跨越这条线段。v【输出】v输出数据应

9、仅包括一个实数，表示建立的通讯网的最短长度，保留3位小数。v如果不能成功建立通讯网，请输出-1.000。分分分分组组组组技技技技术术术术是是是是设设设设计计计计制制制制造造造造系系系系统统统统的的的的一一一一种种种种方方方方法法法法，它它它它把把把把生生生生产产产产零零零零件件件件的的的的机机机机器器器器分分分分组组组组，相相相相应应应应地地地地把把把把需需需需生生生生产产产产的的的的零零零零件件件件分分分分类类类类，使使使使零零零零件件件件跨跨跨跨组组组组加加加加工工工工的的的的情情情情形形形形尽尽尽尽量量量量少少少少，最最最最理理理理想想想想的的的的情情情情况况况况是是是是使使使使每每每每

10、个个个个零件的加工，都在组内完成。零件的加工，都在组内完成。零件的加工，都在组内完成。零件的加工，都在组内完成。假假假假设设设设有有有有13131313种种种种零零零零件件件件，需需需需在在在在9 9 9 9台台台台机机机机器器器器上上上上加加加加工工工工。在在在在各各各各台台台台机器上加工的零件号在下表中给出。机器上加工的零件号在下表中给出。机器上加工的零件号在下表中给出。机器上加工的零件号在下表中给出。范例：制造系统的分组技术范例：制造系统的分组技术范例：制造系统的分组技术范例：制造系统的分组技术 设用Mi表示需由机器i加工的零件集，对任意两台机器i,j,定义相异度：范例：制造系统的分组技

11、术范例：制造系统的分组技术建模“”：对称差，：对称差，：对称差，：对称差，分子：在机器分子：在机器分子：在机器分子：在机器i i i i但不在机器但不在机器但不在机器但不在机器j j j j上加工，或在机上加工，或在机上加工，或在机上加工，或在机 器器器器j j j j但不在机器但不在机器但不在机器但不在机器i i i i上加工的零件数。上加工的零件数。上加工的零件数。上加工的零件数。分母：或在机器分母：或在机器分母：或在机器分母：或在机器i i i i，或在机器或在机器或在机器或在机器j j j j上加工的零件数。上加工的零件数。上加工的零件数。上加工的零件数。显然显然显然显然 0 0 0

12、01 1 1 1建模 1)1)(i,j)=0(i,j)=0和和(i,j)=1(i,j)=1分别分别表示什么？表示什么？2)2)表达了什么？表达了什么？构造加权图 以以以以机机机机器器器器为为为为顶顶顶顶点点点点，作作作作一一一一个个个个完完完完全全全全图图图图，每条边每条边每条边每条边(i,j)(i,j)(i,j)(i,j)被赋予权被赋予权被赋予权被赋予权 (i,j)(i,j)(i,j)(i,j)。原问题的转化 加加加加权权权权图图图图的的的的最最最最小小小小生生生生成成成成树树树树是是是是由由由由那那那那些些些些相相相相异异异异度度度度最最最最小小小小的的的的边边边边构构构构成成成成的的的的连连连连通通通通图图图图，如如如如果果果果希希希希望望望望把把把把机机机机器器器器分分分分成成成成k k k k个个个个组组组组，就就就就继继继继续续续续删删删删去去去去最最最最小小小小生生生生成成成成树树树树上上上上权权权权最最最最大大大大的的的的k-1k-1k-1k-1条条条条边边边边。于于于于是是是是得得得得到到到到k k k k个个个个分分分分离离离离的的的的子子子子树树树树，每每每每棵棵棵棵树树树树的的的的顶顶顶顶点点点点集集集集就就就就构构构构成各机器组。成各机器组。成各机器组。成各机器组。建模