请教大家关于 中国邮递员 问题

镕羽

我觉得下面第四步中 求完备匹配 有点问题。
7 Q. m2 S% Z. t! _
+ V: c% i) t+ s( A3 Z. z
5 x1 B4 E6 S! V) m: V( b, |
/ ~: [. }8 q4 l( U' }4 r5 ?' a5 F
上面的图4情况 求出{v1v4，v2v3}组合没错；
! ]) @7 q& @& X. {- R8 S但是如果是这样的情况，按照完备匹配法来求就不对了：

$ ^% t6 K6 r* W7 u就是有可能  v1v3间距离很短（如只有1），v1v2间距离也很短（如只有1）

那选择“倍边”时，就选{v1v4，v1v2，v1v3}，所有奇数度点 都成了偶数，再来找欧拉回路。
4 Y9 j; K4 ~! E（这种情况不能用完备匹配法求解）
) M7 C  U! T/ N5 L
6 t4 q: v0 W- S* k, |所以就觉得 用完备匹配 找 倍边的 方法不能涵盖所有情况，有点问题。

御剑逍遥

由v3  u4  v2   u3   u2   v1   u1   v4   u6         再由u2到v5   加和11   不知对不？
& C. b! |( v# g" P! e4 W

御剑逍遥

最短路11步     有关知识参考最短路问题

guoxbcqupt

编程试试，看看结果怎么样·····

镕羽

请教大家 哪里想错了？