{"id":1076,"date":"2017-01-11T00:41:56","date_gmt":"2017-01-11T00:41:56","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/?post_type=chapter&#038;p=1076"},"modified":"2019-05-30T16:32:54","modified_gmt":"2019-05-30T16:32:54","slug":"euler-circuits","status":"publish","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/chapter\/euler-circuits\/","title":{"raw":"Euler Circuits","rendered":"Euler Circuits"},"content":{"raw":"<div class=\"textbox learning-objectives\">\r\n<h3>Learning Outcomes<\/h3>\r\n<ul>\r\n \t<li>Determine whether a graph has an Euler path and\/ or circuit<\/li>\r\n \t<li>Use Fleury's algorithm to find an Euler circuit<\/li>\r\n \t<li>Add edges to a graph to create an Euler circuit if one doesn't exist<\/li>\r\n \t<li>Identify whether a graph has a Hamiltonian circuit or path<\/li>\r\n \t<li>Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm<\/li>\r\n \t<li>Identify a connected graph that is a spanning tree<\/li>\r\n \t<li>Use Kruskal's algorithm to form a spanning tree, and a minimum cost spanning tree<\/li>\r\n<\/ul>\r\n<\/div>\r\nIn the first section, we created a graph of the K\u00f6nigsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.\r\n<div class=\"textbox\">\r\n<h3>Euler Path<\/h3>\r\nAn <strong>Euler path<\/strong> is a path that uses every edge in a graph with no repeats. Being a path, it does not have to return to the starting vertex.\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nIn the graph shown below, there are several Euler paths. One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.\r\n\r\n<img class=\"aligncenter wp-image-149 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155125\/Fig2_5_16.png\" alt=\"A graph with four vertices and five edges. Vertex A has edges connecting to Vertices B and C. Vertex B has edges connecting to Vertices A, C, and D. Vertex C has edges connecting to Vertices A, B, and D. Vertex D has edges connecting to Vertices B and C. An Euler path is shown. Path: CABDCB.\" width=\"530\" height=\"211\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Euler Circuit<\/h3>\r\nAn <strong>Euler circuit<\/strong> is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex.\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nThe graph below has several possible Euler circuits. Here\u2019s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.\r\n\r\n<img class=\"aligncenter wp-image-150\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155127\/Fig2_5_17.png\" alt=\"A graph with six vertices and nine edges. Vertex A has edges connecting to Vertices B, C, and D. Vertex B has edges connecting to Vertices C and A. Vertex C has edges connecting to Vertices A, B, E, and F. Vertex D has edges connecting to Vertices A and E. Vertex E has edges connecting to Vertices A, C, D, and F. Vertex F has edges connecting to Vertices C and E. An Euler circuit is shown. Circuit: AECABCFEDA.\" width=\"550\" height=\"188\" \/>\r\n\r\n<\/div>\r\nLook back at the example used for Euler paths\u2014does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit. When we were working with shortest paths, we were interested in the optimal path. With Euler paths and circuits, we\u2019re primarily interested in whether an Euler path or circuit <em>exists<\/em>.\r\n\r\nWhy do we care if an Euler circuit exists? Think back to our housing development lawn inspector from the beginning of the chapter. The lawn inspector is interested in walking as little as possible. The ideal situation would be a circuit that covers every street with no repeats. That\u2019s an Euler circuit! Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.\r\n<div class=\"textbox\">\r\n<h3>Euler\u2019s Path and Circuit Theorems<\/h3>\r\nA graph will contain an Euler path if it contains at most two vertices of odd degree.\r\n\r\nA graph will contain an Euler circuit if all vertices have even degree\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nIn the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex. B is degree 2, D is degree 3, and E is degree 1. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler\u2019s theorems tell us this graph has an Euler path, but not an Euler circuit.\r\n\r\n<img class=\"alignnone wp-image-151\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155128\/Fig2_5_18.png\" alt=\"A graph containing two vertices with odd degrees and three vertices with even degrees.\" width=\"235\" height=\"180\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nIs there an Euler circuit on the housing development lawn inspector graph we created earlier in the chapter? All the highlighted vertices have odd degree. Since there are more than two vertices with odd degree, there are no Euler paths or Euler circuits on this graph. Unfortunately our lawn inspector will need to do some backtracking.\r\n\r\n<img class=\"aligncenter wp-image-152 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155129\/Fig2_5_19.png\" alt=\"Graph with 25 edges and 18 vertices. Seven of the vertices have even degrees, eight of them have odd degrees.\" width=\"657\" height=\"265\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nWhen it snows in the same housing development, the snowplow has to plow both sides of every street. For simplicity, we\u2019ll assume the plow is out early enough that it can ignore traffic laws and drive down either side of the street in either direction. This can be visualized in the graph by drawing two edges for each street, representing the two sides of the street.\r\n\r\n<img class=\"alignnone wp-image-153\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155130\/Fig2_5_20.png\" alt=\"Fig2_5_20\" width=\"250\" height=\"214\" \/>\r\n\r\n<\/div>\r\nNotice that every vertex in this graph has even degree, so this graph does have an Euler circuit.\r\n\r\nThe following video gives more examples of how to determine an Euler path, and an Euler Circuit for a graph.\r\n\r\nhttps:\/\/youtu.be\/5M-m62qTR-s\r\n<h3>Fleury's Algorithm<\/h3>\r\n<div data-canvas-width=\"605.0964705882352\">Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury\u2019s algorithm.<\/div>\r\n<div data-canvas-width=\"590.804117647059\">\r\n<div class=\"textbox\">\r\n<h3 data-canvas-width=\"590.804117647059\">Fleury\u2019s Algorithm<\/h3>\r\n<div data-canvas-width=\"12.044117647058822\">1. Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.<\/div>\r\n<div data-canvas-width=\"12.044117647058822\">2. Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges.<\/div>\r\n<div data-canvas-width=\"12.044117647058822\">3. Add that edge to your circuit, and delete it from the graph.<\/div>\r\n<div data-canvas-width=\"12.044117647058822\">4. Continue until you\u2019re done.<\/div>\r\n<\/div>\r\n<\/div>\r\n<div data-canvas-width=\"181.46470588235292\">\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nFind an Euler Circuit on this graph using Fleury\u2019s algorithm, starting at vertex A.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16190906\/Screen-Shot-2017-03-16-at-12.08.40-PM.png\"><img class=\"aligncenter wp-image-1827\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16190906\/Screen-Shot-2017-03-16-at-12.08.40-PM-300x130.png\" alt=\"Step 1: Original Graph.Choosing edge AD. Circuit so far: AD. Step 2: AD deleted. D is current. Can\u2019t choose DC since that would disconnect graph. Choosing DE.Circuit so far: ADE. Step 3: E is current. From here, there is only one option, so the rest of the circuit is determined. Circuit: ADEBDCA.\" width=\"762\" height=\"330\" \/><\/a>\r\n\r\n&nbsp;\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\nDoes the graph below have an Euler Circuit? If so, find one.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16191250\/Try-It-Now-3-Graph-Theory.png\"><img class=\"alignnone wp-image-1829\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16191250\/Try-It-Now-3-Graph-Theory.png\" alt=\"\" width=\"415\" height=\"241\" \/><\/a>\r\n\r\n<\/div>\r\nThe following video presents more examples of using Fleury's algorithm to find an Euler Circuit.\r\n\r\nhttps:\/\/youtu.be\/vvP4Fg4r-Ns\r\n<h3>Eulerization and the Chinese Postman Problem<\/h3>\r\nNot every graph has an Euler path or circuit, yet our lawn inspector still needs to do her inspections. Her goal is to minimize the amount of walking she has to do. In order to do that, she will have to duplicate some edges in the graph until an Euler circuit exists.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Eulerization<\/h3>\r\n<\/div>\r\n<div>\r\n\r\n<strong>Eulerization <\/strong>is the process of adding edges to a graph to create an Euler circuit on a graph. To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. When two odd degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.\r\n\r\n<\/div>\r\n<\/div>\r\nNote that we can only duplicate edges, not create edges where there wasn\u2019t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn\u2019t one before is akin to installing a new road!\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nFor the rectangular graph shown, three possible eulerizations are shown. Notice in each of these cases the vertices that started with odd degrees have even degrees after eulerization, allowing for an Euler circuit.\r\n<div>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\"><img class=\"alignnone size-full wp-image-1830\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\" alt=\"2 by 4 grid of rectangles. Each intersection has an open dot.\" width=\"137\" height=\"51\" \/><\/a>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\"><img class=\"alignnone size-full wp-image-1831\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\" alt=\"\" width=\"136\" height=\"60\" \/><\/a>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\"><img class=\"alignnone wp-image-1832 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 1:3, right-hand dots on cell 1:3, and lower dots on cell 2:2\" width=\"143\" height=\"61\" \/><\/a>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\"><img class=\"alignnone size-full wp-image-1833\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\" alt=\"\" width=\"137\" height=\"56\" \/><\/a>\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\nIn the example above, you\u2019ll notice that the last eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were eulerizing the graph to find a walking path, we would want the eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the eulerization with the minimal total added weight.\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It now<\/h3>\r\nEulerize the graph shown, then find an Euler circuit on the eulerized graph.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194900\/Untitled5.png\"><img class=\"alignnone size-full wp-image-1834\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194900\/Untitled5.png\" alt=\"Equilateral triangle with dots at vertices labeled A, B, C. There is a smaller triangle which shares the C,D edge with the larger triangle. The smaller triangle has vertices labeled B, C, D.\" width=\"98\" height=\"77\" \/><\/a>\r\n\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nLooking again at the graph for our lawn inspector from Examples 1 and 8, the vertices with odd degree are shown highlighted. With eight vertices, we will always have to duplicate at least four edges. In this case, we need to duplicate five edges since two odd degree vertices are not directly connected. Without weights we can\u2019t be certain this is the eulerization that minimizes walking distance, but it looks pretty good.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195338\/Untitled6.png\"><img class=\"alignnone wp-image-1835 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195338\/Untitled6.png\" alt=\"Graph with 25 edges and 20 vertices.\" width=\"167\" height=\"143\" \/><\/a>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195800\/Untitled7.png\"><img class=\"aligncenter wp-image-1836\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195800\/Untitled7.png\" alt=\"Graph with 30 edges and 18 vertices. 5 of the edges are shown in red to indicate eulerization of the previous image.\" width=\"215\" height=\"185\" \/><\/a>\r\n\r\n<\/div>\r\n<\/div>\r\nThe problem of finding the optimal eulerization is called the Chinese Postman Problem, a name given by an American in honor of the Chinese mathematician Mei-Ko Kwan who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. \u00a0This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.\r\n\r\nUnfortunately, algorithms to solve this problem are fairly complex. Some simpler cases are considered in the exercises\r\n\r\nThe following video shows another view of finding an Eulerization of the lawn inspector problem.\r\n\r\nhttps:\/\/youtu.be\/lUqCtywkskU\r\n\r\n&nbsp;\r\n\r\n<\/div>","rendered":"<div class=\"textbox learning-objectives\">\n<h3>Learning Outcomes<\/h3>\n<ul>\n<li>Determine whether a graph has an Euler path and\/ or circuit<\/li>\n<li>Use Fleury&#8217;s algorithm to find an Euler circuit<\/li>\n<li>Add edges to a graph to create an Euler circuit if one doesn&#8217;t exist<\/li>\n<li>Identify whether a graph has a Hamiltonian circuit or path<\/li>\n<li>Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm<\/li>\n<li>Identify a connected graph that is a spanning tree<\/li>\n<li>Use Kruskal&#8217;s algorithm to form a spanning tree, and a minimum cost spanning tree<\/li>\n<\/ul>\n<\/div>\n<p>In the first section, we created a graph of the K\u00f6nigsberg bridges and asked whether it was possible to walk across every bridge once. Because Euler first studied this question, these types of paths are named after him.<\/p>\n<div class=\"textbox\">\n<h3>Euler Path<\/h3>\n<p>An <strong>Euler path<\/strong> is a path that uses every edge in a graph with no repeats. Being a path, it does not have to return to the starting vertex.<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>In the graph shown below, there are several Euler paths. One such path is CABDCB. The path is shown in arrows to the right, with the order of edges numbered.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-149 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155125\/Fig2_5_16.png\" alt=\"A graph with four vertices and five edges. Vertex A has edges connecting to Vertices B and C. Vertex B has edges connecting to Vertices A, C, and D. Vertex C has edges connecting to Vertices A, B, and D. Vertex D has edges connecting to Vertices B and C. An Euler path is shown. Path: CABDCB.\" width=\"530\" height=\"211\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Euler Circuit<\/h3>\n<p>An <strong>Euler circuit<\/strong> is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex.<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>The graph below has several possible Euler circuits. Here\u2019s a couple, starting and ending at vertex A: ADEACEFCBA and AECABCFEDA. The second is shown in arrows.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-150\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155127\/Fig2_5_17.png\" alt=\"A graph with six vertices and nine edges. Vertex A has edges connecting to Vertices B, C, and D. Vertex B has edges connecting to Vertices C and A. Vertex C has edges connecting to Vertices A, B, E, and F. Vertex D has edges connecting to Vertices A and E. Vertex E has edges connecting to Vertices A, C, D, and F. Vertex F has edges connecting to Vertices C and E. An Euler circuit is shown. Circuit: AECABCFEDA.\" width=\"550\" height=\"188\" \/><\/p>\n<\/div>\n<p>Look back at the example used for Euler paths\u2014does that graph have an Euler circuit? A few tries will tell you no; that graph does not have an Euler circuit. When we were working with shortest paths, we were interested in the optimal path. With Euler paths and circuits, we\u2019re primarily interested in whether an Euler path or circuit <em>exists<\/em>.<\/p>\n<p>Why do we care if an Euler circuit exists? Think back to our housing development lawn inspector from the beginning of the chapter. The lawn inspector is interested in walking as little as possible. The ideal situation would be a circuit that covers every street with no repeats. That\u2019s an Euler circuit! Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.<\/p>\n<div class=\"textbox\">\n<h3>Euler\u2019s Path and Circuit Theorems<\/h3>\n<p>A graph will contain an Euler path if it contains at most two vertices of odd degree.<\/p>\n<p>A graph will contain an Euler circuit if all vertices have even degree<\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>In the graph below, vertices A and C have degree 4, since there are 4 edges leading into each vertex. B is degree 2, D is degree 3, and E is degree 1. This graph contains two vertices with odd degree (D and E) and three vertices with even degree (A, B, and C), so Euler\u2019s theorems tell us this graph has an Euler path, but not an Euler circuit.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-151\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155128\/Fig2_5_18.png\" alt=\"A graph containing two vertices with odd degrees and three vertices with even degrees.\" width=\"235\" height=\"180\" \/><\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Is there an Euler circuit on the housing development lawn inspector graph we created earlier in the chapter? All the highlighted vertices have odd degree. Since there are more than two vertices with odd degree, there are no Euler paths or Euler circuits on this graph. Unfortunately our lawn inspector will need to do some backtracking.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-152 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155129\/Fig2_5_19.png\" alt=\"Graph with 25 edges and 18 vertices. Seven of the vertices have even degrees, eight of them have odd degrees.\" width=\"657\" height=\"265\" \/><\/p>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>When it snows in the same housing development, the snowplow has to plow both sides of every street. For simplicity, we\u2019ll assume the plow is out early enough that it can ignore traffic laws and drive down either side of the street in either direction. This can be visualized in the graph by drawing two edges for each street, representing the two sides of the street.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-153\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155130\/Fig2_5_20.png\" alt=\"Fig2_5_20\" width=\"250\" height=\"214\" \/><\/p>\n<\/div>\n<p>Notice that every vertex in this graph has even degree, so this graph does have an Euler circuit.<\/p>\n<p>The following video gives more examples of how to determine an Euler path, and an Euler Circuit for a graph.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Graph Theory:  Euler Paths and Euler Circuits\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/5M-m62qTR-s?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<h3>Fleury&#8217;s Algorithm<\/h3>\n<div data-canvas-width=\"605.0964705882352\">Now we know how to determine if a graph has an Euler circuit, but if it does, how do we find one? While it usually is possible to find an Euler circuit just by pulling out your pencil and trying to find one, the more formal method is Fleury\u2019s algorithm.<\/div>\n<div data-canvas-width=\"590.804117647059\">\n<div class=\"textbox\">\n<h3 data-canvas-width=\"590.804117647059\">Fleury\u2019s Algorithm<\/h3>\n<div data-canvas-width=\"12.044117647058822\">1. Start at any vertex if finding an Euler circuit. If finding an Euler path, start at one of the two vertices with odd degree.<\/div>\n<div data-canvas-width=\"12.044117647058822\">2. Choose any edge leaving your current vertex, provided deleting that edge will not separate the graph into two disconnected sets of edges.<\/div>\n<div data-canvas-width=\"12.044117647058822\">3. Add that edge to your circuit, and delete it from the graph.<\/div>\n<div data-canvas-width=\"12.044117647058822\">4. Continue until you\u2019re done.<\/div>\n<\/div>\n<\/div>\n<div data-canvas-width=\"181.46470588235292\">\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Find an Euler Circuit on this graph using Fleury\u2019s algorithm, starting at vertex A.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16190906\/Screen-Shot-2017-03-16-at-12.08.40-PM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1827\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16190906\/Screen-Shot-2017-03-16-at-12.08.40-PM-300x130.png\" alt=\"Step 1: Original Graph.Choosing edge AD. Circuit so far: AD. Step 2: AD deleted. D is current. Can\u2019t choose DC since that would disconnect graph. Choosing DE.Circuit so far: ADE. Step 3: E is current. From here, there is only one option, so the rest of the circuit is determined. Circuit: ADEBDCA.\" width=\"762\" height=\"330\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p>Does the graph below have an Euler Circuit? If so, find one.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16191250\/Try-It-Now-3-Graph-Theory.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1829\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16191250\/Try-It-Now-3-Graph-Theory.png\" alt=\"\" width=\"415\" height=\"241\" \/><\/a><\/p>\n<\/div>\n<p>The following video presents more examples of using Fleury&#8217;s algorithm to find an Euler Circuit.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-2\" title=\"Graph Theory:  Fleury&#39;s Algorthim\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/vvP4Fg4r-Ns?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<h3>Eulerization and the Chinese Postman Problem<\/h3>\n<p>Not every graph has an Euler path or circuit, yet our lawn inspector still needs to do her inspections. Her goal is to minimize the amount of walking she has to do. In order to do that, she will have to duplicate some edges in the graph until an Euler circuit exists.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Eulerization<\/h3>\n<\/div>\n<div>\n<p><strong>Eulerization <\/strong>is the process of adding edges to a graph to create an Euler circuit on a graph. To eulerize a graph, edges are duplicated to connect pairs of vertices with odd degree. Connecting two odd degree vertices increases the degree of each, giving them both even degree. When two odd degree vertices are not directly connected, we can duplicate all edges in a path connecting the two.<\/p>\n<\/div>\n<\/div>\n<p>Note that we can only duplicate edges, not create edges where there wasn\u2019t one before. Duplicating edges would mean walking or driving down a road twice, while creating an edge where there wasn\u2019t one before is akin to installing a new road!<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>For the rectangular graph shown, three possible eulerizations are shown. Notice in each of these cases the vertices that started with odd degrees have even degrees after eulerization, allowing for an Euler circuit.<\/p>\n<div>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1830\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16193934\/Untitled1.png\" alt=\"2 by 4 grid of rectangles. Each intersection has an open dot.\" width=\"137\" height=\"51\" \/><\/a><\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1831\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194045\/Untitled2.png\" alt=\"\" width=\"136\" height=\"60\" \/><\/a><\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1832 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194337\/Untitled3.png\" alt=\"2 by 3 grid with dots at intersections. curved lines connecting upper dots on cell 2:1, right-hand dots on cell 1:1, upper dots on cell 1:3, right-hand dots on cell 1:3, and lower dots on cell 2:2\" width=\"143\" height=\"61\" \/><\/a><\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1833\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194534\/Untitled4.png\" alt=\"\" width=\"137\" height=\"56\" \/><\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>In the example above, you\u2019ll notice that the last eulerization required duplicating seven edges, while the first two only required duplicating five edges. If we were eulerizing the graph to find a walking path, we would want the eulerization with minimal duplications. If the edges had weights representing distances or costs, then we would want to select the eulerization with the minimal total added weight.<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try It now<\/h3>\n<p>Eulerize the graph shown, then find an Euler circuit on the eulerized graph.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194900\/Untitled5.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1834\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16194900\/Untitled5.png\" alt=\"Equilateral triangle with dots at vertices labeled A, B, C. There is a smaller triangle which shares the C,D edge with the larger triangle. The smaller triangle has vertices labeled B, C, D.\" width=\"98\" height=\"77\" \/><\/a><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Looking again at the graph for our lawn inspector from Examples 1 and 8, the vertices with odd degree are shown highlighted. With eight vertices, we will always have to duplicate at least four edges. In this case, we need to duplicate five edges since two odd degree vertices are not directly connected. Without weights we can\u2019t be certain this is the eulerization that minimizes walking distance, but it looks pretty good.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195338\/Untitled6.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1835 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195338\/Untitled6.png\" alt=\"Graph with 25 edges and 20 vertices.\" width=\"167\" height=\"143\" \/><\/a><\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195800\/Untitled7.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1836\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16195800\/Untitled7.png\" alt=\"Graph with 30 edges and 18 vertices. 5 of the edges are shown in red to indicate eulerization of the previous image.\" width=\"215\" height=\"185\" \/><\/a><\/p>\n<\/div>\n<\/div>\n<p>The problem of finding the optimal eulerization is called the Chinese Postman Problem, a name given by an American in honor of the Chinese mathematician Mei-Ko Kwan who first studied the problem in 1962 while trying to find optimal delivery routes for postal carriers. \u00a0This problem is important in determining efficient routes for garbage trucks, school buses, parking meter checkers, street sweepers, and more.<\/p>\n<p>Unfortunately, algorithms to solve this problem are fairly complex. Some simpler cases are considered in the exercises<\/p>\n<p>The following video shows another view of finding an Eulerization of the lawn inspector problem.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-3\" title=\"Eulerization\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/lUqCtywkskU?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<\/div>\n\n\t\t\t <section class=\"citations-section\" role=\"contentinfo\">\n\t\t\t <h3>Candela Citations<\/h3>\n\t\t\t\t\t <div>\n\t\t\t\t\t\t <div id=\"citation-list-1076\">\n\t\t\t\t\t\t\t <div class=\"licensing\"><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Original<\/div><ul class=\"citation-list\"><li>Revision and Adaptaion. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Shared previously<\/div><ul class=\"citation-list\"><li>Graph Theory: Euler Paths and Euler Circuits . <strong>Authored by<\/strong>: James Sousa (Mathispower4u.com). <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/5M-m62qTR-s\">https:\/\/youtu.be\/5M-m62qTR-s<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Math in Society. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Graph Theory: Fleury&#039;s Algorthim . <strong>Authored by<\/strong>: James Sousa (Mathispower4u.com). <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/vvP4Fg4r-Ns\">https:\/\/youtu.be\/vvP4Fg4r-Ns<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Hamiltonian circuits. <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/lUqCtywkskU\">https:\/\/youtu.be\/lUqCtywkskU<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><\/div>\n\t\t\t\t\t\t <\/div>\n\t\t\t\t\t <\/div>\n\t\t\t <\/section>","protected":false},"author":21,"menu_order":6,"template":"","meta":{"_candela_citation":"[{\"type\":\"cc\",\"description\":\"Graph Theory: Euler Paths and Euler Circuits \",\"author\":\"James Sousa (Mathispower4u.com)\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/5M-m62qTR-s\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Graph Theory: Fleury\\'s Algorthim \",\"author\":\"James Sousa (Mathispower4u.com)\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/vvP4Fg4r-Ns\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Hamiltonian circuits\",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/lUqCtywkskU\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"original\",\"description\":\"Revision and Adaptaion\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","CANDELA_OUTCOMES_GUID":"80215870-7383-4d4b-857c-1cd4400fa939","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-1076","chapter","type-chapter","status-publish","hentry"],"part":1193,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapters\/1076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":18,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapters\/1076\/revisions"}],"predecessor-version":[{"id":2966,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapters\/1076\/revisions\/2966"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/parts\/1193"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapters\/1076\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/wp\/v2\/media?parent=1076"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/pressbooks\/v2\/chapter-type?post=1076"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/wp\/v2\/contributor?post=1076"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/wp-json\/wp\/v2\/license?post=1076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}