✓ 避圈法
“避圈加小边,连通为止”。即先选择图中权 最小的边,以后每步从未选的边中,选一条权 最小的边,使与已选的边不构成圈,直到图中
所有的点都连通(即不存在孤立点)为止。
.
33
第三节 无向赋权图优化-最小树问题
例1:某城市有六个居民点,道路交通图G如图 所示,现要沿道路铺设煤气管道,将六个居民 点连成网,已知每条道路长度,求使管道长度 最短的铺设方案。
.
31
第三节 无向赋权图优化-最小树问题
2.最小树的充要条件
若T*是图G的一棵树,则当且仅当对T*外的每 条边[vi,vj]有
w ij mw a i1j,w x j1j2 { , w jk }j
时,它是最小树,其中 {wi1j,wj1j2,wjk}j
是树T*内连接点vi和点vj的唯一的链。也就是
说,如果将最小树T*外任意一条边[vi,vj]加入T*
内,得到了唯一的一个圈,那么[vi,vj]是这个圈
上权最大的边。
.
32
第三节 无向赋权图优化-最小树问题
三、最小树问题
求最小树方法:
✓ 破圈法
“找圈去大边,无圈为止”。即在图中作找一 圈,去掉其中权最大的一条边,在余下的图中,
重复这个步骤,直到无圈为止。
起始节点 F_node
终止节点 T_node
是否联通 Impedance
禁行时段 ForbidTime
1
503
1
4
1
2
501
2
4
1
3
502
3
4
1
4
501
4
3
3
7:00-22:00
5
503