{"id":1539,"date":"2023-04-11T14:39:13","date_gmt":"2023-04-11T14:39:13","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=1539"},"modified":"2025-08-29T20:19:51","modified_gmt":"2025-08-29T20:19:51","slug":"euler-and-hamiltonian-paths-and-circuits-fresh-take","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/euler-and-hamiltonian-paths-and-circuits-fresh-take\/","title":{"raw":"Euler and Hamiltonian Paths and Circuits: Fresh Take","rendered":"Euler and Hamiltonian Paths and Circuits: Fresh Take"},"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>Euler Circuits<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p>Euler paths and circuits are concepts in graph theory that help us analyze and solve various problems related to networks, routes, and connections. They provide a way to systematically explore graphs and determine the most efficient paths or circuits to visit all edges or vertices.<\/p>\r\n<p><strong>Euler Path<\/strong>: An Euler path is a path in a graph that visits every edge exactly once. It starts at one vertex and ends at another vertex, but may not necessarily visit all vertices in the graph. In other words, an Euler path allows us to travel through all the edges of a graph without lifting the pen from the paper (or without retracing any edges).<\/p>\r\n<p><strong>Euler Circuit<\/strong>: An Euler circuit is a special type of Euler path that starts and ends at the same vertex. It visits every edge exactly once and also includes all the vertices in the graph. Similar to an Euler path, an Euler circuit allows us to traverse through all the edges of a graph without lifting the pen and also ensures that we return to the starting point.<\/p>\r\n<\/div>\r\n<section class=\"textbox watchIt\"><iframe src=\"\/\/plugin.3playmedia.com\/show?mf=11328615&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=sw79Z34v0dQ&amp;video_target=tpm-plugin-2wf1ky9g-sw79Z34v0dQ\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Eulerian+Circuits+and+Eulerian+Graphs+%7C+Graph+Theory%2C+Euler+Graphs+and+Euler+Circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cEulerian Circuits and Eulerian Graphs | Graph Theory, Euler Graphs and Euler Circuits\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<section class=\"textbox example\">Is there an Euler circuit on the housing development lawn inspector graph we created in the previous section? 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.<center><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\" \/><\/center><\/section>\r\n<section class=\"textbox example\">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.<center><img class=\"aligncenter 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=\"The same graph from above, but now, every dot is connected by two lines.\" width=\"250\" height=\"214\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nNotice that every vertex in this graph has even degree, so this graph does have an Euler circuit.<\/section>\r\n<p>The following video gives more examples of how to determine an Euler path, and an Euler Circuit for a graph.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/5M-m62qTR-s\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Euler+Paths+and+Euler+Circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Euler Paths and Euler Circuits\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Fleury\u2019s Algorithm<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p><strong>Fleury's Algorithm<\/strong> is a method used to find an Eulerian path or circuit in a graph. It helps us determine if a graph has an Euler path or circuit and, if it does, find the specific path or circuit.<\/p>\r\n<p>The algorithm works by iteratively selecting edges in the graph while ensuring that they do not disconnect the graph or create any bridges (edges that, if removed, would separate the graph into two or more disconnected components). The goal is to visit every edge in the graph exactly once, following a specific set of rules to maintain connectivity.<\/p>\r\n<p>Fleury's Algorithm starts at an arbitrary vertex and chooses edges that are not bridges until there are no more available edges. If at any point there are multiple choices, the algorithm selects an edge that does not create a bridge. By carefully selecting edges in this way, the algorithm constructs an Eulerian path or circuit that covers all edges of the graph.<\/p>\r\n<\/div>\r\n<p>Another method of identifying Euler circuits is to find any circuit in the graph, then find a second circuit starting at a vertex from the first circuit that uses only edges that were not in the first circuit, then find a third circuit starting at a vertex from either of the first two circuits that uses only edges that were not in the first two circuits, and then continue this process until all edges have been used. In the end, you will be able to link all the circuits together into one large Euler circuit. Let\u2019s find an Euler circuit in the map of the Camp Woebegone canoe race. In the figure below, we have labeled the edges of the multigraph so that the circuits can be named. In a multigraph it is necessary to name circuits using edges and vertices because there can be more than one edge between adjacent vertices.<\/p>\r\n<center>\r\n[caption id=\"attachment_8751\" align=\"aligncenter\" width=\"500\"]<img class=\"wp-image-8751\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. \" width=\"500\" height=\"182\" \/> Figure 1. Multigraph of Canoe Race with Vertices and Edges Labeled[\/caption]\r\n<\/center><center><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>We will begin with vertex [latex]1[\/latex] because it represents the starting line in this application. In general, you can start at any vertex you want. Find any circuit beginning and ending with vertex 1. Remember, a circuit is a trail, so it doesn\u2019t pass through any edge more than once. The figure below shows one possible circuit that we could use as the first circuit, [latex]1 \u2192 A \u2192 2 \u2192 B \u2192 3 \u2192 C \u2192 4 \u2192 G \u2192 5 \u2192 J \u2192 1[\/latex].<\/p>\r\n<center>\r\n[caption id=\"attachment_8752\" align=\"aligncenter\" width=\"500\"]<img class=\"wp-image-8752\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue.\" width=\"500\" height=\"182\" \/> Figure 2. First Circuit[\/caption]\r\n<\/center><center><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>From the edges that remain, we can form two more circuits that each start at one of the vertices along the first circuit. Starting at vertex [latex]3[\/latex] we can use [latex]3 \u2192 H \u2192 5 \u2192 I \u2192 1 \u2192 K \u2192 3[\/latex] and starting at vertex [latex]2[\/latex] we can use [latex]2 \u2192 D \u2192 6 \u2192 E \u2192 7 \u2192 F \u2192 2[\/latex], as shown below.<\/p>\r\n<center>\r\n[caption id=\"attachment_8753\" align=\"aligncenter\" width=\"500\"]<img class=\"wp-image-8753\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue. The edges, I, K, and H are in green. The edges, F, D, and E are in red.\" width=\"500\" height=\"182\" \/> Figure 3. Second and Third Circuits[\/caption]\r\n<\/center><center><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Now that each of the edges is included in one and only once circuit, we can create one large circuit by inserting the second and third circuits into the first. We will insert them at their starting vertices 2 and 3<\/p>\r\n<center>[latex]1\u2192A\u2192 \\fbox{2} \u2192B\u2192 \\fbox{3} \u2192C\u21924\u2192G\u21925\u2192J\u21921[\/latex]<\/center>\r\n<p>becomes<\/p>\r\n<center>[latex]1\u2192A\u2192\\fbox{2\u2192D\u21926\u2192E\u21927\u2192F\u21922}\u2192B\u2192\\fbox{3\u2192H\u21925\u2192I\u21921\u2192K\u21923}\u2192C\u21924\u2192G\u21925\u2192J\u21921[\/latex]<\/center>\r\n<p>&nbsp;<\/p>\r\n<p>Finally, we can name the circuit using vertices, [latex]1 \u2192 2 \u2192 6 \u2192 7 \u2192 2 \u2192 3 \u2192 5 \u2192 1 \u2192 3 \u2192 4 \u2192 5 \u2192 1,[\/latex] or edges, [latex]A \u2192 D \u2192 E \u2192 F \u2192 B \u2192 H \u2192 I \u2192 K \u2192 C \u2192 G \u2192 J[\/latex].<\/p>\r\n<p>Let's review the steps we used to find this Eulerian Circuit.<\/p>\r\n<section class=\"textbox proTip\">\r\n<p><strong>Steps to Find an Euler Circuit in an Eulerian Graph<\/strong><\/p>\r\n<ul>\r\n\t<li><strong>Step 1:<\/strong> Find a circuit beginning and ending at any point on the graph. If the circuit crosses every edges of the graph, the circuit you found is an Euler circuit. If not, move on to step 2.<\/li>\r\n\t<li><strong>Step 2:<\/strong> Beginning at a vertex on a circuit you already found, find a circuit that only includes edges that have not previously been crossed. If every edge has been crossed by one of the circuits you have found, move on to Step 3. Otherwise, repeat Step 2.<\/li>\r\n\t<li><strong>Step 3:<\/strong> Now that you have found circuits that cover all of the edges in the graph, combine them into an Euler circuit. You can do this by inserting any of the circuits into another circuit with a common vertex repeatedly until there is one long circuit.<\/li>\r\n<\/ul>\r\n<\/section>\r\n<section class=\"textbox example\">Does the graph below have an Euler Circuit? If so, find one.<center><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=\"A graph with 7 vertices. Vertices A and G have a degree of 2 and the other vertices have a degree of 4.\" width=\"415\" height=\"241\" \/><\/a><\/center>[reveal-answer q=\"997648\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997648\"] Yes, all vertices have even degree so this graph has an Euler Circuit. There are several possibilities. One is: [latex]ABEGFCDFEDBCA[\/latex] [\/hidden-answer]<\/section>\r\n<section class=\"textbox watchIt\"><iframe src=\"\/\/plugin.3playmedia.com\/show?mf=11328616&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=F4BM6fnLl04&amp;video_target=tpm-plugin-y856raiw-F4BM6fnLl04\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Euler+Part+3+Fleurys+Algorithm+for+Finding+an+Euler+Circuit+in+Graph+with+Vertices+of+Even+Degree.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cEuler Part 3: Fleury's Algorithm for Finding an Euler Circuit in Graph with Vertices of Even Degree\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h3>Eulerization<\/h3>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p><strong>Eulerization<\/strong> is the process of modifying a graph by adding edges to make it possible to find an Eulerian circuit or path. It is used when the original graph does not have an Eulerian circuit or path, but we want to transform it in such a way that it becomes possible to traverse all edges exactly once.<\/p>\r\n<p>To Eulerize a graph, additional edges are added strategically to connect pairs of vertices with odd degrees. By adding these extra edges, the degrees of all vertices in the modified graph become even, allowing for the existence of an Eulerian circuit or path.<\/p>\r\n<\/div>\r\n<section class=\"textbox example\">Eulerize the graph shown, then find an Euler circuit on the eulerized graph.<center><img class=\"aligncenter size-full wp-image-2742\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163450\/Screenshot-2023-05-15-123424.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=\"177\" height=\"176\" \/><\/center>[reveal-answer q=\"197648\"]Show Solution[\/reveal-answer] [hidden-answer a=\"197648\"] This graph can be eulerized by duplicating the edge [latex]BC[\/latex], as shown. One possible Euler circuit on the eulerized graph is [latex]ACDBCBA[\/latex].<center><img class=\"size-full wp-image-2743 aligncenter\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163524\/Screenshot-2023-05-15-123428.png\" alt=\"The same graph as above is shown with a red line connecting vertices B to C\" width=\"240\" height=\"187\" \/><\/center>[\/hidden-answer]<\/section>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/Z7MRbPrxjcQ\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Eulerization.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Eulerization\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Hamiltonian Circuits and Paths<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p><strong>Hamiltonian Circuit<\/strong>: A Hamiltonian circuit is a path in a graph that visits every vertex exactly once, starting and ending at the same vertex. In other words, it is a closed loop that passes through every vertex of the graph without revisiting any vertex.<\/p>\r\n<p><strong>Hamiltonian Path<\/strong>: A Hamiltonian path is a path in a graph that visits every vertex exactly once, but may not necessarily start and end at the same vertex. Unlike a Hamiltonian circuit, it does not form a closed loop.<\/p>\r\n<p>The search for Hamiltonian circuits and paths is often considered more difficult than the search for Eulerian circuits and paths, as there is no known general method to quickly find them in arbitrary graphs.<\/p>\r\n<\/div>\r\n<p>Watch the following video for more information on Hamiltonian circuits and paths.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/AamHZhAmR7o?si=PxIzZPAi3LeIVxhH\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Hamiltonian+Circuits+and+Paths.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Hamiltonian Circuits and Paths\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<p>Watch the following video to see examples of finding a Hamiltonian circuit.<\/p>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/SjtVuw4-1Qo?si=1Jv_bg2lVr3TsrsK\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Hamiltonian+circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cHamiltonian circuits\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Brute Force Algorithm<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p>The <strong>brute force algorithm<\/strong> is a straightforward and exhaustive approach to problem-solving that involves systematically checking all possible solutions to find the optimal or desired solution. It is called \"brute force\" because it explores every possible option without using any shortcuts or optimization techniques. This method guarantees finding the correct solution, but it can be computationally intensive and time-consuming, especially for problems with large input sizes. The steps of using the brute force algorithm are:<\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>List all possible Hamiltonian circuits<\/li>\r\n\t<li>Find the length of each circuit by adding the edge weights<\/li>\r\n\t<li>Select the circuit with minimal total weight.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/SIGukyznLLw\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+The+Brute+Force+Algorithm.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: The Brute Force Algorithm\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Nearest Neighbor Algorithm<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p>The <strong>nearest neighbor algorith<\/strong>m is a simple and intuitive approach used to solve certain optimization problems, especially those involving finding the shortest path or tour in a graph. It works by iteratively selecting the nearest unvisited neighbor from the current location until all nodes are visited. The algorithm starts at an arbitrary node and keeps track of the current location. It then selects the closest unvisited neighboring node and moves to that node. This process is repeated until all nodes have been visited, forming a complete tour or path. The steps of using the nearest neighbor algorithm are:<\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Select a starting point.<\/li>\r\n\t<li>Move to the nearest unvisited vertex (the edge with smallest weight).<\/li>\r\n\t<li>Repeat until the circuit is complete.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/zPgsNsOfxQ8\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Nearest+Neighbor+Algorithm+(NNA).txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Nearest Neighbor Algorithm (NNA)\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Sorted Edges Algorithm<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p>The <strong>sorted edges algorithm<\/strong> is a method used to determine the order in which edges are selected and processed in a graph. It involves sorting the edges of the graph based on a certain criterion, such as their weights, and then iteratively considering these edges in the sorted order. The algorithm starts by sorting all the edges of the graph based on a specific attribute, such as their weights or costs. Once the edges are sorted, they can be processed one by one in the specified order. The steps of using the sorted edges algorithm are:<\/p>\r\n<ol style=\"list-style-type: decimal;\">\r\n\t<li>Select the cheapest unused edge in the graph.<\/li>\r\n\t<li>Repeat step 1, adding the cheapest unused edge to the circuit, unless:\r\n\r\n<ol style=\"list-style-type: lower-alpha;\">\r\n\t<li>adding the edge would create a circuit that doesn\u2019t contain all vertices, or<\/li>\r\n\t<li>adding the edge would give a vertex degree [latex]3[\/latex].<\/li>\r\n<\/ol>\r\n<\/li>\r\n\t<li>Repeat until a circuit containing all vertices is formed.<\/li>\r\n<\/ol>\r\n<\/div>\r\n<section class=\"textbox watchIt\"><iframe title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/WUMxRp3xei0\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Sorted+Edges+Algorithm+(Cheapest+Link+Algorithm).txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Sorted Edges Algorithm (Cheapest Link Algorithm)\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<h2>Spanning Trees<\/h2>\r\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong>\r\n<p>A <strong>spanning tree<\/strong> is a subgraph of a connected graph that includes all the vertices of the original graph and forms a tree structure without any cycles.<\/p>\r\n<p>In other words, it is a tree-like subset of the graph that spans across all the vertices while maintaining connectivity.<\/p>\r\n<p>A spanning tree can be thought of as a way to connect all the vertices of a graph using the fewest possible number of edges. It eliminates any redundant or unnecessary edges that could form cycles and ensures that there is a unique path between any pair of vertices.<\/p>\r\n<p><strong>Kruskal's Algorithm<\/strong> is a popular method used to find a minimum spanning tree in a weighted graph. It efficiently selects edges from the graph based on their weights, gradually forming a minimum spanning tree that connects all the vertices. The steps of using the Kruskal's Algorithm are:<\/p>\r\n<ol>\r\n\t<li>Select the cheapest unused edge in the graph.<\/li>\r\n\t<li>Repeat step 1, adding the cheapest unused edge, unless:<\/li>\r\n\t<li>adding the edge would create a circuit<\/li>\r\n<\/ol>\r\n<p>Repeat until a spanning tree is formed<\/p>\r\n<\/div>\r\n<section class=\"textbox watchIt\"><iframe src=\"\/\/plugin.3playmedia.com\/show?mf=11328617&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=b233VKD6udo&amp;video_target=tpm-plugin-rn166vzi-b233VKD6udo\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe>\r\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Recognizing+and+Finding+Spanning+Trees+in+Graph+Theory.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cRecognizing and Finding Spanning Trees in Graph Theory\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<section class=\"textbox example\">The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay?\r\n\r\n<div style=\"width: auto;\">\r\n<table style=\"width: 586px; height: 333px;\">\r\n<tbody>\r\n<tr>\r\n<td>&nbsp;<\/td>\r\n<td>\u00a0Ashland<\/td>\r\n<td>Astoria<\/td>\r\n<td>\u00a0Bend<\/td>\r\n<td>\u00a0Corvallis<\/td>\r\n<td>\u00a0Crater Lake<\/td>\r\n<td>\u00a0Eugene<\/td>\r\n<td>\u00a0Newport<\/td>\r\n<td>\u00a0Portland<\/td>\r\n<td>\u00a0Salem<\/td>\r\n<td>\u00a0Seaside<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Ashland<\/td>\r\n<td>-<\/td>\r\n<td>[latex]374[\/latex]<\/td>\r\n<td>[latex]200[\/latex]<\/td>\r\n<td>[latex]223[\/latex]<\/td>\r\n<td>[latex]108[\/latex]<\/td>\r\n<td>[latex]178[\/latex]<\/td>\r\n<td>[latex]252[\/latex]<\/td>\r\n<td>[latex]285[\/latex]<\/td>\r\n<td>[latex]240[\/latex]<\/td>\r\n<td>[latex]356[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Astoria<\/td>\r\n<td>[latex]374[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]255[\/latex]<\/td>\r\n<td>[latex]166[\/latex]<\/td>\r\n<td>[latex]433[\/latex]<\/td>\r\n<td>[latex]199[\/latex]<\/td>\r\n<td>[latex]135[\/latex]<\/td>\r\n<td>[latex]95[\/latex]<\/td>\r\n<td>[latex]136[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bend<\/td>\r\n<td>[latex]200[\/latex]<\/td>\r\n<td>[latex]255[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]277[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]180[\/latex]<\/td>\r\n<td>[latex]160[\/latex]<\/td>\r\n<td>[latex]131[\/latex]<\/td>\r\n<td>[latex]247[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Corvallis<\/td>\r\n<td>[latex]223[\/latex]<\/td>\r\n<td>[latex]166[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]430[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]52[\/latex]<\/td>\r\n<td>[latex]84[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]155[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Crater Lake<\/td>\r\n<td>[latex]108[\/latex]<\/td>\r\n<td>[latex]433[\/latex]<\/td>\r\n<td>[latex]277[\/latex]<\/td>\r\n<td>[latex]430[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]453[\/latex]<\/td>\r\n<td>[latex]478[\/latex]<\/td>\r\n<td>[latex]344[\/latex]<\/td>\r\n<td>[latex]389[\/latex]<\/td>\r\n<td>[latex]423[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Eugene<\/td>\r\n<td>[latex]178[\/latex]<\/td>\r\n<td>[latex]199[\/latex]<\/td>\r\n<td>[latex]128[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]453[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]91[\/latex]<\/td>\r\n<td>[latex]110[\/latex]<\/td>\r\n<td>[latex]64[\/latex]<\/td>\r\n<td>[latex]181[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Newport<\/td>\r\n<td>[latex]252[\/latex]<\/td>\r\n<td>[latex]135[\/latex]<\/td>\r\n<td>[latex]180[\/latex]<\/td>\r\n<td>[latex]52[\/latex]<\/td>\r\n<td>[latex]478[\/latex]<\/td>\r\n<td>[latex]91[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]114[\/latex]<\/td>\r\n<td>[latex]83[\/latex]<\/td>\r\n<td>[latex]117[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Portland<\/td>\r\n<td>[latex]285[\/latex]<\/td>\r\n<td>[latex]95[\/latex]<\/td>\r\n<td>[latex]160[\/latex]<\/td>\r\n<td>[latex]84[\/latex]<\/td>\r\n<td>[latex]344[\/latex]<\/td>\r\n<td>[latex]110[\/latex]<\/td>\r\n<td>[latex]114[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>[latex]78[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Salem<\/td>\r\n<td>[latex]240[\/latex]<\/td>\r\n<td>[latex]136[\/latex]<\/td>\r\n<td>[latex]131[\/latex]<\/td>\r\n<td>[latex]40[\/latex]<\/td>\r\n<td>[latex]389[\/latex]<\/td>\r\n<td>[latex]64[\/latex]<\/td>\r\n<td>[latex]83[\/latex]<\/td>\r\n<td>[latex]47[\/latex]<\/td>\r\n<td>-<\/td>\r\n<td>[latex]118[\/latex]<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Seaside<\/td>\r\n<td>[latex]356[\/latex]<\/td>\r\n<td>[latex]17[\/latex]<\/td>\r\n<td>[latex]247[\/latex]<\/td>\r\n<td>[latex]155[\/latex]<\/td>\r\n<td>[latex]423[\/latex]<\/td>\r\n<td>[latex]181[\/latex]<\/td>\r\n<td>[latex]117[\/latex]<\/td>\r\n<td>[latex]78[\/latex]<\/td>\r\n<td>[latex]118[\/latex]<\/td>\r\n<td>-<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n\r\n[reveal-answer q=\"997641\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997641\"] Using Kruskal\u2019s algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.<center>[latex] \\begin{array}{r@{\\hfill}l} \\text{Seaside to Astoria} &amp;&amp; 17 \\text{ miles} \\\\ \\text{Corvallis to Salem} &amp;&amp; 40 \\text{ miles} \\\\ \\text{Portland to Salem} &amp;&amp; 47 \\text{ miles} \\\\ \\text{Corvallis to Eugene} &amp;&amp; 47 \\text{ miles} \\\\ \\text{Corvallis to Newport} &amp;&amp; 52 \\text{ miles} \\\\ \\text{Salem to Eugene} &amp;&amp; \\text{reject \u2013 closes circuit} \\\\ \\end{array}[\/latex]<\/center>\r\n<p>&nbsp;<\/p>\r\n<em>The graph up to this point is shown below.<\/em><center><img class=\"alignnone wp-image-12919\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Salem and Corvallis, Newport and Corvallis, and Salem and Portland.\" width=\"500\" height=\"331\" \/><\/center>\r\n<p>&nbsp;<\/p>\r\n\r\nContinuing,<center>[latex] \\begin{array}{r@{\\hfill}l} \\text{Newport to Salem} &amp;&amp; \\text{reject} \\\\ \\text{Corvallis to Portland} &amp;&amp; \\text{reject} \\\\ \\text{Eugene to Newport} &amp;&amp; \\text{reject} \\\\ \\text{Portland to Astoria} &amp;&amp; \\text{reject} \\\\ \\text{Ashland to Crater Lk} &amp;&amp; 108 \\text{ miles} \\\\ \\text{Eugene to Portland} &amp;&amp; \\text{reject} \\\\ \\text{Newport to Portland} &amp;&amp; \\text{reject} \\\\ \\text{Newport to Seaside} &amp;&amp; \\text{reject} \\\\ \\text{Salem to Seaside} &amp;&amp; \\text{reject} \\\\ \\text{Bend to Eugene} &amp;&amp; 128 \\text{ miles} \\\\ \\text{Bend to Salem} &amp;&amp; \\text{reject} \\\\ \\text{Astoria to Newport} &amp;&amp; \\text{reject} \\\\ \\text{Salem to Astoria} &amp;&amp; \\text{reject} \\\\ \\text{Corvallis to Seaside} &amp;&amp; \\text{reject} \\\\ \\text{Portland to Bend} &amp;&amp; \\text{reject} \\\\ \\text{Astoria to Corvallis} &amp;&amp; \\text{reject} \\\\ \\text{Eugene to Ashland} &amp;&amp; 178 \\text{ miles} \\\\ \\end{array}[\/latex]\r\n\r\n<p>&nbsp;<\/p>\r\n<\/center>This connects the graph. The total length of cable to lay would be [latex]695[\/latex] miles.\r\n\r\n<p>&nbsp;<\/p>\r\n<center><img class=\"alignnone wp-image-12920\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Portland and Salem, Salem and Corvallis, Eugene and Corvallis, Newport and Corvallis, Eugene and Bend, Eugene and Ashland, and Ashland and Crater Lake.\" width=\"500\" height=\"331\" \/><\/center>[\/hidden-answer]<\/section>\r\n<section class=\"textbox example\">Find a minimum spanning tree for the weighted graph. Give its total weight.<center><img class=\"aligncenter size-medium wp-image-8835\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-300x254.png\" alt=\"A weighted graph with five vertices. The vertices are as follows: U, V, W, X, and Z. The edges are labeled as follows. U V, 89. V Y, 24. Y X, 68. X W, 45. W U, 37. U X, 49. W V, 68.\" width=\"300\" height=\"254\" \/><\/center>[reveal-answer q=\"997612\"]Show Solution[\/reveal-answer] [hidden-answer a=\"997612\"] There are two possible minimum spanning trees, each with a total weight of [latex]174[\/latex]:<center><img class=\"aligncenter size-medium wp-image-8836\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-300x107.png\" alt=\"Two weighted graphs. The vertices in each graph are as follows: U, V, W, X, and Y. The edges in the first graph are as follows. U W, 37. W X, 45. W V, 68. V Y, 24. The edges in the second graph are as follows. U W, 37. W X, 45. X Y, 68. Y V, 24.\" width=\"300\" height=\"107\" \/><\/center>[\/hidden-answer]<\/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>Euler Circuits<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>Euler paths and circuits are concepts in graph theory that help us analyze and solve various problems related to networks, routes, and connections. They provide a way to systematically explore graphs and determine the most efficient paths or circuits to visit all edges or vertices.<\/p>\n<p><strong>Euler Path<\/strong>: An Euler path is a path in a graph that visits every edge exactly once. It starts at one vertex and ends at another vertex, but may not necessarily visit all vertices in the graph. In other words, an Euler path allows us to travel through all the edges of a graph without lifting the pen from the paper (or without retracing any edges).<\/p>\n<p><strong>Euler Circuit<\/strong>: An Euler circuit is a special type of Euler path that starts and ends at the same vertex. It visits every edge exactly once and also includes all the vertices in the graph. Similar to an Euler path, an Euler circuit allows us to traverse through all the edges of a graph without lifting the pen and also ensures that we return to the starting point.<\/p>\n<\/div>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" src=\"\/\/plugin.3playmedia.com\/show?mf=11328615&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=sw79Z34v0dQ&amp;video_target=tpm-plugin-2wf1ky9g-sw79Z34v0dQ\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Eulerian+Circuits+and+Eulerian+Graphs+%7C+Graph+Theory%2C+Euler+Graphs+and+Euler+Circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cEulerian Circuits and Eulerian Graphs | Graph Theory, Euler Graphs and Euler Circuits\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<section class=\"textbox example\">Is there an Euler circuit on the housing development lawn inspector graph we created in the previous section? 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<div style=\"text-align: center;\"><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\" \/><\/div>\n<\/section>\n<section class=\"textbox example\">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<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter 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=\"The same graph from above, but now, every dot is connected by two lines.\" width=\"250\" height=\"214\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Notice that every vertex in this graph has even degree, so this graph does have an Euler circuit.<\/section>\n<p>The following video gives more examples of how to determine an Euler path, and an Euler Circuit for a graph.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/5M-m62qTR-s\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Euler+Paths+and+Euler+Circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Euler Paths and Euler Circuits\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Fleury\u2019s Algorithm<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p><strong>Fleury&#8217;s Algorithm<\/strong> is a method used to find an Eulerian path or circuit in a graph. It helps us determine if a graph has an Euler path or circuit and, if it does, find the specific path or circuit.<\/p>\n<p>The algorithm works by iteratively selecting edges in the graph while ensuring that they do not disconnect the graph or create any bridges (edges that, if removed, would separate the graph into two or more disconnected components). The goal is to visit every edge in the graph exactly once, following a specific set of rules to maintain connectivity.<\/p>\n<p>Fleury&#8217;s Algorithm starts at an arbitrary vertex and chooses edges that are not bridges until there are no more available edges. If at any point there are multiple choices, the algorithm selects an edge that does not create a bridge. By carefully selecting edges in this way, the algorithm constructs an Eulerian path or circuit that covers all edges of the graph.<\/p>\n<\/div>\n<p>Another method of identifying Euler circuits is to find any circuit in the graph, then find a second circuit starting at a vertex from the first circuit that uses only edges that were not in the first circuit, then find a third circuit starting at a vertex from either of the first two circuits that uses only edges that were not in the first two circuits, and then continue this process until all edges have been used. In the end, you will be able to link all the circuits together into one large Euler circuit. Let\u2019s find an Euler circuit in the map of the Camp Woebegone canoe race. In the figure below, we have labeled the edges of the multigraph so that the circuits can be named. In a multigraph it is necessary to name circuits using edges and vertices because there can be more than one edge between adjacent vertices.<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_8751\" aria-describedby=\"caption-attachment-8751\" style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-8751\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3.\" width=\"500\" height=\"182\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-300x109.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-768x280.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-65x24.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-225x82.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc-350x128.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153707\/94f9155d00c1ca6a00907123f08151d396a863dc.png 787w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><figcaption id=\"caption-attachment-8751\" class=\"wp-caption-text\">Figure 1. Multigraph of Canoe Race with Vertices and Edges Labeled<\/figcaption><\/figure>\n<\/div>\n<div style=\"text-align: center;\"><\/div>\n<p>&nbsp;<\/p>\n<p>We will begin with vertex [latex]1[\/latex] because it represents the starting line in this application. In general, you can start at any vertex you want. Find any circuit beginning and ending with vertex 1. Remember, a circuit is a trail, so it doesn\u2019t pass through any edge more than once. The figure below shows one possible circuit that we could use as the first circuit, [latex]1 \u2192 A \u2192 2 \u2192 B \u2192 3 \u2192 C \u2192 4 \u2192 G \u2192 5 \u2192 J \u2192 1[\/latex].<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_8752\" aria-describedby=\"caption-attachment-8752\" style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-8752\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue.\" width=\"500\" height=\"182\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-300x109.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-768x280.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-65x24.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-225x82.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555-350x128.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153823\/1be43e0b240b87ad4677aaff7c0d662e1b830555.png 787w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><figcaption id=\"caption-attachment-8752\" class=\"wp-caption-text\">Figure 2. First Circuit<\/figcaption><\/figure>\n<\/div>\n<div style=\"text-align: center;\"><\/div>\n<p>&nbsp;<\/p>\n<p>From the edges that remain, we can form two more circuits that each start at one of the vertices along the first circuit. Starting at vertex [latex]3[\/latex] we can use [latex]3 \u2192 H \u2192 5 \u2192 I \u2192 1 \u2192 K \u2192 3[\/latex] and starting at vertex [latex]2[\/latex] we can use [latex]2 \u2192 D \u2192 6 \u2192 E \u2192 7 \u2192 F \u2192 2[\/latex], as shown below.<\/p>\n<div style=\"text-align: center;\">\n<figure id=\"attachment_8753\" aria-describedby=\"caption-attachment-8753\" style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-8753\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-300x109.png\" alt=\"A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue. The edges, I, K, and H are in green. The edges, F, D, and E are in red.\" width=\"500\" height=\"182\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-300x109.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-768x279.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-65x24.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-225x82.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9-350x127.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05153938\/4fc3e455a395b50ca21da580298a34e30b3b80b9.png 789w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><figcaption id=\"caption-attachment-8753\" class=\"wp-caption-text\">Figure 3. Second and Third Circuits<\/figcaption><\/figure>\n<\/div>\n<div style=\"text-align: center;\"><\/div>\n<p>&nbsp;<\/p>\n<p>Now that each of the edges is included in one and only once circuit, we can create one large circuit by inserting the second and third circuits into the first. We will insert them at their starting vertices 2 and 3<\/p>\n<div style=\"text-align: center;\">[latex]1\u2192A\u2192 \\fbox{2} \u2192B\u2192 \\fbox{3} \u2192C\u21924\u2192G\u21925\u2192J\u21921[\/latex]<\/div>\n<p>becomes<\/p>\n<div style=\"text-align: center;\">[latex]1\u2192A\u2192\\fbox{2\u2192D\u21926\u2192E\u21927\u2192F\u21922}\u2192B\u2192\\fbox{3\u2192H\u21925\u2192I\u21921\u2192K\u21923}\u2192C\u21924\u2192G\u21925\u2192J\u21921[\/latex]<\/div>\n<p>&nbsp;<\/p>\n<p>Finally, we can name the circuit using vertices, [latex]1 \u2192 2 \u2192 6 \u2192 7 \u2192 2 \u2192 3 \u2192 5 \u2192 1 \u2192 3 \u2192 4 \u2192 5 \u2192 1,[\/latex] or edges, [latex]A \u2192 D \u2192 E \u2192 F \u2192 B \u2192 H \u2192 I \u2192 K \u2192 C \u2192 G \u2192 J[\/latex].<\/p>\n<p>Let&#8217;s review the steps we used to find this Eulerian Circuit.<\/p>\n<section class=\"textbox proTip\">\n<p><strong>Steps to Find an Euler Circuit in an Eulerian Graph<\/strong><\/p>\n<ul>\n<li><strong>Step 1:<\/strong> Find a circuit beginning and ending at any point on the graph. If the circuit crosses every edges of the graph, the circuit you found is an Euler circuit. If not, move on to step 2.<\/li>\n<li><strong>Step 2:<\/strong> Beginning at a vertex on a circuit you already found, find a circuit that only includes edges that have not previously been crossed. If every edge has been crossed by one of the circuits you have found, move on to Step 3. Otherwise, repeat Step 2.<\/li>\n<li><strong>Step 3:<\/strong> Now that you have found circuits that cover all of the edges in the graph, combine them into an Euler circuit. You can do this by inserting any of the circuits into another circuit with a common vertex repeatedly until there is one long circuit.<\/li>\n<\/ul>\n<\/section>\n<section class=\"textbox example\">Does the graph below have an Euler Circuit? If so, find one.<\/p>\n<div style=\"text-align: center;\"><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=\"A graph with 7 vertices. Vertices A and G have a degree of 2 and the other vertices have a degree of 4.\" width=\"415\" height=\"241\" \/><\/a><\/div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997648\">Show Solution<\/button> <\/p>\n<div id=\"q997648\" class=\"hidden-answer\" style=\"display: none\"> Yes, all vertices have even degree so this graph has an Euler Circuit. There are several possibilities. One is: [latex]ABEGFCDFEDBCA[\/latex] <\/div>\n<\/div>\n<\/section>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" src=\"\/\/plugin.3playmedia.com\/show?mf=11328616&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=F4BM6fnLl04&amp;video_target=tpm-plugin-y856raiw-F4BM6fnLl04\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Euler+Part+3+Fleurys+Algorithm+for+Finding+an+Euler+Circuit+in+Graph+with+Vertices+of+Even+Degree.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cEuler Part 3: Fleury&#8217;s Algorithm for Finding an Euler Circuit in Graph with Vertices of Even Degree\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h3>Eulerization<\/h3>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p><strong>Eulerization<\/strong> is the process of modifying a graph by adding edges to make it possible to find an Eulerian circuit or path. It is used when the original graph does not have an Eulerian circuit or path, but we want to transform it in such a way that it becomes possible to traverse all edges exactly once.<\/p>\n<p>To Eulerize a graph, additional edges are added strategically to connect pairs of vertices with odd degrees. By adding these extra edges, the degrees of all vertices in the modified graph become even, allowing for the existence of an Eulerian circuit or path.<\/p>\n<\/div>\n<section class=\"textbox example\">Eulerize the graph shown, then find an Euler circuit on the eulerized graph.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-2742\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163450\/Screenshot-2023-05-15-123424.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=\"177\" height=\"176\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163450\/Screenshot-2023-05-15-123424.png 177w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163450\/Screenshot-2023-05-15-123424-150x150.png 150w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163450\/Screenshot-2023-05-15-123424-65x65.png 65w\" sizes=\"(max-width: 177px) 100vw, 177px\" \/><\/div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q197648\">Show Solution<\/button> <\/p>\n<div id=\"q197648\" class=\"hidden-answer\" style=\"display: none\"> This graph can be eulerized by duplicating the edge [latex]BC[\/latex], as shown. One possible Euler circuit on the eulerized graph is [latex]ACDBCBA[\/latex].<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-2743 aligncenter\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163524\/Screenshot-2023-05-15-123428.png\" alt=\"The same graph as above is shown with a red line connecting vertices B to C\" width=\"240\" height=\"187\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163524\/Screenshot-2023-05-15-123428.png 240w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163524\/Screenshot-2023-05-15-123428-65x51.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/15163524\/Screenshot-2023-05-15-123428-225x175.png 225w\" sizes=\"(max-width: 240px) 100vw, 240px\" \/><\/div>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/Z7MRbPrxjcQ\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Eulerization.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Eulerization\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Hamiltonian Circuits and Paths<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p><strong>Hamiltonian Circuit<\/strong>: A Hamiltonian circuit is a path in a graph that visits every vertex exactly once, starting and ending at the same vertex. In other words, it is a closed loop that passes through every vertex of the graph without revisiting any vertex.<\/p>\n<p><strong>Hamiltonian Path<\/strong>: A Hamiltonian path is a path in a graph that visits every vertex exactly once, but may not necessarily start and end at the same vertex. Unlike a Hamiltonian circuit, it does not form a closed loop.<\/p>\n<p>The search for Hamiltonian circuits and paths is often considered more difficult than the search for Eulerian circuits and paths, as there is no known general method to quickly find them in arbitrary graphs.<\/p>\n<\/div>\n<p>Watch the following video for more information on Hamiltonian circuits and paths.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/AamHZhAmR7o?si=PxIzZPAi3LeIVxhH\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Hamiltonian+Circuits+and+Paths.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Hamiltonian Circuits and Paths\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<p>Watch the following video to see examples of finding a Hamiltonian circuit.<\/p>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/SjtVuw4-1Qo?si=1Jv_bg2lVr3TsrsK\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Hamiltonian+circuits.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cHamiltonian circuits\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Brute Force Algorithm<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>The <strong>brute force algorithm<\/strong> is a straightforward and exhaustive approach to problem-solving that involves systematically checking all possible solutions to find the optimal or desired solution. It is called &#8220;brute force&#8221; because it explores every possible option without using any shortcuts or optimization techniques. This method guarantees finding the correct solution, but it can be computationally intensive and time-consuming, especially for problems with large input sizes. The steps of using the brute force algorithm are:<\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>List all possible Hamiltonian circuits<\/li>\n<li>Find the length of each circuit by adding the edge weights<\/li>\n<li>Select the circuit with minimal total weight.<\/li>\n<\/ol>\n<\/div>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/SIGukyznLLw\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+The+Brute+Force+Algorithm.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: The Brute Force Algorithm\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Nearest Neighbor Algorithm<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>The <strong>nearest neighbor algorith<\/strong>m is a simple and intuitive approach used to solve certain optimization problems, especially those involving finding the shortest path or tour in a graph. It works by iteratively selecting the nearest unvisited neighbor from the current location until all nodes are visited. The algorithm starts at an arbitrary node and keeps track of the current location. It then selects the closest unvisited neighboring node and moves to that node. This process is repeated until all nodes have been visited, forming a complete tour or path. The steps of using the nearest neighbor algorithm are:<\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>Select a starting point.<\/li>\n<li>Move to the nearest unvisited vertex (the edge with smallest weight).<\/li>\n<li>Repeat until the circuit is complete.<\/li>\n<\/ol>\n<\/div>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/zPgsNsOfxQ8\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Nearest+Neighbor+Algorithm+(NNA).txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Nearest Neighbor Algorithm (NNA)\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Sorted Edges Algorithm<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>The <strong>sorted edges algorithm<\/strong> is a method used to determine the order in which edges are selected and processed in a graph. It involves sorting the edges of the graph based on a certain criterion, such as their weights, and then iteratively considering these edges in the sorted order. The algorithm starts by sorting all the edges of the graph based on a specific attribute, such as their weights or costs. Once the edges are sorted, they can be processed one by one in the specified order. The steps of using the sorted edges algorithm are:<\/p>\n<ol style=\"list-style-type: decimal;\">\n<li>Select the cheapest unused edge in the graph.<\/li>\n<li>Repeat step 1, adding the cheapest unused edge to the circuit, unless:\n<ol style=\"list-style-type: lower-alpha;\">\n<li>adding the edge would create a circuit that doesn\u2019t contain all vertices, or<\/li>\n<li>adding the edge would give a vertex degree [latex]3[\/latex].<\/li>\n<\/ol>\n<\/li>\n<li>Repeat until a circuit containing all vertices is formed.<\/li>\n<\/ol>\n<\/div>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" title=\"YouTube video player\" src=\"https:\/\/www.youtube.com\/embed\/WUMxRp3xei0\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory_+Sorted+Edges+Algorithm+(Cheapest+Link+Algorithm).txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Sorted Edges Algorithm (Cheapest Link Algorithm)\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<h2>Spanning Trees<\/h2>\n<div class=\"textbox shaded\"><strong>The Main Idea\u00a0<\/strong><\/p>\n<p>A <strong>spanning tree<\/strong> is a subgraph of a connected graph that includes all the vertices of the original graph and forms a tree structure without any cycles.<\/p>\n<p>In other words, it is a tree-like subset of the graph that spans across all the vertices while maintaining connectivity.<\/p>\n<p>A spanning tree can be thought of as a way to connect all the vertices of a graph using the fewest possible number of edges. It eliminates any redundant or unnecessary edges that could form cycles and ensures that there is a unique path between any pair of vertices.<\/p>\n<p><strong>Kruskal&#8217;s Algorithm<\/strong> is a popular method used to find a minimum spanning tree in a weighted graph. It efficiently selects edges from the graph based on their weights, gradually forming a minimum spanning tree that connects all the vertices. The steps of using the Kruskal&#8217;s Algorithm are:<\/p>\n<ol>\n<li>Select the cheapest unused edge in the graph.<\/li>\n<li>Repeat step 1, adding the cheapest unused edge, unless:<\/li>\n<li>adding the edge would create a circuit<\/li>\n<\/ol>\n<p>Repeat until a spanning tree is formed<\/p>\n<\/div>\n<section class=\"textbox watchIt\"><iframe loading=\"lazy\" src=\"\/\/plugin.3playmedia.com\/show?mf=11328617&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=b233VKD6udo&amp;video_target=tpm-plugin-rn166vzi-b233VKD6udo\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\n<p>You can view the\u00a0<a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Recognizing+and+Finding+Spanning+Trees+in+Graph+Theory.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cRecognizing and Finding Spanning Trees in Graph Theory\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<section class=\"textbox example\">The power company needs to lay updated distribution lines connecting the ten Oregon cities below to the power grid. How can they minimize the amount of new line to lay?<\/p>\n<div style=\"width: auto;\">\n<table style=\"width: 586px; height: 333px;\">\n<tbody>\n<tr>\n<td>&nbsp;<\/td>\n<td>\u00a0Ashland<\/td>\n<td>Astoria<\/td>\n<td>\u00a0Bend<\/td>\n<td>\u00a0Corvallis<\/td>\n<td>\u00a0Crater Lake<\/td>\n<td>\u00a0Eugene<\/td>\n<td>\u00a0Newport<\/td>\n<td>\u00a0Portland<\/td>\n<td>\u00a0Salem<\/td>\n<td>\u00a0Seaside<\/td>\n<\/tr>\n<tr>\n<td>Ashland<\/td>\n<td>&#8211;<\/td>\n<td>[latex]374[\/latex]<\/td>\n<td>[latex]200[\/latex]<\/td>\n<td>[latex]223[\/latex]<\/td>\n<td>[latex]108[\/latex]<\/td>\n<td>[latex]178[\/latex]<\/td>\n<td>[latex]252[\/latex]<\/td>\n<td>[latex]285[\/latex]<\/td>\n<td>[latex]240[\/latex]<\/td>\n<td>[latex]356[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Astoria<\/td>\n<td>[latex]374[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]255[\/latex]<\/td>\n<td>[latex]166[\/latex]<\/td>\n<td>[latex]433[\/latex]<\/td>\n<td>[latex]199[\/latex]<\/td>\n<td>[latex]135[\/latex]<\/td>\n<td>[latex]95[\/latex]<\/td>\n<td>[latex]136[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Bend<\/td>\n<td>[latex]200[\/latex]<\/td>\n<td>[latex]255[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]277[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]180[\/latex]<\/td>\n<td>[latex]160[\/latex]<\/td>\n<td>[latex]131[\/latex]<\/td>\n<td>[latex]247[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Corvallis<\/td>\n<td>[latex]223[\/latex]<\/td>\n<td>[latex]166[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]430[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]52[\/latex]<\/td>\n<td>[latex]84[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]155[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Crater Lake<\/td>\n<td>[latex]108[\/latex]<\/td>\n<td>[latex]433[\/latex]<\/td>\n<td>[latex]277[\/latex]<\/td>\n<td>[latex]430[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]453[\/latex]<\/td>\n<td>[latex]478[\/latex]<\/td>\n<td>[latex]344[\/latex]<\/td>\n<td>[latex]389[\/latex]<\/td>\n<td>[latex]423[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Eugene<\/td>\n<td>[latex]178[\/latex]<\/td>\n<td>[latex]199[\/latex]<\/td>\n<td>[latex]128[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]453[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]91[\/latex]<\/td>\n<td>[latex]110[\/latex]<\/td>\n<td>[latex]64[\/latex]<\/td>\n<td>[latex]181[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Newport<\/td>\n<td>[latex]252[\/latex]<\/td>\n<td>[latex]135[\/latex]<\/td>\n<td>[latex]180[\/latex]<\/td>\n<td>[latex]52[\/latex]<\/td>\n<td>[latex]478[\/latex]<\/td>\n<td>[latex]91[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]114[\/latex]<\/td>\n<td>[latex]83[\/latex]<\/td>\n<td>[latex]117[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Portland<\/td>\n<td>[latex]285[\/latex]<\/td>\n<td>[latex]95[\/latex]<\/td>\n<td>[latex]160[\/latex]<\/td>\n<td>[latex]84[\/latex]<\/td>\n<td>[latex]344[\/latex]<\/td>\n<td>[latex]110[\/latex]<\/td>\n<td>[latex]114[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>[latex]78[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Salem<\/td>\n<td>[latex]240[\/latex]<\/td>\n<td>[latex]136[\/latex]<\/td>\n<td>[latex]131[\/latex]<\/td>\n<td>[latex]40[\/latex]<\/td>\n<td>[latex]389[\/latex]<\/td>\n<td>[latex]64[\/latex]<\/td>\n<td>[latex]83[\/latex]<\/td>\n<td>[latex]47[\/latex]<\/td>\n<td>&#8211;<\/td>\n<td>[latex]118[\/latex]<\/td>\n<\/tr>\n<tr>\n<td>Seaside<\/td>\n<td>[latex]356[\/latex]<\/td>\n<td>[latex]17[\/latex]<\/td>\n<td>[latex]247[\/latex]<\/td>\n<td>[latex]155[\/latex]<\/td>\n<td>[latex]423[\/latex]<\/td>\n<td>[latex]181[\/latex]<\/td>\n<td>[latex]117[\/latex]<\/td>\n<td>[latex]78[\/latex]<\/td>\n<td>[latex]118[\/latex]<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997641\">Show Solution<\/button> <\/p>\n<div id=\"q997641\" class=\"hidden-answer\" style=\"display: none\"> Using Kruskal\u2019s algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.<\/p>\n<div style=\"text-align: center;\">[latex]\\begin{array}{r@{\\hfill}l} \\text{Seaside to Astoria} && 17 \\text{ miles} \\\\ \\text{Corvallis to Salem} && 40 \\text{ miles} \\\\ \\text{Portland to Salem} && 47 \\text{ miles} \\\\ \\text{Corvallis to Eugene} && 47 \\text{ miles} \\\\ \\text{Corvallis to Newport} && 52 \\text{ miles} \\\\ \\text{Salem to Eugene} && \\text{reject \u2013 closes circuit} \\\\ \\end{array}[\/latex]<\/div>\n<p>&nbsp;<\/p>\n<p><em>The graph up to this point is shown below.<\/em><\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-12919\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Eugene and Corvallis, Salem and Corvallis, Newport and Corvallis, and Salem and Portland.\" width=\"500\" height=\"331\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5.png 686w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182043\/large-Oregon-Circuit-5-350x232.png 350w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/div>\n<p>&nbsp;<\/p>\n<p>Continuing,<\/p>\n<div style=\"text-align: center;\">[latex]\\begin{array}{r@{\\hfill}l} \\text{Newport to Salem} && \\text{reject} \\\\ \\text{Corvallis to Portland} && \\text{reject} \\\\ \\text{Eugene to Newport} && \\text{reject} \\\\ \\text{Portland to Astoria} && \\text{reject} \\\\ \\text{Ashland to Crater Lk} && 108 \\text{ miles} \\\\ \\text{Eugene to Portland} && \\text{reject} \\\\ \\text{Newport to Portland} && \\text{reject} \\\\ \\text{Newport to Seaside} && \\text{reject} \\\\ \\text{Salem to Seaside} && \\text{reject} \\\\ \\text{Bend to Eugene} && 128 \\text{ miles} \\\\ \\text{Bend to Salem} && \\text{reject} \\\\ \\text{Astoria to Newport} && \\text{reject} \\\\ \\text{Salem to Astoria} && \\text{reject} \\\\ \\text{Corvallis to Seaside} && \\text{reject} \\\\ \\text{Portland to Bend} && \\text{reject} \\\\ \\text{Astoria to Corvallis} && \\text{reject} \\\\ \\text{Eugene to Ashland} && 178 \\text{ miles} \\\\ \\end{array}[\/latex]<\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<p>This connects the graph. The total length of cable to lay would be [latex]695[\/latex] miles.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-12920\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Seaside and Portland, Portland and Salem, Salem and Corvallis, Eugene and Corvallis, Newport and Corvallis, Eugene and Bend, Eugene and Ashland, and Ashland and Crater Lake.\" width=\"500\" height=\"331\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6.png 686w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6-300x199.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6-65x43.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6-225x149.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/12182114\/large-Oregon-Circuit-6-350x232.png 350w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/div>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox example\">Find a minimum spanning tree for the weighted graph. Give its total weight.<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium wp-image-8835\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-300x254.png\" alt=\"A weighted graph with five vertices. The vertices are as follows: U, V, W, X, and Z. The edges are labeled as follows. U V, 89. V Y, 24. Y X, 68. X W, 45. W U, 37. U X, 49. W V, 68.\" width=\"300\" height=\"254\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-300x254.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-65x55.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-225x191.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460-350x296.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181640\/3696c0171fec3b179bd4c0e8b8c23dd8f7a30460.png 418w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q997612\">Show Solution<\/button> <\/p>\n<div id=\"q997612\" class=\"hidden-answer\" style=\"display: none\"> There are two possible minimum spanning trees, each with a total weight of [latex]174[\/latex]:<\/p>\n<div style=\"text-align: center;\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium wp-image-8836\" src=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-300x107.png\" alt=\"Two weighted graphs. The vertices in each graph are as follows: U, V, W, X, and Y. The edges in the first graph are as follows. U W, 37. W X, 45. W V, 68. V Y, 24. The edges in the second graph are as follows. U W, 37. W X, 45. X Y, 68. Y V, 24.\" width=\"300\" height=\"107\" srcset=\"https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-300x107.png 300w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-768x275.png 768w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-65x23.png 65w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-225x81.png 225w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f-350x125.png 350w, https:\/\/content-cdn.one.lumenlearning.com\/wp-content\/uploads\/sites\/18\/2023\/04\/05181710\/c983d4b4e2021cfeba4e4c1d1b766fdb3ba7c25f.png 936w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/div>\n<\/div>\n<\/div>\n<\/section>\n","protected":false},"author":15,"menu_order":16,"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":"fresh_take","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\/1539"}],"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":65,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1539\/revisions"}],"predecessor-version":[{"id":15936,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/1539\/revisions\/15936"}],"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\/1539\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=1539"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=1539"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=1539"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=1539"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}