欧拉回路
参考自https://blog.csdn.net/qq_41730082/article/details/84927199
参考自《算法竞赛入门经典》
前置定义
欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的通路
欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路
有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。
前置简单证明
不难发现,在欧拉道路中,“进”和“出”是对应的——除起点和终点外,其它点的“进出”此书应该相等。换句话说,除了起点和终点外,其它点的度数应该是偶数
无向图情况
欧拉通路:设G是连通无向图,则称经过G的每条边一次并且仅经过一次的路径为欧拉通路;
欧拉回路:如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路是欧拉回路
欧拉图:具有欧拉回路的无向图G成为欧拉图
有向图情况
欧拉通路:设D是有向图,D的基图连通,则称经过D的每条边一次并且仅有一次的有向路径为有向欧拉通路
欧拉回路:如果有向欧拉通路是有向回路,则称此有向回路为 有向欧拉回路
欧拉图:具有有向欧拉回路的图D称为有向欧拉图
无向图中定理
无向图G存在欧拉通路的充要条件是:G为连通图,并且G仅有两个奇度结点(度数为奇数的顶点)或者无奇度结点。
推论
(1) 当G是仅有两个奇度结点的连通图时,G的欧拉通路必以此两个结点为端点;
(2)当G是无奇度结点的连通图时,G必有欧拉回路
(3)G为欧拉图(存在欧拉回路)的充分必要条件是 G为无奇度结点的连通图
有向图中定理
有向图D存在欧拉通路的充要条件是:D为有向图,D的基图连通,并且所有顶点的出度与入度相等;或者 除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中一个顶点的出度与入度之差为1,另一个顶点的出度与入度之差为-1.
推论
(1)当D除出、入度之差为1,-1的两个顶点之外,其余顶点的出度与入度相等时,D的有向欧拉通路必以出、入度之差为1的顶点作为始点,以出、入度之差为-1的顶点作为终点。
(2)当D的所有顶点的出、入度都相等时,D中存在有向欧拉回路。
(3)有向图D为有向欧拉图的充要条件是 D的基图为连通图,并且所有顶点的出、入度都相等。
求解
dps解法
用欧拉定理判断出一个正确的起点,以此开始遍历,记录下遍历的顺序
1 | //代码是逆序输出 |
Fleury算法
任取G中一顶点v0,令P0=v0;
假设沿Pi=v0e1v1e2v2……eivi走到顶点vi,按下面方法从E(G)-{e1,e2,…,ei}中选ei+1
ei+1与vi相关联
除非无别的边可供选择,否则ei+1不应该是Gi=G-{e1,e2,…,ei}中的桥。当2不能再进行时算法停止。
可以证明的是,当算法停止时,所得到的简单回路Pm=v0e1v1e2v2……emvm,(vm=v0)为G中一条欧拉回路。
代码待更
相关题目
洛谷P1341(并查集+欧拉回路)
板子题,由于copy了题解再慢慢理解慢慢改的,代码规范并不好,有空再改(咕咕咕)
- 很明显看出是用图来做
- n条边,n+1个点解决问题,典型的一笔画问题
- 先判断是否联通
- 再判断是否有解
- 再确定顶点开始搜索
1 | //欧拉回路问题 |