图论真是一个神秘的东西，本来觉得欧拉图不就是一个图，一种图嘛。

结果没想到，在研究过程中，发现了越来越多的问题。全部延展开来，使这个小问题，变成了一堆巨大的问题。

另外，图论与数学推导真的密切相关，如果想要理解到本质是真的很累+很难。

我尽量讲的简化一点，明白一点。

如果有错误，望大佬们指出。

1、欧拉图的定义与起源 2、欧拉图的算法推演过程（性质与定理） 3、几种算法思路 4、参考算法模板？ 5、各种测评题

欧拉图是个经典的图论分析代表，很具有研究图论思想的价值。但是我不知道到底哪种情况下该使用欧拉图。

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。

其实分解下来定义精华：

欧拉回路——图G中经过每条边一次并且仅一次的回路称作欧拉回路。 （一笔画）

其实就是这个图里包含的所有边，我全都走了，并且都只有一次，就可以说这是一个欧拉路（不一定回到出发点）。我最后回到的是出发点就是欧拉回路。

（这个说法虽然挺不严密，但是很便于理解。）

这里给一个图解，大家理解一下：

半欧拉图——存在欧拉路但不存在欧拉回路的图称为半欧拉图。

欧拉图——存在欧拉回路的图称为欧拉图。

欧拉图听名字就知道发明创作者是谁，七桥问题其实是欧拉提出的论文中图论的第一篇论文“哥尼斯堡七桥问题”。

在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。（其实故事挺迷的，大家都好闲）

为了解决这个问题，欧拉用 A,B,C,D 4个字母代替陆地，作为 4 个顶点，将联结两块陆地的桥用相应的线段表示，于是哥尼斯堡七桥问题就变成了图中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。

然后巨佬就给出了专业的解析过程。

欧拉把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 后来推论出此种走法是不可能的。 他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。

手推此处

在使用欧拉图的时候：

我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧 拉路径）。

在此因主题原因，故不再讨论半欧拉图，只考虑欧拉图。

之前欧拉对于七桥问题的解决思路很好的给我们判断欧拉图是否成立，一些思路。

还是有严谨证明思路与定理来支撑我们判断欧拉图。

欧拉图的定理与性质（常用部分）：

**这一部分我是从巨佬的博客下引用过来的，精简了一下 在此声明非本人原创，传送门：大佬“ DZYO” 的博客

另外，证明我是真的没有完全看懂。

一、

无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。

证明： （系统证明需要从必要性与充分性两个面来进行证明，即充分必要证明）

1、必要性。

设图G的一条欧拉回路为C。由于C经过图G的每一条边，而图G没 有孤立点，所以C也经过图G的每一个顶点，G为连通图成立。而对于图G的任意一个顶点 v，经过C时都是从一条边进入，从另一条边离开，因此v经过C的关联边的次数为偶数。又由于C不重复地经过了图G的每一条边，因此 的度为偶数。

2、充分性

（握手定理：有n个人握手，每人握手x次，握手总次数为S= nx/2。后推导出大量图论定理与性质。不是重点，但传送门：握手定理）

二、

定理2

有向图G为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。

tips: 1、证明类似于无向图。 2、另外，出度、入度类似于角在于高中阶段的定义，按照方向定义“出边”与“入边”。

所谓顶点的度(degree)，就是指和该顶点相关联的边数。

入度 (in-degree) ：以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度

出度 (out-degree) ：以某顶点为弧尾，起始于该顶点的弧的数目称为该顶点的出度

三、

性质1

设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的图G′′,则 G′′的每一个极大连通子图都有一条欧拉回路。

证明

若G为无向图，则图G′′的各顶点的度为偶数；若G为有向图，则图 G′′的各顶点的入度等于出度。

要想一个图G是欧拉图，图G需要满足两个条件：

针对有向图来说：

1.图G是连通的，不能有孤立的点存在。

2.每个顶点的入度要等于出度。

（离开此点与到达此点的边数相同。）

针对无向图来说：

1.图G是连通的，不能有孤立的点存在。

2.度数为奇数的点的个数为0。

无向图这里给了一个图解，大家可以看看。挺可爱的。有助理解，但它讲的方面不是很全，如果没有看明白也不用强迫着去看，忽略就好。

要推出几种算法思路，我们需要明确欧拉图的成立条件（上文已简单叙述）

如果只是仅仅需要运用欧拉回路，可直接运用下列算法。

欧拉图的算法都有一些缺陷，也有一些优点，请论情况使用。

由此可以推出欧拉图的算法有几种：

dfs算法思想

利用欧拉定理判断出一个图存在欧拉通路或回路后。

选择一个正确的起始顶点，用DFS 算法遍历所有的边（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。

这个很简单但挺实用，大家应该对于dfs都很熟悉了，毕竟已经学了图论，不多赘述。

重点！！！

说句实话，fleury算法就是加上割边判定的深搜。

fleury虽然复杂度较差，但实现简单。（所以有什么用）

这个算法是较为高效地运用了图论思想，也是求解欧拉回路最有名且使用广泛的算法之一。

这个算法是弗勒里(B.H.Fleury) 在1883 年给出了在欧拉图中找出一个欧拉环游的多项式时间算法。

运用前我们需要明确“桥”（割边）的含义。

假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。

然后看算法。 其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉回路来。

我下面虽然有实现模板，但我把重点截出来一下。

核心代码挺简单的，主要是对于割边的判断很重要。

并查集一般用来确定图是否连通，然后根据度来判断是否存在欧拉图，递归用来输出路路径。

但递归打印路径时候需要注意：必须先确定里面有欧拉路径，欧拉回路直接打印即可，欧拉通路需要找到起点。

有部分题需要用到这一种算法，但是实现真的挺复杂的。

另外，这玩意儿容易爆栈。

毕竟递归次数有点多。

所以防止爆栈的话用非递归。

这个方法挺迷，参考大佬的博客：dalao传送门

这一部分仅供参考，最好自己实现算法，毕竟欧拉图深搜挺简单的。

选了可读性稍微好一点的模板，主要大部分博客上的代码写得真的很乱，可读性差。前两个模板来自楼上提到的大佬。

1、查并集判断连通图