欧拉图

欧拉通路

经过图中每条边一次且仅一次行遍所有顶点的通路.

指向原始笔记的链接

欧拉回路

经过图中每条边一次且仅一次行遍所有顶点的回路.

指向原始笔记的链接

具有欧拉回路的图称为欧拉图.

半欧拉图

具有欧拉通路但无欧拉回路的图.

指向原始笔记的链接

• 平凡图为欧拉图.
• 欧拉通路是生成的简单通路, 欧拉回路是生成的简单回路.
• 环不影响图的欧拉性.

定理 无向图 $G$ 是欧拉图当且仅当 $G$ 连通且无奇数度顶点.

定理 无向图 $G$ 是半欧拉图当且仅当 $G$ 连通且恰有两个奇度顶点.

Fleury 算法

能不走桥就不走桥

寻找欧拉图中一条欧拉回路.

指向原始笔记的链接

定理 有向图 $D$ 是欧拉图当且仅当 $D$ 强连通且每个顶点的入度等于出度.

定理 有向图 $D$ 是半欧拉图当且仅当 $D$ 单向连通且 $D$ 中恰好有两个奇度顶点.

定理 $G$ 是非平凡的欧拉图当且仅当 $G$ 是连通的且为若干个边不重的圈.