{"id":27168,"date":"2018-01-03T22:01:13","date_gmt":"2018-01-03T16:31:13","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27168"},"modified":"2018-10-31T14:40:18","modified_gmt":"2018-10-31T09:10:18","slug":"python-programming-eulerian-path-circuit-undirected-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-eulerian-path-circuit-undirected-graph\/","title":{"rendered":"Eulerian path and circuit for undirected graph"},"content":{"rendered":"

Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.<\/p>\n

How to find whether a given graph is Eulerian or not?<\/strong><\/span><\/h3>\n

The problem is same as following question. \u201cIs it possible to draw a given graph<\/a> without lifting pencil from the paper and without tracing any of the edges more than once\u201d.<\/p>\n

A 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<\/a>\u00a0which 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)<\/strong> time.<\/p>\n[ad type=\u201dbanner\u201d]\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

Eulerian Cycle<\/strong><\/span><\/h3>\n

An undirected graph<\/a> 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>\n

Eulerian Path<\/strong><\/span><\/h3>\n

An 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>\n

Note that a graph with no edges is considered Eulerian because there are no edges to traverse.<\/p>\n

How does this work?<\/strong><\/span><\/h3>\n

In 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=\u201dbanner\u201d]\n

PYTHON Programming:<\/span><\/h3>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20check%20if%20a%20given%20graph%20is%20Eulerian%20or%20not%0A%23Complexity%20%3A%20O(V%2BE)%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20a%20undirected%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%20%0A%20%20%20%20%23A%20function%20used%20by%20isConnected%0A%20%20%20%20def%20DFSUtil(self%2Cv%2Cvisited)%3A%0A%20%20%20%20%20%20%20%20%23%20Mark%20the%20current%20node%20as%20visited%20%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20i%20in%20self.graph%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%3D%3DFalse%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.DFSUtil(i%2Cvisited)%0A%20%20%0A%20%20%0A%20%20%20%20\u201d\u2019Method%20to%20check%20if%20all%20non-zero%20degree%20vertices%20are%0A%20%20%20%20connected.%20It%20mainly%20does%20DFS%20traversal%20starting%20from%20%0A%20%20%20%20node%20with%20non-zero%20degree\u201d\u2019%0A%20%20%20%20def%20isConnected(self)%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20visited%20%3D%5BFalse%5D*(self.V)%0A%20%0A%20%20%20%20%20%20%20%20%23%20%20Find%20a%20vertex%20with%20non-zero%20degree%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(self.graph%5Bi%5D)%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20there%20are%20no%20edges%20in%20the%20graph%2C%20return%20true%0A%20%20%20%20%20%20%20%20if%20i%20%3D%3D%20self.V-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Start%20DFS%20traversal%20from%20a%20vertex%20with%20non-zero%20degree%0A%20%20%20%20%20%20%20%20self.DFSUtil(i%2Cvisited)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20all%20non-zero%20degree%20vertices%20are%20visited%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%3D%3DFalse%20and%20len(self.graph%5Bi%5D)%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20True%0A%20%0A%20%0A%20%20%20%20\u201d\u2019The%20function%20returns%20one%20of%20the%20following%20values%0A%20%20%20%20%20%20%200%20\u2013%3E%20If%20grpah%20is%20not%20Eulerian%0A%20%20%20%20%20%20%201%20\u2013%3E%20If%20graph%20has%20an%20Euler%20path%20(Semi-Eulerian)%0A%20%20%20%20%20%20%202%20\u2013%3E%20If%20graph%20has%20an%20Euler%20Circuit%20(Eulerian)%20%20\u201d\u2019%0A%20%20%20%20def%20isEulerian(self)%3A%0A%20%20%20%20%20%20%20%20%23%20Check%20if%20all%20non-zero%20degree%20vertices%20are%20connected%0A%20%20%20%20%20%20%20%20if%20self.isConnected()%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23Count%20vertices%20with%20odd%20degree%0A%20%20%20%20%20%20%20%20%20%20%20%20odd%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20len(self.graph%5Bi%5D)%20%25%202%20!%3D0%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20odd%20%2B%3D1%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20\u201d\u2019If%20odd%20count%20is%202%2C%20then%20semi-eulerian.%0A%20%20%20%20%20%20%20%20%20%20%20%20If%20odd%20count%20is%200%2C%20then%20eulerian%0A%20%20%20%20%20%20%20%20%20%20%20%20If%20count%20is%20more%20than%202%2C%20then%20graph%20is%20not%20Eulerian%0A%20%20%20%20%20%20%20%20%20%20%20%20Note%20that%20odd%20count%20can%20never%20be%201%20for%20undirected%20graph\u201d\u2019%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20odd%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%202%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20odd%20%3D%3D%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20odd%20%3E%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%200%0A%20%0A%20%0A%20%20%20%20%23%20Function%20to%20run%20test%20cases%0A%20%20%20%20def%20test(self)%3A%0A%20%20%20%20%20%20%20%20res%20%3D%20self.isEulerian()%0A%20%20%20%20%20%20%20%20if%20res%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20%22graph%20is%20not%20Eulerian%22%0A%20%20%20%20%20%20%20%20elif%20res%20%3D%3D1%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20%22graph%20has%20a%20Euler%20path%22%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20%22graph%20has%20a%20Euler%20cycle%22%0A%20%20%0A%20%20%0A%20%0A%23Let%20us%20create%20and%20test%20graphs%20shown%20in%20above%20figures%0Ag1%20%3D%20Graph(5)%3B%0Ag1.addEdge(1%2C%200)%0Ag1.addEdge(0%2C%202)%0Ag1.addEdge(2%2C%201)%0Ag1.addEdge(0%2C%203)%0Ag1.addEdge(3%2C%204)%0Ag1.test()%0A%20%0Ag2%20%3D%20Graph(5)%0Ag2.addEdge(1%2C%200)%0Ag2.addEdge(0%2C%202)%0Ag2.addEdge(2%2C%201)%0Ag2.addEdge(0%2C%203)%0Ag2.addEdge(3%2C%204)%0Ag2.addEdge(4%2C%200)%0Ag2.test()%3B%0A%20%0Ag3%20%3D%20Graph(5)%0Ag3.addEdge(1%2C%200)%0Ag3.addEdge(0%2C%202)%0Ag3.addEdge(2%2C%201)%0Ag3.addEdge(0%2C%203)%0Ag3.addEdge(3%2C%204)%0Ag3.addEdge(1%2C%203)%0Ag3.test()%0A%20%0A%23Let%20us%20create%20a%20graph%20with%203%20vertices%0A%23%20connected%20in%20the%20form%20of%20cycle%0Ag4%20%3D%20Graph(3)%0Ag4.addEdge(0%2C%201)%0Ag4.addEdge(1%2C%202)%0Ag4.addEdge(2%2C%200)%0Ag4.test()%0A%20%0A%23%20Let%20us%20create%20a%20graph%20with%20all%20veritces%0A%23%20with%20zero%20degree%0Ag5%20%3D%20Graph(3)%0Ag5.test()\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/span><\/h3>\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[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
PYTHON Programming – Eulerian path and circuit for undirected graph – Eulerian Path is a path in graph that visits every edge exactly once.<\/p>\n","protected":false},"author":1,"featured_media":31259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,78385,73906,4148],"tags":[80980,80982,80979,80983,73926,80984,80981,80985],"class_list":["post-27168","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding","category-connectivity","category-graph-algorithms","category-python","tag-euler-tour-geeks-for-geeks","tag-eulerian-graph-example","tag-eulerian-path-directed-graph","tag-fleurys-algorithm","tag-hamiltonian-circuit","tag-hierholzer-algorithm-c","tag-how-to-print-a-eulerian-path-or-circuit","tag-semi-eulerian-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27168","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=27168"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27168\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31259"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}