跳转至

欧拉图

定义

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

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

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

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

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

性质

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

G是欧拉图,则它若干个边不重的圈的并。

判别法

G是欧拉图当且仅当 G是连通的且没有奇度定点。

G是半欧拉图当且仅当 G中恰有两个奇度定点。

求欧拉回路

Fleury 算法

也称避桥法。

算法流程为每次选择下一条边的时候优先选择不是桥的边。

逐步插入回路法

算法流程为从一条边开始,每次任取一条目前回路中某顶点关联的边,将其替换为一条简单回路。

应用

有向欧拉图可用于计算机译码。

设有 m个字母,希望构造一个有 m^n个扇形的圆盘,每个圆盘上放一个字母,使得圆盘上每连续 n位对应长为 n的符号串。转动一周( m^n次)后得到由 m个字母产生的长度为 nm^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」骑马修栅栏


评论