三七二十一
LUCKY !

欧拉路径与回路

欧拉路径:经过每条边恰好一次。欧拉回路:起点终点相同。连通图有欧拉回路 ⟺ 所有顶点度数为偶数。有欧拉路径 ⟺ 恰有两个奇度数顶点。

Eulerian circuit: all degrees even. Path: exactly 2 odd degrees.

现实应用

邮差路线规划(中国邮递员问题)、扫雪车路线、DNA序列拼接、电路板检测。

返回