跳转至

欧拉图

定义

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

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

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

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

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

性质

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

若 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本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论