图论 - 可遍历性

---

如果您可以在所有顶点之间绘制一条路径而无需重新追踪同一路径，则该图是可遍历的。基于这条路径，本章描述了一些类别，例如欧拉路径和欧拉回路。

欧拉路径

欧拉路径包含“G”的每条边恰好一次，并且“G”的每个顶点至少包含一次。如果连通图 G 包含欧拉路径，则称其是可遍历的。

例子

欧拉路径 = dcabde.

欧拉电路

在欧拉路径中，如果起始顶点与其结束顶点相同，则称为欧拉回路。

例子

欧拉路径= abcdagfeca.

欧拉电路定理

连通图“G”是可遍历的当且仅当 G 中具有奇数度的顶点数量恰好为 2 或 0。连通图 G 可以包含欧拉路径，但不能包含欧拉回路，如果它恰好有两个顶点一个奇怪的程度。

注意- 该欧拉路径以奇数度的顶点开始，以奇数度的另一个顶点结束。

例子

欧拉路径- beabdca 不是欧拉电路，但它是欧拉路径。显然它有 2 个奇数度顶点。

注- 在连通图 G 中，如果奇数度的顶点数 = 0，则欧拉回路存在。

哈密​​顿图

如果存在包含 G 的所有顶点的环，则称连通图 G 为哈密顿图。

每个周期都是一个电路，但一个电路可以包含多个周期。这样的循环称为G 的哈密顿循环。

哈密​​顿路径

如果连通图仅包含 G 的每个顶点一次，则称其为哈密顿图。这样的路径称为哈密顿路径。

例子

哈密​​顿路径- edbac。

笔记

• 欧拉电路只包含图的每条边一次。

• 在哈密顿循环中，可以跳过图的某些边。

例子

看一下下图 -

对于上面显示的图表 -

• 欧拉路径存在 – false

• 欧拉回路存在 – false

• 哈密​​顿循环存在——正确

• 哈密​​顿路径存在——正确

G 有四个奇数顶点，因此不可遍历。通过跳过内部边，该图具有穿过所有顶点的哈密顿循环。