欧拉图

定义

通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。

通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。

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

具有欧拉通路的图称为半欧拉图。

有向图的时候可以类似地定义。

性质

欧拉图中所有顶点的度数都是偶数。

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 中的顺序排成圆形放在圆盘上即可。

练习题

「洛谷 1341」无序字母对

「洛谷 2731」骑马修栅栏


评论