欧拉图
概念
定义
欧拉回路:图中经过每条边一次且仅一次的环;
欧拉路径:图中经过每条边一次且仅一次的路径;
欧拉图:有至少一个欧拉回路的图;
半欧拉图:没有欧拉环,但有至少一条欧拉路径的图。
无向图判定条件
- 图是联通的(度数为0的点不用考虑,因为是孤立的点,没影响)~先决条件
- 所有点的度数都是偶数~存在欧拉回路,欧拉图
- 有且仅有两个点的度数是奇数~存在欧拉路径,半欧拉图
两个奇数度数的点一个是路径起点一个是路径终点
证明:因为任意一个点,欧拉环(或欧拉路径)从它这里进去多少次就要出来多少次,故(进去的次数+出来的次数)为偶数,又因为(进去的次数+出来的次数)=该点的度数(根据定义),所以该点的度数为偶数。
有向图判定条件
- 把所有的边强行改为无向边之后(这个图叫原图的基图),联通~先决条件
- 所有点出度等于入度~存在欧拉回路,欧拉图
- 有且仅有两个点出度不等于入度,一个出度比入度大1,另一个入度比出度大1~欧拉路径,半欧拉图
出度比入度大1的点是路径起点,入度比出度大1的点是路径终点
证明:与无向图证明类似,一个点进去多少次就要出来多少次。
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
struct Graph{ int head[MAXN]; int nxt[MAXE]; int ind[MAXN]; int outd[MAXN]; int from[MAXE]; int end[MAXE]; int vis[MAXE]; int q; int V,E; inline void addEdge(int _from,int _to){ from[q] = _from; end[q] = _to; outd[_from]++; ind[_to]++; nxt[q] = head[_from]; head[_from] = q++; } inline void clear(){ q = 1; memset(head, 0, sizeof(head)); memset(nxt, 0, sizeof(nxt)); memset(end, 0, sizeof(end)); memset(vis, false, sizeof(vis)); memset(from, 0, sizeof(from)); memset(ind, 0, sizeof(ind)); memset(outd, 0, sizeof(outd)); } }; stack<int> res; void euler_dfs(Graph &g,int cur){ for (int i = g.head[cur]; i; i = g.nxt[i]) { if (!g.vis[i]) { g.vis[i] = true; //g.vis[i^1] = true; 无向图的时候,取消这句注释 euler_dfs(g,g.end[i]); res.push(i); } } } vector<int> singular; int euler_judge(Graph &g){ singular.clear(); for (int i = 1; i <= g.V; i++) { if (g.ind[i] != g.outd[i]) { singular.push_back(i); } } if (singular.size() == 2) { if(g.ind[singular[0]] == g.outd[singular[0]] + 1){ swap(singular[0],singular[1]); } if(g.ind[singular[0]] + 1 == g.outd[singular[0]] && g.outd[singular[1]] + 1 == g.ind[singular[1]]){ return 1; } return 0;//euler path //判断必须严格,差一点也不行,跑出合适个数的结果都可能是错的! }else if(singular.size() == 0){ for (int i = 1; i<= g.V; i++) { if (g.ind[i]) { singular.push_back(i); } } return 2;//euler loop }else{ return 0;//failed } } //singular[0]是起点 |
October 31, 2015
[…] 如果不会这个知识,请参考:有关欧拉图问题的一些总结。 […]