欧拉图的课题研究 _拉图

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。
其实分解下来定义精华：
欧拉图听名字就知道发明创作者是谁，七桥问题其实是欧拉提出的论文中图论的第一篇论文“哥尼斯堡七桥问题” 。
在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。（其实故事挺迷的，大家都好闲）
为了解决这个问题，欧拉用 A,B,C,D 4个字母代替陆地，作为 4 个顶点，将联结两块陆地的桥用相应的线段表示，于是哥尼斯堡七桥问题就变成了图中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。
然后巨佬就给出了专业的解析过程。
欧拉把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。
后来推论出此种走法是不可能的。
他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最后回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。
手推此处
在使用欧拉图的时候：
我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧拉路径）。
判定的算法思路（这部分如果题目已经可以明确确定是欧拉图，则不用编写）：
在此因主题原因，故不再讨论半欧拉图，只考虑欧拉图。
之前欧拉对于七桥问题的解决思路很好的给我们判断欧拉图是否成立，一些思路。
还是有严谨证明思路与定理来支撑我们判断欧拉图。
欧拉图的定理与性质（常用部分）：
**这一部分我是从巨佬的博客下引用过来的，精简了一下
在此声明非本人原创，传送门：大佬“ DZYO” 的博客
另外，证明我是真的没有完全看懂。
一、
无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。
二、
三、
要想一个图G是欧拉图，图G需要满足两个条件：
针对有向图来说：
1.图G是连通的，不能有孤立的点存在。
2.每个顶点的入度要等于出度。
（离开此点与到达此点的边数相同。）
针对无向图来说：
1.图G是连通的，不能有孤立的点存在。
2.度数为奇数的点的个数为0 。
无向图这里给了一个图解，大家可以看看。挺可爱的。有助理解，但它讲的方面不是很全，如果没有看明白也不用强迫着去看，忽略就好。
要推出几种算法思路，我们需要明确欧拉图的成立条件（上文已简单叙述）
如果只是仅仅需要运用欧拉回路，可直接运用下列算法。

文章插图
欧拉图的算法都有一些缺陷，也有一些优点，请论情况使用。
由此可以推出欧拉图的算法有几种：
dfs&&查并集
dfs算法思想
利用欧拉定理判断出一个图存在欧拉通路或回路后。
【欧拉图的课题研究】选择一个正确的起始顶点，用DFS 算法遍历所有的边（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。