How to find whether a given graph is Eulerian or not?<\/strong>
\nThe problem is same as following question. \u201cIs it possible to draw a given graph without lifting pencil from the paper and without tracing any of the edges more than once\u201d.<\/p>\nA graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path. The problem seems similar to Hamiltonian Path which is NP complete problem for a general graph. Fortunately, we can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.<\/p>\n
Following are some interesting properties of undirected graphs with an Eulerian path and cycle. We can use these properties to find whether a graph is Eulerian or not.<\/p>\n[ad type=”banner”]\n
Eulerian Cycle<\/strong>
\nAn undirected graph has Eulerian cycle if following two conditions are true.
\n\u2026.a) All vertices with non-zero degree are connected. We don\u2019t care about vertices with zero degree because they don\u2019t belong to Eulerian Cycle or Path (we only consider all edges).
\n\u2026.b) All vertices have even degree.<\/p>\nEulerian Path<\/strong>
\nAn undirected graph has Eulerian Path if following two conditions are true.
\n\u2026.a) Same as condition (a) for Eulerian Cycle
\n\u2026.b) If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)<\/p>\nNote that a graph with no edges is considered Eulerian because there are no edges to traverse.<\/p>\n
How does this work?<\/strong>
\nIn Eulerian path, each time we visit a vertex v, we walk through two unvisited edges with one end point as v. Therefore, all middle vertices in Eulerian Path must have even degree. For Eulerian Cycle, any vertex can be middle vertex, therefore all vertices must have even degree.<\/p>\n[ad type=”banner”]\nC++ \u00a0programming:<\/p>\n
<\/div>
\/\/ A C++ program to check if a given graph is Eulerian or not#include<iostream>#include <list>using namespace std; \/\/ A class that represents an undirected graphclass Graph{ int V; \/\/ No. of vertices list<int> *adj; \/\/ A dynamic array of adjacency listspublic: \/\/ Constructor and destructor Graph(int V) {this->V = V; adj = new list<int>[V]; } ~Graph() { delete [] adj; } \/\/ To avoid memory leak \/\/ function to add an edge to graph void addEdge(int v, int w); \/\/ Method to check if this graph is Eulerian or not int isEulerian(); \/\/ Method to check if all non-zero degree vertices are connected bool isConnected(); \/\/ Function to do DFS starting from v. Used in isConnected(); void DFSUtil(int v, bool visited[]);}; void Graph::addEdge(int v, int w){ adj[v].push_back(w); adj[w].push_back(v); \/\/ Note: the graph is undirected} void Graph::DFSUtil(int v, bool visited[]){ \/\/ Mark the current node as visited and print it visited[v] = true; \/\/ Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited);} \/\/ Method to check if all non-zero degree vertices are connected.\/\/ It mainly does DFS traversal starting frombool Graph::isConnected(){ \/\/ Mark all the vertices as not visited bool visited[V]; int i; for (i = 0; i < V; i++) visited[i] = false; \/\/ Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; \/\/ If there are no edges in the graph, return true if (i == V) return true; \/\/ Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); \/\/ Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true;} \/* The function returns one of the following values 0 --> If grpah is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) *\/int Graph::isEulerian(){ \/\/ Check if all non-zero degree vertices are connected if (isConnected() == false) return 0; \/\/ Count vertices with odd degree int odd = 0; for (int i = 0; i < V; i++) if (adj[i].size() & 1) odd++; \/\/ If count is more than 2, then graph is not Eulerian if (odd > 2) return 0; \/\/ If odd count is 2, then semi-eulerian. \/\/ If odd count is 0, then eulerian \/\/ Note that odd count can never be 1 for undirected graph return (odd)? 1 : 2;} \/\/ Function to run test casesvoid test(Graph &g){ int res = g.isEulerian(); if (res == 0) cout << "graph is not Eulerian\\n"; else if (res == 1) cout << "graph has a Euler path\\n"; else cout << "graph has a Euler cycle\\n";} \/\/ Driver program to test above functionint main(){ \/\/ Let us create and test graphs shown in above figures Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); test(g1); Graph g2(5); g2.addEdge(1, 0); g2.addEdge(0, 2); g2.addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); test(g2); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); test(g3); \/\/ Let us create a graph with 3 vertices \/\/ connected in the form of cycle Graph g4(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); test(g4); \/\/ Let us create a graph with all veritces \/\/ with zero degree Graph g5(3); test(g5); return 0;}<\/code><\/pre> <\/div>\nOutput:<\/p>\n
graph has a Euler path\r\ngraph has a Euler cycle\r\ngraph is not Eulerian\r\ngraph has a Euler cycle\r\ngraph has a Euler cycle<\/pre>\n\u00a0[ad type=”banner”]<\/div>\n","protected":false},"excerpt":{"rendered":"
C++ programming Eulerian path and circuit – undirected graph. Eulerian Path is a path in graph that visits every edge exactly once.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,78385,73906],"tags":[83844,83843,83846,83845,82292,80982,83839,80979,83842,82294,82293,80983,73926,83841,80981,83840],"class_list":["post-27140","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-connectivity","category-graph-algorithms","tag-circuit-graph-theory","tag-cycle-graph-theory","tag-cyclic-graph-examples","tag-directed-cycle-graph","tag-eulerian-circuit-algorithm","tag-eulerian-graph-example","tag-eulerian-path-and-circuit","tag-eulerian-path-directed-graph","tag-eulerian-path-directed-graph-algorithm","tag-eulerian-path-undirected-graph","tag-fleury-algorithm-directed-graph","tag-fleurys-algorithm","tag-hamiltonian-circuit","tag-hierholzer-algorithm","tag-how-to-print-a-eulerian-path-or-circuit","tag-semi-eulerian"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27140"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27140\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}