{"id":1537,"date":"2023-04-11T14:39:01","date_gmt":"2023-04-11T14:39:01","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=1537"},"modified":"2024-10-18T20:58:09","modified_gmt":"2024-10-18T20:58:09","slug":"euler-and-hamiltonian-paths-and-circuits-learn-it-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-learn-it-1\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Learn It 1","rendered":"Euler and Hamiltonian Paths and Circuits: Learn It 1"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Determine whether a graph has an Euler path or circuit and use Fleury's algorithm to find an Euler circuit<\/li>\r\n\t<li>Recognize whether a graph contains a Hamiltonian circuit or path and determine the optimal Hamiltonian circuit using various algorithms<\/li>\r\n\t<li>Identify a connected graph as a spanning tree and utilize Kruskal's algorithm to create both a spanning tree and a minimum-cost spanning tree<\/li>\r\n<\/ul>\r\n<\/section>\r\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>\r\n<h2>Euler Circuits<\/h2>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Euler path<\/h3>\r\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>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">In the graph shown below, there are several Euler paths. One such path is [latex]CABDCB[\/latex]. The path is shown in arrows to the right, with the order of edges numbered.<center><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\" \/><\/center><\/section>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Euler circuit<\/h3>\r\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>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">The graph below has several possible Euler circuits. Here\u2019s a couple, starting and ending at vertex [latex]A[\/latex]: [latex]ADEACEFCBA[\/latex] and [latex]AECABCFEDA[\/latex]. The second is shown in arrows.\r\n\r\n<p>&nbsp;<\/p>\r\n<center><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\" \/><\/center><\/section>\r\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 exists.<\/p>\r\n<p>Why do we care if an Euler circuit exists? We care if an Euler circuit exists because it can help us solve problems, such as determining the most efficient route for a traveling salesperson or the optimal path for a network of roads. By finding an Euler circuit, we can ensure that every edge in the graph is visited exactly once, which can help us to avoid redundancy or inefficiency in our solutions. Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>Euler\u2019s path and circuit theorems<\/h3>\r\n<p>A graph will contain an <strong>Euler path<\/strong> if it contains at most two vertices of odd degree.<\/p>\r\n<p>A graph will contain an <strong>Euler circuit<\/strong> if all vertices have even degree<\/p>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">In the graph below, vertices [latex]A[\/latex] and [latex]C[\/latex] have degree [latex]4[\/latex], since there are [latex]4[\/latex] edges leading into each vertex. [latex]B[\/latex] is degree [latex]2[\/latex], [latex]D[\/latex] is degree [latex]3[\/latex], and [latex]E[\/latex] is degree [latex]1[\/latex]. This graph contains two vertices with odd degree ([latex]D[\/latex] and [latex]E[\/latex]) and three vertices with even degree ([latex]A[\/latex], [latex]B[\/latex], and [latex]C[\/latex]), so Euler\u2019s theorems tell us this graph has an Euler path, but not an Euler circuit.<center><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\" \/><\/center><\/section>\r\n<section class=\"textbox tryIt\">\r\n<p>[ohm2_question hide_question_numbers=1]12708[\/ohm2_question]<\/p>\r\n<\/section>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Determine whether a graph has an Euler path or circuit and use Fleury&#8217;s algorithm to find an Euler circuit<\/li>\n<li>Recognize whether a graph contains a Hamiltonian circuit or path and determine the optimal Hamiltonian circuit using various algorithms<\/li>\n<li>Identify a connected graph as a spanning tree and utilize Kruskal&#8217;s algorithm to create both a spanning tree and a minimum-cost spanning tree<\/li>\n<\/ul>\n<\/section>\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<h2>Euler Circuits<\/h2>\n<section class=\"textbox keyTakeaway\">\n<div>\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<\/section>\n<section class=\"textbox example\">In the graph shown below, there are several Euler paths. One such path is [latex]CABDCB[\/latex]. The path is shown in arrows to the right, with the order of edges numbered.<\/p>\n<div style=\"text-align: center;\"><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\" \/><\/div>\n<\/section>\n<section class=\"textbox keyTakeaway\">\n<div>\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<\/section>\n<section class=\"textbox example\">The graph below has several possible Euler circuits. Here\u2019s a couple, starting and ending at vertex [latex]A[\/latex]: [latex]ADEACEFCBA[\/latex] and [latex]AECABCFEDA[\/latex]. The second is shown in arrows.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><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\" \/><\/div>\n<\/section>\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 exists.<\/p>\n<p>Why do we care if an Euler circuit exists? We care if an Euler circuit exists because it can help us solve problems, such as determining the most efficient route for a traveling salesperson or the optimal path for a network of roads. By finding an Euler circuit, we can ensure that every edge in the graph is visited exactly once, which can help us to avoid redundancy or inefficiency in our solutions. Luckily, Euler solved the question of whether or not an Euler path or circuit will exist.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>Euler\u2019s path and circuit theorems<\/h3>\n<p>A graph will contain an <strong>Euler path<\/strong> if it contains at most two vertices of odd degree.<\/p>\n<p>A graph will contain an <strong>Euler circuit<\/strong> if all vertices have even degree<\/p>\n<\/div>\n<\/section>\n<section class=\"textbox example\">In the graph below, vertices [latex]A[\/latex] and [latex]C[\/latex] have degree [latex]4[\/latex], since there are [latex]4[\/latex] edges leading into each vertex. [latex]B[\/latex] is degree [latex]2[\/latex], [latex]D[\/latex] is degree [latex]3[\/latex], and [latex]E[\/latex] is degree [latex]1[\/latex]. This graph contains two vertices with odd degree ([latex]D[\/latex] and [latex]E[\/latex]) and three vertices with even degree ([latex]A[\/latex], [latex]B[\/latex], and [latex]C[\/latex]), so Euler\u2019s theorems tell us this graph has an Euler path, but not an Euler circuit.<\/p>\n<div style=\"text-align: center;\"><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\" \/><\/div>\n<\/section>\n<section class=\"textbox tryIt\">\n<iframe loading=\"lazy\" id=\"ohm12708\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=12708&theme=lumen&iframe_resize_id=ohm12708&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><br \/>\n<\/section>\n","protected":false},"author":15,"menu_order":9,"template":"","meta":{"_candela_citation":"[{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Math in Society\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"learn_it","content_attributions":[{"type":"original","description":"Revision and Adaptation","author":"","organization":"Lumen Learning","url":"","project":"","license":"cc-by","license_terms":""},{"type":"cc","description":"Math in Society","author":"David Lippman","organization":"","url":"http:\/\/www.opentextbookstore.com\/mathinsociety\/","project":"","license":"cc-by","license_terms":""}],"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1537"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":28,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1537\/revisions"}],"predecessor-version":[{"id":11737,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1537\/revisions\/11737"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1537\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=1537"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=1537"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=1537"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=1537"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}