数模论坛

 找回密码
 注-册-帐-号
搜索
热搜: 活动 交友 discuz
查看: 5082|回复: 7

破圈法??

[复制链接]
发表于 2003-8-23 20:15:12 | 显示全部楼层 |阅读模式
那天看一个图论的题目也是寻找最小路径(加权无向连通图),书上说用破圈法??
哪位高手可以解释一下这个方法呢?3Q先了[em05]
发表于 2003-8-23 20:22:19 | 显示全部楼层
破圈就是:
Step1:去掉最大的权的边
Step2:判断是否是连通的:yes——》Step1;
                                      not——》Step33;
Step3:不去该边,在不含该边的里面去掉最大边——》Step2;
Step4:没有边可去,结束;
发表于 2003-8-23 20:27:50 | 显示全部楼层
我的看法不全面,高手加加啊
发表于 2003-8-23 20:32:54 | 显示全部楼层
关于破圈法可以参考清华大学出版的运筹学的第六章.
另外寻找最小路径还可以用避圈法.
发表于 2003-8-23 22:02:10 | 显示全部楼层
就是为了不转圈,而去掉部分边。前题是不改变结果
发表于 2003-8-29 06:13:55 | 显示全部楼层
破圈法就是求最小生成树的一种算法,在数据结构书上有现成的//
发表于 2003-8-29 23:36:43 | 显示全部楼层
破圈法其实就是,按照点不重复,保证不能让三条边构成一个回路了,其实说百了就是把所有的点联系起来,但不能两两有回路,着就是说对每一个图形来说,破圈法有很多种了!
发表于 2003-8-29 23:37:24 | 显示全部楼层

破圈法其实就是,按照点不重复,保证不能让三条边构成一个回路了,其实说百了就是把所有的点联系起来,但不能两两有回路,着就是说对每一个图形来说,破圈法有很多种了!
您需要登录后才可以回帖 登录 | 注-册-帐-号

本版积分规则

小黑屋|手机版|Archiver|数学建模网 ( 湘ICP备11011602号 )

GMT+8, 2024-3-29 10:00 , Processed in 0.058137 second(s), 18 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表