第八讲 图论概念和一笔画问题
（教材：第八 章 图论概念和一笔画问题）
二． 欧拉环游及弗莱里算法
这里看一个著名的“七桥问题”：
流经哥尼斯堡的普雷格河的河湾有两个小岛，七座桥连接了两岸和小岛（如图1），当地流传一个游戏：要求在一次散步中恰好通过每座桥一次。
图1
在这个问题中，我们可以将“两个小岛和两岸”看成“点”。连接他们之间的“七座桥”看成“边”，得到图 2。
图 2
“七桥问题”可以归结为“一笔画”问题：即能否用一支笔不离开纸面地画出经过所有桥一次的 路线。用图论的术语，就是一个图是否存在欧拉环游？如果有，如何找出来？
一个图存在欧拉环游的条件是：
网络 N 有欧拉环游当且仅当 N 中每一点的次为偶数。
一般地，一个图能“一笔画”（不要求回到起点），当且仅当该图或没有奇点，或只有 2 个奇点。
利用上述结论，我们判定“七桥问题”不能实现“一笔画”，因为七桥问题中的图有 4 个奇点。
但是要注意，一个图存在欧拉环游，如果方法不对，仍然可能找不到具体的欧拉环游。如下图：
如果从 A 出发我们沿 ABCA 取一条路，则就不可能再继续从 A 出发，走遍余下的边。
上面的例子说明找欧拉环游必须要遵循一定的准则。这就是求一个图的欧拉环游的弗莱里算法。