欧拉图（一笔画问题）
欧拉图：从某个节点出发能走到底，使得每条边必须恰好经过一次，（结点可以经过多次）
通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路。
通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图（Euler Graph）。
具有欧拉通路而无欧拉回路的图称为半欧拉图。
欧拉通路(Euler tour)——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路 (Euler circuit)——通过图中每条边一次且仅一次，并且过每一顶点的回路。
无向图：
G有欧拉通路：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。
有向图：
G有欧拉通路：G连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
G有欧拉回路(G为欧拉图)：G连通，G中所有顶点的入度等于出度。
版权声明：本文为匿名原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。