文档介绍：数学实验之八
——树算法及其应用
Mathematical Experiments
2/10/2018
[1] 掌握求最小生成树的Prim算法和Kruscal算法,了解贪婪算法的基本思想,发挥联想力,把知识融会贯通,举一反三。
[2] 初步领会用MATLAB语言编写非数值计算问题的编程技术;
[3] 通过实例学****怎样建立最小生成树模型。
[4] 通过自己提出问题,动手做实验,并在文献检索、调查研究、动手和动脑等方面得到锻炼,提高创造力和解决实际问题的能力。
实验目的
主页
上一页
下一页
2/10/2018
树算法主要内容
范例:制造系统设计的分组技术
引例:计算机网络的线路设计
生成树算法及其MATLAB程序实现
树图——直观形象的表示工具
布置实验
返回
2/10/2018
赵根
赵明
赵亮
赵丽
赵雷
赵虹
赵雨
赵霞
赵云
赵梅
赵松
树图——直观形象的表示工具
类似于自然界中的树
形象地表示家族
2/10/2018
连通图:其中任意两点之间都有路径。
圈:当一条路径的起点和终点是同一顶点时,称这条路径为圈。
1
2
3
4
5

提示
一个连通图
树图——直观形象的表示工具
2/10/2018
树: 没有圈的连通图
树中任意两点间有唯一路径。
树的边数恰好为顶点数减1。
在树中任意去掉一条边,将会不连通。
树中任意两个不相邻顶点间添一边后,就恰好含一个圈。
树图——直观形象的表示工具
2/10/2018
形象地表示家族;
表示行政组织机构;
用树图来列举排列;
用树来分析游戏中的策略;
计算机用树来描述运算顺序;
用树来组织其拥有的资源以便于查找;
在编译程序中,用树来表示源程序语法结构;
在数据库系统中,可用树来组织信息。
树图——直观形象的表示工具
返回
2/10/2018
城市电信局有许多业务如收费,营业,112,114等,希望在全市范围实现计算机联网服务,共享各种资源。一个主要关心的问题是:用数据通讯线把一组站点联结起来,而不允许通讯线在非站点处相交,如何连接可使通讯线的花费最小?
引例:计算机网络的线路设计
2/10/2018
假设各站点间可以铺设通讯线路进行连接的情况如图所示,顶点为站点,边为连接两站点之间的通讯线,边的权为其费用。
1
2
3
4
5
8
6
9
1
5
7
10
3
引例:计算机网络的线路设计
2/10/2018
1)左图中哪些边是多余的?
2)最经济的网络应具备什么特性?
3)如何求出最经济的连接线路图?
引例:计算机网络的线路设计

想
1
2
3
4
5
8
6
9
1
5
7
10
3
2/10/2018