欧拉图
定义¶
通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。
通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉通路的图称为半欧拉图。
有向图的时候可以类似地定义。
性质¶
欧拉图中所有顶点的度数都是偶数。
若 G 是欧拉图，则它若干个边不重的圈的并。
判别法¶
G 是欧拉图当且仅当 G 是连通的且没有奇度定点。
G 是半欧拉图当且仅当 G 中恰有两个奇度定点。
求欧拉回路¶
Fleury 算法¶
也称避桥法。
算法流程为每次选择下一条边的时候优先选择不是桥的边。
逐步插入回路法¶
算法流程为从一条边开始，每次任取一条目前回路中某顶点关联的边，将其替换为一条简单回路。
应用¶
有向欧拉图可用于计算机译码。
设有 m 个字母，希望构造一个有 m^n 个扇形的圆盘，每个圆盘上放一个字母，使得圆盘上每连续 n 位对应长为 n 的符号串。转动一周（ m^n 次）后得到由 m 个字母产生的长度为 n 的 m^n 个各不相同的符号串。
构造如下邮箱欧拉图：
设 S = \{a_1, a_2, \cdots, a_m\} ，构造 D=<V, E> ，如下：
V = \{a_{i_1}a_{i_2}\cdots a_{i_{n-1}} |a_i \in S, 1 \leq i \leq n - 1 \}
E = \{a_{j_1}a_{j_2}\cdots a_{j_{n-1}}|a_j \in S, 1 \leq j \leq n\}
规定 D 中顶点与边的关联关系如下：
顶点 a_{i_1}a_{i_2}\cdots a_{i_{n-1}} 引出 m 条边： a_{i_1}a_{i_2}\cdots a_{i_{n-1}}a_r, r=1, 2, \cdots, m 。
边 a_{j_1}a_{j_2}\cdots a_{j_{n-1}} 引入顶点 a_{j_2}a_{j_3}\cdots a_{j_{n}} 。
这样的 D 是连通的，且每个顶点入度等于出度（均等于 m ），所以 D 是有向欧拉图。
任求 D 中一条欧拉回路 C ，取 C 中各边的最后一个字母，按各边在 C 中的顺序排成圆形放在圆盘上即可。
练习题¶
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用