02最小生成树

最小生成树,一些常见的树形结构,无向树的定义,无向树:连通无回路的无向图平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数2的顶点,子图,定义设G=,G=是2个图(同为无向图,或同为有向图)若VV且EE,则称G为G的子图,G为G的母图,记作GG若GG且V=V,则称G为G的生成子图设VV且V,以V为顶点集,以两端点都在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的导出子图,生成树,定义设G是无向连通图,若G的生成子图T是一棵树,则称T是G的生成树.G在T中的边称作T的树枝,不在T中的边称作T的弦.T的所有弦的集合的导出子图称作T的余树,例如图中黑边构成生成树红边构成余树,最小生成树,H是G的子图,H所有边的权的和称作H的权,记作W(H).最小生成树:带权图权最小的生成树。,最小生成树的意义：例如城市的通讯系统，网络的顶点代表城市，网络的边的权重代表架设通讯线路的造价，求构建一个连接所有城市的通讯网络所需的最低造价。,求最小生成树的算法,Prim算法Kruskal算法Prim算法特点:将顶点归并，与边数无关，适于稠密网。Kruskal算法特点：将边归并，适于求稀疏网。,Prim算法,Prim算法的matlab程序,例子,T=v1,R=空集，w=0,S=v2,v3,v4,v5,v6,v7,T=v1,v2,R=v1v2,w=2,T=v1,v2,v3,R=v1v2,v1v3,w=5,T=v1,v2,v3,v5,T=v1,v2,v3,v5,v6,T=v1,v2,v3,v5,v6,v7,T=v1,v2,v3,v5,v6,v7,v4,R=v1v2,v1v3,v2v5,w=9,R=v1v2,v1v3,v2v5,v5v6,w=13,R=v1v2,v1v3,v2v5,v5v6,v6v7,w=18,R=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,w=24,Kruskal算法,用Kruskal算法(避圈法)求赋权连通图G的最小树,最小树的权为24，最小树为T=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,数学规划方法，用Lingo解决,根至少有一条边连接到其他点,除根外,每个点只有一条边进入,1表示结点i和j连接，0表示不连接,实例：机器蛇,在未来的某次战争中，我军计划了一次军事行动，目的是劫持敌人的航母。由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络。计划中要将数百条机器蛇投放到航母的各个角落里。由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题。每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你。每条机器蛇上都带有接收、发射系统，可以同时与多条机器蛇通讯。由于整个系统承载的数据量庞大，需要一个固定的通讯网络。情报部门提供了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌。请你设计一个程序，根据以上信息构造通讯网络，要求信息可以在任意两条机器蛇间传递，同时为了避免干扰，通讯网络的总长度要尽可能的短,【输入】输入数据的第一行是一个整数n（n200）表示参战的机器蛇总数。以下n行，每行两个整数xi，yi，为第i支机器蛇的战斗位置。接下来一行是一个整数m（m100）表示航母内部可能产生屏蔽的位置。最后m行，每行四个整数ai，bi，ci，di，表示线段(ai，bi)-(ci，di)处可能有屏蔽，也就是说通讯网络不能跨越这条线段。【输出】输出数据应仅包括一个实数，表示建立的通讯网的最短长度，保留3位小数。如果不能成功建立通讯网，请输出-1.000。,分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工，都在组内完成。假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。,范例：制造系统的分组技术,范例：制造系统的分组技术,设用Mi表示需由机器i加工的零件集，对任意两台机器i,j,定义相异度：,范例：制造系统的分组技术,建模,“”：对称差，分子：在机器i但不在机器j上加工，或在机器j但不在机器i上加工的零件数。分母：或在机器i，或在机器j上加工的零件数。显然01,建模,1)(i,j)=0和(i,j)=1分别表示什么？2)表达了什么？,构造加权图以机器为顶点，作一个完全图，每条边(i,j)被赋