最小生成树(强烈推荐).ppt

赵根
赵明
赵亮
赵丽
赵雷
赵虹
赵雨
赵霞
赵云
赵梅
赵松
树图——直观形象的表示工具
类似于自然界中的树
形象地表示家族
连通图:其中任意两点之间都有路径。
圈:当一条路径的起点和终点是同一顶点时,称这条路径为圈。
1
2
3
4
5
一个连通图
树图——直观形象的表示工具
树: 没有圈的连通图
树中任意两点间有唯一路径。
树的边数恰好为顶点数减1。
在树中任意去掉一条边,将会不连通。
树中任意两个不相邻顶点间添一边后,就恰好含一个圈。
树图——直观形象的表示工具
连通图
任意两个节点之间至少有一条链的图称为连通图
2
4
3
5
1
圈(Cycle)
起点和终点重合的链称为圈
ρ={(1,2),(2,4),(3,4),(1,3)}
圈中各条边方向不一定相同
4
2
3
1
树(Tree)
无圈的连通图称为树
树中只与一条边关联的节点称为悬挂节点
树的性质
任何树至少有一个悬挂节点
2
4
3
5
1
2
4
3
5
1
2
4
3
5
1
如果树的节点个数为m,则边的个数为m-1
树中任意两个节点之间只有唯一的一条链
在树的任意两个不相邻的节点之间增加一条边,则形成唯一的圈
形象地表示家族;
表示行政组织机构;
用树图来列举排列;
用树来分析游戏中的策略;
计算机用树来描述运算顺序;
用树来组织其拥有的资源以便于查找;
在编译程序中,用树来表示源程序语法结构;
在数据库系统中,可用树来组织信息。
树图——直观形象的表示工具
城市电信局有许多业务如收费,营业,112,114等,希望在全市范围实现计算机联网服务,共享各种资源。一个主要关心的问题是:用数据通讯线把一组站点联结起来,而不允许通讯线在非站点处相交,如何连接可使通讯线的花费最小?
引例:计算机网络的线路设计
假设各站点间可以铺设通讯线路进行连接的情况如图所示,顶点为站点,边为连接两站点之间的通讯线,边的权为其费用。
1
2
3
4
5
8
6
9
1
5
7
10
3
引例:计算机网络的线路设计
1)左图中哪些边是多余的?
2)最经济的网络应具备什么特性?
3)如何求出最经济的连接线路图?
引例:计算机网络的线路设计
1
2
3
4
5
8
6
9
1
5
7
10
3
图G
A
B
D
C
E
F
G
A
B
D
C
E
F
G
图G的生成树
A
B
D
C
E
F
G
图G的又一生成树
如果在一棵生成树上添加一条边,必定构成一个环;因为这条边使得它依附的那两个顶点之间有了第二条路径。
一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边,如果一个图有n个顶点和小于(n-1)条边,则是非连通图。如果它多于(n-1)条边,则一定有回路。
有(n-1)条边的图不一定都是生成树。