欧拉路径和哈密顿路径

如果您可以在所有顶点之间绘制一条路径而无需重新绘制同一条路径，则该图形是可遍历的。基于此路径，本章将介绍一些类别，例如欧拉路径和欧拉电路。

欧拉之路

欧拉路径仅包含一次“ G”的每个边缘，至少包含一次“ G”的每个顶点。连通图G如果包含欧拉路径，则被认为是可遍历的。

示例

欧拉路径= dcabde。

欧拉巡回赛

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

示例

欧拉路径= abcdagfeca。

欧拉回路定理

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

注-此Euler路径以奇数度的顶点开始，并以奇数度的另一个顶点结束。

示例

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

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

哈密顿路径

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

示例

哈密顿路径-edbac。

注意-

• 欧拉电路仅包含一次图形的每个边。

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

示例

看一下下图-

对于上面显示的图形-

• 欧拉路径存在–错误

• 欧拉回路存在–错误

• 存在哈密顿循环–正确

• 哈密顿路径存在–正确

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