如何连接通信站使费用最少

1、数学实验数学实验第第12章章 如何连接通信站使费用最少如何连接通信站使费用最少 -最小生成树最小生成树2021-12-8河北大学河北大学Hebei University 数学家之擅长证明缘于对证明过程的大量研读和反复实践。同样，可以通过涉猎引人入胜、特色各异的算法，尝试设计各种问题的解决方法，培养算法设计的成熟性和机敏性。 -作者作者2021-12-8河北大学河北大学Hebei University实验目的实验目的1. 掌握最小生成树的Prim算法和Kruskal算法，了解贪婪算法的基本思想，发挥联想力，把知识融会贯通，举一反三。2. 初步领会用Matlab语言编写非数值计算问题的编程技术；3

2、. 通过实例学习怎样建立最小生成树模型；4. 通过自己提出问题，动手做实验，并在文献检索、调查研究、动手和动脑等方面得到锻炼，提高创造力和解决实际问题的能力。2021-12-8河北大学河北大学Hebei University主要内容主要内容树图树图直观现象的表示工具直观现象的表示工具引例：计算机网络的线路设计引例：计算机网络的线路设计生成树算法及其生成树算法及其MATLAB程序实现程序实现范例：制造系统设计的分组技术范例：制造系统设计的分组技术布置实验布置实验2021-12-8河北大学河北大学Hebei University12.1 树图树图直观形象的表示工具直观形象的表示工具2021-12-

3、8河北大学河北大学Hebei University12.1 树图树图直观形象的表示工具直观形象的表示工具一个连通图一个连通图连通图连通图：其中任意两点之间都有路径，当一条路径的起点和终点是同一顶点时，称这条路径为圈圈2021-12-8河北大学河北大学Hebei University12.1 树图树图直观形象的表示工具直观形象的表示工具 树树：没有圈的连通图 -树中任意两点间有唯一路径。 -树的边数恰好为顶点数减1。 -在树中任意去掉一条边，将 会不连通。 -树中任意两个不相邻顶点间 添一边后，就恰好含一个圈。2021-12-8河北大学河北大学Hebei University12.1 树图树图直

4、观形象的表示工具直观形象的表示工具2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计 城市电信局有许多业 务如收费，营业，112， 114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计假设各站点间可以铺设通讯线路进行连接的情况如图所示，顶点为站点，边为连接两站点之间的通讯线，边的权为

5、其费用。2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计思考：思考：1）左图中哪些是多余的？2）最经济的网络应具备什么特性？3）如何求出最经济的连接路线图？2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计最经济的网络不应该有任何封闭的回路。橡筋圈上剪一刀后，仍然是一个整段。联想2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计生成数或支撑树（spanning tree）：

6、若G的子图T是树，且其顶点集等于G的顶点集。2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计 确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？ 生成树的权：其上所有边权之和。2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计2021-12-8河北大学河北大学Hebei University12.2 引例引例计算机网络的线路设计计算机网络的线路设计2021-12-8河北大学河北大学Hebei Univers

7、ity12.3 生成树算法及其生成树算法及其MATLAB程序实现程序实现Kruskal算法算法的MATLAB程序实现背景聚焦Prim算法2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法思考：1. 计算机如何实现上述非数值计算算法？2. 计算机如何判断一些边是否形成圈？2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法给每个子树一个不同的编号20

8、21-12-8河北大学河北大学Hebei University2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法2021-12-8河北大学河北大学Hebei University2021-12-8河北大学河北大学Hebei UniversityKruskal算法算法2021-12-8河北大学河北大学Hebei University最小生成树算法的背景聚焦最小生成树算法的背景聚焦 1956年，美国电话电报公司（AT&T）利用最小生成树计算出对几家商业客户的索价。 一张大比例的美国地图铺在地板上，寻找联结所有站点的总长度最小的网络。 用手工（并且跪着）

9、操作的方式完成的问题很有限。2021-12-8河北大学河北大学Hebei University最小生成树算法的背景聚焦最小生成树算法的背景聚焦2021-12-8河北大学河北大学Hebei University最小生成树算法的背景聚焦最小生成树算法的背景聚焦2021-12-8河北大学河北大学Hebei UniversityPrim算法算法n算法的手工操作：算法的手工操作：任选一个顶点任选一个顶点v v1 1，将其涂红；，将其涂红；在一个端点为红色，另一个端点为黄色在一个端点为红色，另一个端点为黄色的边中，找一条权最小的边涂红，把该的边中，找一条权最小的边涂红，把该边的黄端点也涂成红色；边的黄端点

10、也涂成红色；重复重复直到所有顶点都成红色为止，最直到所有顶点都成红色为止，最终的红色边和顶点便是最小生成树。终的红色边和顶点便是最小生成树。2021-12-8河北大学河北大学Hebei UniversityPrim算法算法2021-12-8河北大学河北大学Hebei University提示提示2021-12-8河北大学河北大学Hebei University注意注意2021-12-8河北大学河北大学Hebei University12.4 范例：制造系统的分组技术范例：制造系统的分组技术2021-12-8河北大学河北大学Hebei University12.4 范例：制造系统的分组技术范例：

11、制造系统的分组技术2021-12-8河北大学河北大学Hebei University12.4 范例：制造系统的分组技术范例：制造系统的分组技术2021-12-8河北大学河北大学Hebei University12.4 范例：制造系统的分组技术范例：制造系统的分组技术思考思考：1）(i,j)=0和(i,j)=1分别表示什么？ 2）表达了什么？2021-12-8河北大学河北大学Hebei University建模建模2021-12-8河北大学河北大学Hebei University2021-12-8河北大学河北大学Hebei University2021-12-8河北大学河北大学Hebei University2021-12-8河北大学河北大学Hebei University布置实验布置实验2021-12-8河北大学河北大学Hebei University布置实验布置实验2021-12-8河北大