图论 - 可遍历性

如果可以绘制一条经过所有顶点而不重复相同路径的路径，则该图是可遍历的。基于此路径，本章描述了欧拉路径和欧拉回路等一些类别。

欧拉路径

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

例子

欧拉路径 = d-c-a-b-d-e。

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

例子

欧拉路径 = a-b-c-d-a-g-f-e-c-a。

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

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

例子

欧拉路径 − b-e-a-b-d-c-a 不是欧拉回路，但它是欧拉路径。显然它恰好有两个奇数度顶点。

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

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

每个回路都是一个环路，但环路可能包含多个回路。这样的回路称为图 G 的哈密顿回路。

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

例子

哈密顿路径 − e-d-b-a-c。

注意

例子

请看下面的图：

对于上面显示的图：

G 有四个奇数度顶点，因此它不可遍历。通过跳过内部边，该图具有经过所有顶点的哈密顿回路。

打印页面