图论中的欧拉回路

要理解欧拉回路，我们首先要了解图，然后才能轻松地学习欧拉回路。

Graph

图是由非空边的集合和顶点的集合组成的。 图也可以表示为点和线的图形表示。 图的两个线使用点连接。 图的顶点用点表示，图的边用线表示。 两个顶点通过边连接。 在一个图中，至少使用一条边来连接两个顶点。

图可以表示为 G = (V, E)，其中顶点集由 V 表示，边集由 E 表示。边用于连接图的两个顶点。在本节中，我们将学习行进、行进的类型、行进的示例以及更多内容。

欧拉回路

欧拉回路可以描述为一个回路，其中图的每条边都必须只访问一次。 欧拉回路的顶点可以被访问，也可以不被访问。 对于欧拉回路，必须有相同的起始顶点和最后的顶点。 欧拉回路也可以用其他不同的名称来称呼，即欧拉游或欧拉圈。 学习欧拉回路时有三个要点很重要，描述如下

• 所有边仅被覆盖一次。
• 欧拉图的起始顶点和结束顶点必须相同。
• 顶点可以重复，也可以不重复。

欧拉回路也可以用其他定义来解释，描述如下

• 如果图包含一个访问图的所有边的回路，则该连通图称为欧拉回路。
• 如果图包含一个仅访问图的所有边一次且其起始顶点和最后顶点相同的游走，则该连通图称为欧拉回路。 对于欧拉回路，顶点可以重复。
• 如果图包含一个起始和结束于同一顶点的欧拉路径，则该图称为欧拉回路。 换句话说，如果存在一个封闭的欧拉路径，那么它被称为欧拉回路。
• 如果该图的所有顶点都具有偶数度，则该图称为欧拉回路。 如果图中存在任何一个顶点，其度数为奇数，那么这种类型的图不能是欧拉回路。

欧拉回路示例

欧拉回路包含很多例子，并且描述了一些例子，如下所示

示例 1

此示例包含两个图，其中我们有一个无向图和一个有向图，我们需要找到这些图的欧拉回路。

解决方案： 众所周知，如果所有边仅被覆盖一次且起始顶点和最后顶点相同，则图包含欧拉回路。 在这里，我们有连通图。 第一个图是一个无向图，第二个图是一个有向图。 在这里，我们首先检查无向图。 为此，我们从顶点 'A' 开始，然后转到顶点 D、E、A、C、E、F、C、B 和 A。 现在，我们检查有向图。 为此，我们从顶点 'A' 开始，然后转到顶点 E、C、A、B、C、F、E、D 和 A。 在这两条路径中，所有边仅访问一次，并且起始顶点和最后顶点相同，即顶点 A。 因此，这些图满足欧拉回路的属性。 因此，这两个图都包含欧拉回路，如下所示

无向图的欧拉回路：ADEACEFCBA

有向图的欧拉回路：AECABCFEDA

示例 2

此图包含一个图，我们需要找到此图的欧拉回路。

解决方案： 众所周知，如果图的所有顶点都包含偶数度，则图包含欧拉回路。 图中总共有 5 个顶点。 顶点 A 和 C 的度为 4，因为总共有 4 条边在顶点 A 和 C 处相遇。 顶点 B 的度为 2，因为总共有 2 条边在顶点 B 处相遇。

顶点 D 的度为 3，顶点 E 的度为 1。 因此，在此图中，有两个顶点（D 和 E）包含奇数度，并且有 3 个顶点（A、B 和 C）包含偶数度。 因此，此图不满足欧拉回路的属性。 因此，它没有欧拉回路。

示例 3

此图包含一个图，我们需要找到此图的欧拉回路。

解决方案： 众所周知，如果图的所有边仅被覆盖一次，并且起始顶点和最后顶点相同，则图包含欧拉回路。 在这里，我们有一个连通图。 为了检查它，我们从顶点 'V1' 开始，然后转到顶点 V2、V5、V3、V6、V2、V4、V3 和 V1。 在此路径中，所有边都被访问，但起始顶点和最后顶点相同（起始顶点和最后顶点是 V1）。 因此，此图满足欧拉回路的属性。 因此，该图是一个欧拉回路，如下所示

欧拉回路：V1V2V5V3V6V2V4V3V1

示例 4

此图包含一个图，我们需要找到此图的欧拉回路。

解决方案： 众所周知，如果图的所有顶点都包含偶数度，则图包含欧拉回路。 图中总共有 8 个顶点。 顶点 A、G 和 H 的度为 2，因为总共有 2 条边在顶点 A、G 和 H 处相遇。 顶点 E 的度为 1，顶点 C、B 和 D 的度为 3，顶点 F 的度为 4。 因此，在此图中，有四个顶点（C、B、D 和 E）包含奇数度，并且有四个顶点（A、G、H 和 F）包含偶数度。 因此，此图不满足欧拉回路的属性。 因此，它没有欧拉回路。

示例 5

此图包含一个图，我们需要找到此图的欧拉回路。

解决方案： 众所周知，如果所有边仅被覆盖一次，并且起始顶点和最后顶点相同，则图包含欧拉回路。 在这里，我们有一个连通图。 为了检查它，我们从顶点 'A' 开始，然后转到顶点 B、C、F、G、H、C、G、E、D、F 和 A。 在此路径中，所有边都被访问，但起始顶点和最后顶点相同（起始顶点和最后顶点是 A）。 因此，该图满足欧拉回路的属性。 因此，该图是一个欧拉回路，如下所示

欧拉回路：ABCFGHCGEDFA

我们还有另一种方法可以找到此图是否包含欧拉回路。

众所周知，如果图的所有顶点都包含偶数度，则图包含欧拉回路。 图中总共有 8 个顶点。 顶点 A、B、D、E 和 H 的度为 2，因为总共有 2 条边在顶点 A、B、D、E 和 H 处相遇。 顶点 C、F 和 G 的度为 4。 因此，在此图中，所有顶点都包含偶数度。 因此，该图满足欧拉回路的属性。 因此，它具有欧拉回路。

示例 6

此图包含一个图，我们需要找到此图的欧拉回路。

解决方案： 众所周知，如果所有边仅被覆盖一次，并且起始顶点和最后顶点相同，则图包含欧拉回路。 在这里，我们有一个连通图。 为了检查它，我们从顶点 'f' 开始，然后转到顶点 e、a、b、c、a、d、b、e、c、d、e、g 和 f。 在此路径中，所有边都被访问，但起始顶点和最后顶点相同（起始顶点和最后顶点是 f）。 因此，该图满足欧拉回路的属性。 因此，该图是一个欧拉回路，如下所示

欧拉回路：feabcadbecdegf