数学建模社区-数学中国

标题: 请教大家关于 中国邮递员 问题 [打印本页]

---

作者: 镕羽    时间: 2013-6-12 09:32
标题: 请教大家关于 中国邮递员 问题
我觉得下面第四步中 求完备匹配 有点问题。
, B/ b7 I- n" c8 ]3 m7 D
1 }  x7 H; }1 o0 {
5 e- S1 D$ @  x. f; Z5 E

5 h5 u1 e  B5 Y/ r0 k上面的图4情况 求出{v1v4，v2v3}组合没错；
但是如果是这样的情况，按照完备匹配法来求就不对了：

就是有可能  v1v3间距离很短（如只有1），v1v2间距离也很短（如只有1）

那选择“倍边”时，就选{v1v4，v1v2，v1v3}，所有奇数度点 都成了偶数，再来找欧拉回路。
! U! ^+ J0 E0 n+ w; n( R( ?/ x% u（这种情况不能用完备匹配法求解）
1 U- y  ?& c9 u5 C$ J% V6 `
$ o! p+ ^+ K7 l8 D- `& q所以就觉得 用完备匹配 找 倍边的 方法不能涵盖所有情况，有点问题。

111111111.jpg (77.42 KB, 下载次数: 449)

2013-6-12 09:25 上传

点击文件名下载附件

222222222.jpg (83.02 KB, 下载次数: 566)

2013-6-12 09:25 上传

点击文件名下载附件

333333.jpg (80.97 KB, 下载次数: 455)

2013-6-12 09:25 上传

点击文件名下载附件

4444444.jpg (15.77 KB, 下载次数: 455)

2013-6-12 09:26 上传

点击文件名下载附件

---

作者: 镕羽    时间: 2013-6-12 09:32
请教大家 哪里想错了？

---

作者: guoxbcqupt    时间: 2013-8-15 17:19
编程试试，看看结果怎么样·····

---

作者: 御剑逍遥    时间: 2013-8-16 17:43
最短路11步     有关知识参考最短路问题

---

作者: 御剑逍遥    时间: 2013-8-16 18:32
由v3  u4  v2   u3   u2   v1   u1   v4   u6         再由u2到v5   加和11   不知对不？
" K+ N# E. t9 m1 {6 c: R- D( J

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5