{"id":8289,"date":"2023-09-29T14:30:57","date_gmt":"2023-09-29T14:30:57","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=8289"},"modified":"2025-08-29T20:18:34","modified_gmt":"2025-08-29T20:18:34","slug":"euler-and-hamiltonian-paths-and-circuits-apply-it-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-apply-it-1\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Apply It 1","rendered":"Euler and Hamiltonian Paths and Circuits: Apply 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<h2>Mission Route Optimization<\/h2>\r\n<p>An officer at Vandenberg AFB has a critical assignment that requires visiting three other California Air Force bases: Travis AFB (in Los Angeles), Beale AFB, and Edwards AFB. The officer must determine the most efficient route to visit each base once before returning to Vandenberg. The vertices in the graph below represent the four U.S. Air Force bases, Vandenberg, Edwards, Los Angeles, and Beale. The edges are labeled to with the driving distance between each pair of cities.<\/p>\r\n<center>\r\n[caption id=\"attachment_10594\" align=\"aligncenter\" width=\"500\"]<img class=\"wp-image-10594\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853.png\" alt=\"A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.\" width=\"500\" height=\"316\" \/> Figure 1. A graph of the four California air force bases (Vandenberg, Edwards, Los Angeles, and Beale) with the distances labeled[\/caption]\r\n<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Before our officer can embark on their mission, it's essential to understand the underlying structure of the routes between bases. This begins with a fundamental concept in graph theory: the Euler circuit.<\/p>\r\n<section class=\"textbox tryIt\">\r\n<p>[ohm2_question hide_question_numbers=1]13901[\/ohm2_question]<\/p>\r\n<\/section>\r\n<p>Having established the feasibility of an Euler circuit within the network of bases, we shift our focus to planning an actual mission route. A Hamiltonian cycle will ensure that each base is visited just once \u2013 a critical requirement for the officer\u2019s itinerary.<\/p>\r\n<p>Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown below.<\/p>\r\n<center><img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/80a22d9d01c87e5229a539d795d2d876f528883a\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" \/><\/center><center><img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/0333f78e1b5bd40ba76ce23cb7bd980def40470d\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" data-media-type=\"image\/png\" \/><\/center><center><img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/16f26022f8448a12cf484aec7646628447b5e1ac\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" data-media-type=\"image\/png\" \/><\/center>\r\n<div class=\"os-caption-container\" style=\"text-align: center;\"><span style=\"font-size: 10pt;\"><strong><span class=\"os-caption\">Figure 2. Three Possible Distances<\/span><\/strong><\/span><\/div>\r\n<p>&nbsp;<\/p>\r\n<p>The officer will now use the strategy of the Traveling Salesperson Problem to determine the most efficient sequence of visits.<\/p>\r\n<section class=\"textbox tryIt\">\r\n<p>[ohm2_question hide_question_numbers=1]13903[\/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<h2>Mission Route Optimization<\/h2>\n<p>An officer at Vandenberg AFB has a critical assignment that requires visiting three other California Air Force bases: Travis AFB (in Los Angeles), Beale AFB, and Edwards AFB. The officer must determine the most efficient route to visit each base once before returning to Vandenberg. The vertices in the graph below represent the four U.S. Air Force bases, Vandenberg, Edwards, Los Angeles, and Beale. The edges are labeled to with the driving distance between each pair of cities.<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_10594\" aria-describedby=\"caption-attachment-10594\" style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-10594\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853.png\" alt=\"A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.\" width=\"500\" height=\"316\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853.png 819w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853-300x190.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853-768x486.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853-65x41.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853-225x142.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/09\/10182139\/Screenshot-2023-11-10-131853-350x221.png 350w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><figcaption id=\"caption-attachment-10594\" class=\"wp-caption-text\">Figure 1. A graph of the four California air force bases (Vandenberg, Edwards, Los Angeles, and Beale) with the distances labeled<\/figcaption><\/figure>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Before our officer can embark on their mission, it&#8217;s essential to understand the underlying structure of the routes between bases. This begins with a fundamental concept in graph theory: the Euler circuit.<\/p>\n<section class=\"textbox tryIt\">\n<iframe loading=\"lazy\" id=\"ohm13901\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=13901&theme=lumen&iframe_resize_id=ohm13901&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><br \/>\n<\/section>\n<p>Having established the feasibility of an Euler circuit within the network of bases, we shift our focus to planning an actual mission route. A Hamiltonian cycle will ensure that each base is visited just once \u2013 a critical requirement for the officer\u2019s itinerary.<\/p>\n<p>Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown below.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/80a22d9d01c87e5229a539d795d2d876f528883a\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" \/><\/div>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/0333f78e1b5bd40ba76ce23cb7bd980def40470d\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" data-media-type=\"image\/png\" \/><\/div>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/16f26022f8448a12cf484aec7646628447b5e1ac\" alt=\"Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.\" width=\"500\" height=\"316\" data-media-type=\"image\/png\" \/><\/div>\n<div class=\"os-caption-container\" style=\"text-align: center;\"><span style=\"font-size: 10pt;\"><strong><span class=\"os-caption\">Figure 2. Three Possible Distances<\/span><\/strong><\/span><\/div>\n<p>&nbsp;<\/p>\n<p>The officer will now use the strategy of the Traveling Salesperson Problem to determine the most efficient sequence of visits.<\/p>\n<section class=\"textbox tryIt\">\n<iframe loading=\"lazy\" id=\"ohm13903\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=13903&theme=lumen&iframe_resize_id=ohm13903&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><br \/>\n<\/section>\n","protected":false},"author":15,"menu_order":14,"template":"","meta":{"_candela_citation":"[]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"apply_it","content_attributions":[],"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\/8289"}],"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":13,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8289\/revisions"}],"predecessor-version":[{"id":15933,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8289\/revisions\/15933"}],"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\/8289\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=8289"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=8289"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=8289"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=8289"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}