{"id":1860,"date":"2017-03-16T23:04:55","date_gmt":"2017-03-16T23:04:55","guid":{"rendered":"https:\/\/courses.lumenlearning.com\/waymakermath4libarts\/?post_type=chapter&#038;p=1860"},"modified":"2021-02-05T23:49:30","modified_gmt":"2021-02-05T23:49:30","slug":"hamiltonian-circuits","status":"web-only","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/chapter\/hamiltonian-circuits\/","title":{"raw":"Hamiltonian Circuits","rendered":"Hamiltonian Circuits"},"content":{"raw":"<div class=\"textbox learning-objectives\">\r\n<h3>Learning Outcomes<\/h3>\r\n<ul>\r\n \t<li>Identify whether a graph has a Hamiltonian circuit or path<\/li>\r\n \t<li>Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm<\/li>\r\n \t<li>Identify a connected graph that is a spanning tree<\/li>\r\n \t<li>Use Kruskal's algorithm to form a spanning tree, and a minimum cost spanning tree<\/li>\r\n<\/ul>\r\n<\/div>\r\n<h2>Hamiltonian Circuits and the Traveling Salesman Problem<\/h2>\r\nIn the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.\r\n<div class=\"textbox examples\">\r\n<h3>putting all your study skills together<\/h3>\r\nThis section contains a bit of everything you've encountered so far: new vocabulary, new usages of familiar words, multi-step processes, and new ideas. Allow yourself ample time to work through the examples and problems multiple times so that you can develop a good understanding.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Hamiltonian Circuits and Paths<\/h3>\r\n<\/div>\r\n<div>\r\n\r\nA <strong>Hamiltonian circuit<\/strong> is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A <strong>Hamiltonian path<\/strong> also visits every vertex once with no repeats, but does not have to start and end at the same vertex.\r\n\r\n<\/div>\r\n<\/div>\r\nHamiltonian circuits are named for William Rowan Hamilton who studied them in the 1800\u2019s.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nOne Hamiltonian circuit is shown on the graph below. There are several other Hamiltonian circuits possible on this graph. Notice that the circuit only has to visit every vertex once; it does not need to use every edge.\r\n\r\nThis circuit could be notated by the sequence of vertices visited, starting and ending at the same vertex: ABFGCDHMLKJEA. Notice that the same circuit could be written in reverse order, or starting and ending at a different vertex.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225006\/Screen-Shot-2017-03-16-at-3.48.22-PM.png\"><img class=\" wp-image-1862 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225006\/Screen-Shot-2017-03-16-at-3.48.22-PM.png\" alt=\"Rectangular graph with 12 vertices labeled a through M (without I) \" width=\"359\" height=\"186\" \/><\/a>\r\n\r\n<\/div>\r\n<\/div>\r\nUnlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.<a href=\"#_ftn1\">[1]<\/a>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nDoes a Hamiltonian path or circuit exist on the graph below?\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225240\/Untitled17.png\"><img class=\" wp-image-1863 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225240\/Untitled17.png\" alt=\"Arrow shaped graph with 5 vertices labeled A- E, Edge from C to E is not part of the arrow shape. A and C are connected by two edges.\" width=\"231\" height=\"189\" \/><\/a>\r\n\r\nWe can see that once we travel to vertex E there is no way to leave without returning to C, so there is no possibility of a Hamiltonian circuit. If we start at vertex E we can find several Hamiltonian paths, such as ECDAB and ECABD\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\n[ohm_question]6557[\/ohm_question]\r\n\r\n<\/div>\r\nWith Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.\r\n\r\nWatch this video to see the examples above worked out.\r\n\r\nhttps:\/\/youtu.be\/SjtVuw4-1Qo\r\n\r\nThis problem is called the <strong>Traveling salesman problem<\/strong> (TSP) because the question can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost?\r\n\r\nTo answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225500\/Untitled18.png\"><img class=\" wp-image-1864 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225500\/Untitled18.png\" alt=\"Star Shaped graph with 5 vertices named home (Seattle), Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: home and dallas - $12, home and atlanta - $14, home and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $16, LA and atlanta - $170, chicago and dallas - $16\" width=\"487\" height=\"248\" \/><\/a>\r\n\r\nquestion can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost?\r\n\r\nTo answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Brute Force Algorithm (a.k.a. exhaustive search)<\/h3>\r\n<\/div>\r\n<div>\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0 List all possible Hamiltonian circuits\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0 Find the length of each circuit by adding the edge weights\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0 Select the circuit with minimal total weight.\r\n\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nApply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img class=\"alignnone size-full wp-image-1865\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. \" width=\"85\" height=\"78\" \/><\/a>\r\n<div>\r\n\r\nTo apply the Brute force algorithm, we list all possible Hamiltonian circuits and calculate their weight:\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>Circuit<\/strong><\/td>\r\n<td><strong>Weight<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>ABCDA<\/td>\r\n<td>4+13+8+1 = 26<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>ABDCA<\/td>\r\n<td>4+9+8+2 = 23<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>ACBDA<\/td>\r\n<td>2+13+9+1 = 25<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\nNote: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights.\r\n\r\n&nbsp;\r\n\r\nFrom this we can see that the second circuit, ABDCA, is the optimal circuit.\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<\/div>\r\n<\/div>\r\nWatch these examples worked again in the following video.\r\n\r\nhttps:\/\/youtu.be\/wDXQ6tWsJxw\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\n[ohm_question]78158[\/ohm_question]\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\nThe Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let\u2019s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a <strong>complete graph.<\/strong>\r\n\r\nSuppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home.\r\n\r\nThis can be shown visually:\r\n\r\n&nbsp;\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230435\/Untitled20.png\"><img class=\" wp-image-1866 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230435\/Untitled20-300x83.png\" alt=\"\" width=\"570\" height=\"158\" \/><\/a>\r\n\r\n&nbsp;\r\n<div>\r\n\r\nCounting the number of routes, we can see thereare [latex]4\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. For six cities there would be [latex]5\\cdot{4}\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Number of Possible Circuits<\/h3>\r\n<\/div>\r\n<div>\r\n\r\nFor <em>N<\/em> vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\\dots{3}\\cdot{2}\\cdot{1}[\/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\\frac{(n-1)!}{2}[\/latex] unique circuits.\r\n\r\nThe exclamation symbol, !, is read \u201cfactorial\u201d and is shorthand for the product shown.\r\n\r\n<\/div>\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nHow many circuits would a complete graph with 8 vertices have?\r\n\r\nA complete graph with 8 vertices would have = 5040 possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving 2520 unique routes.\r\n\r\nWhile this is a lot, it doesn\u2019t seem unreasonably huge. But consider what happens as the number of cities increase:\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>Cities<\/strong><\/td>\r\n<td><strong>Unique Hamiltonian Circuits<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>9<\/td>\r\n<td>8!\/2 = 20,160<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>10<\/td>\r\n<td>9!\/2 = 181,440<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>11<\/td>\r\n<td>10!\/2 = 1,814,400<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>15<\/td>\r\n<td>14!\/2 = 43,589,145,600<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>20<\/td>\r\n<td>19!\/2 = 60,822,550,204,416,000<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<\/div>\r\nWatch these examples worked again in the following video.\r\n\r\nhttps:\/\/youtu.be\/DwZw4t0qxuQ\r\n\r\n&nbsp;\r\n\r\nAs you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only 20 cities! Certainly Brute Force is <strong>not <\/strong>an efficient algorithm.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Nearest Neighbor Algorithm (NNA)<\/h3>\r\n<\/div>\r\n<div>\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0 Select a starting point.\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0 Move to the nearest unvisited vertex (the edge with smallest weight).\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0 Repeat until the circuit is complete.\r\n\r\n<\/div>\r\n<\/div>\r\nUnfortunately, no one has yet found an efficient <em>and<\/em> optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to <strong>heuristic algorithms<\/strong>; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nConsider our earlier graph, shown to the right.\r\n\r\nStarting at vertex A, the nearest neighbor is vertex D with a weight of 1.\r\n\r\nFrom D, the nearest neighbor is C, with a weight of 8.\r\n\r\nFrom C, our only option is to move to vertex B, the only unvisited vertex, with a cost of 13.\r\n\r\nFrom B we return to A with a weight of 4.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img class=\" wp-image-1865 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"126\" height=\"116\" \/><\/a>\r\n\r\nThe resulting circuit is ADCBA with a total weight of [latex]1+8+13+4 = 26[\/latex].\r\n\r\n<\/div>\r\n<\/div>\r\nWatch the example worked out in the following video.\r\n\r\nhttps:\/\/youtu.be\/SqOP5n9bNX4\r\n\r\nWe ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a <strong>greedy<\/strong> algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nConsider again our salesman. Starting in Seattle, the nearest neighbor (cheapest flight) is to LA, at a cost of $70. From there:\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231425\/Untitled21.png\"><img class=\" wp-image-1870 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231425\/Untitled21.png\" alt=\"\" width=\"438\" height=\"234\" \/><\/a>\r\n\r\nLA to Chicago: $100\r\n\r\nChicago to Atlanta: $75\r\n\r\nAtlanta to Dallas: $85\r\n\r\nDallas to Seattle: $120\r\n\r\nTotal cost: $450\r\n\r\n&nbsp;\r\n\r\nIn this case, nearest neighbor did find the optimal circuit.\r\n\r\n<\/div>\r\n<\/div>\r\nWatch this example worked out again in this video.\r\n\r\nhttps:\/\/youtu.be\/3Eq36iqjGKI\r\n\r\n&nbsp;\r\n\r\nGoing back to our first example, how could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn\u2019t a big deal.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nWe will revisit the graph from Example 17.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img class=\"wp-image-1865 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"260\" height=\"238\" \/><\/a>\r\n\r\nStarting at vertex A resulted in a circuit with weight 26.\r\n\r\nStarting at vertex B, the nearest neighbor circuit is BADCB with a weight of 4+1+8+13 = 26. This is the same circuit we found starting at vertex A. No better.\r\n\r\nStarting at vertex C, the nearest neighbor circuit is CADBC with a weight of 2+1+9+13 = 25. Better!\r\n\r\nStarting at vertex D, the nearest neighbor circuit is DACBA. Notice that this is actually the same circuit we found starting at C, just written with a different starting vertex.\r\n\r\nThe RNNA was able to produce a slightly better circuit with a weight of 25, but still not the optimal circuit in this case. Notice that even though we found the circuit by starting at vertex C, we could still write the circuit starting at A: ADBCA or ACBDA.\r\n\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\nThe table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled A-F for convenience.\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><\/td>\r\n<td>A<\/td>\r\n<td>B<\/td>\r\n<td>C<\/td>\r\n<td>D<\/td>\r\n<td>E<\/td>\r\n<td>F<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>A<\/td>\r\n<td>--<\/td>\r\n<td>44<\/td>\r\n<td>34<\/td>\r\n<td>12<\/td>\r\n<td>40<\/td>\r\n<td>41<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>B<\/td>\r\n<td>44<\/td>\r\n<td>--<\/td>\r\n<td>31<\/td>\r\n<td>43<\/td>\r\n<td>24<\/td>\r\n<td>50<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>C<\/td>\r\n<td>34<\/td>\r\n<td>31<\/td>\r\n<td>--<\/td>\r\n<td>20<\/td>\r\n<td>39<\/td>\r\n<td>27<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>D<\/td>\r\n<td>12<\/td>\r\n<td>43<\/td>\r\n<td>20<\/td>\r\n<td>--<\/td>\r\n<td>11<\/td>\r\n<td>17<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>E<\/td>\r\n<td>40<\/td>\r\n<td>24<\/td>\r\n<td>39<\/td>\r\n<td>11<\/td>\r\n<td>--<\/td>\r\n<td>42<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>F<\/td>\r\n<td>41<\/td>\r\n<td>50<\/td>\r\n<td>27<\/td>\r\n<td>17<\/td>\r\n<td>42<\/td>\r\n<td>--<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<div>\r\n\r\na.\u00a0\u00a0\u00a0\u00a0 Find the circuit generated by the NNA starting at vertex B.\r\n\r\nb.\u00a0\u00a0\u00a0\u00a0 Find the circuit generated by the RNNA.\r\n\r\n<\/div>\r\n<\/div>\r\nWhile certainly better than the basic NNA, unfortunately, the RNNA is still greedy and will produce very bad results for some graphs. As an alternative, our next approach will step back and look at the \u201cbig picture\u201d \u2013 it will select first the edges that are shortest, and then fill in the gaps.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nUsing the four vertex graph from earlier, we can use the Sorted Edges algorithm.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img class=\"alignnone size-full wp-image-1865\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"85\" height=\"78\" \/><\/a>\r\n\r\nThe cheapest edge is AD, with a cost of 1. We highlight that edge to mark it selected.\r\n\r\n<\/div>\r\nThe next shortest edge is AC, with a weight of 2, so we highlight that edge.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231715\/Untitled22.png\"><img class=\"wp-image-1871 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231715\/Untitled22.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. The edge between A and D is highlighted\" width=\"165\" height=\"151\" \/><\/a>\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231825\/Untitled23.png\"><img class=\" wp-image-1872 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231825\/Untitled23.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"179\" height=\"164\" \/><\/a>\r\n\r\nFor the third edge, we\u2019d like to add AB, but that would give vertex A degree 3, which is not allowed in a Hamiltonian circuit. The next shortest edge is CD, but that edge would create a circuit ACDA that does not include vertex B, so we reject that edge. The next shortest edge is BD, so we add that edge to the graph.\r\n\r\n[caption id=\"attachment_1873\" align=\"aligncenter\" width=\"180\"]<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231918\/Untitled24.png\"><img class=\"wp-image-1873\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231918\/Untitled24.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. Edge between A and B is highlighted.\" width=\"180\" height=\"165\" \/><\/a> BAD[\/caption]\r\n\r\n[caption id=\"attachment_1874\" align=\"aligncenter\" width=\"180\"]<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232033\/Untitled25.png\"><img class=\"wp-image-1874\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232033\/Untitled25.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. \" width=\"180\" height=\"165\" \/><\/a> BAD[\/caption]\r\n\r\n[caption id=\"attachment_1875\" align=\"aligncenter\" width=\"224\"]<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232208\/Untitled26.png\"><img class=\"wp-image-1875 \" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232208\/Untitled26.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"224\" height=\"206\" \/><\/a> OK[\/caption]\r\n\r\n<div>\r\n\r\nWe then add the last edge to complete the circuit: ACBDA with weight 25.\r\n<div>\r\n\r\nNotice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232257\/Untitled27.png\"><img class=\"wp-image-1876 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232257\/Untitled27.png\" alt=\"Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23. \" width=\"180\" height=\"165\" \/><\/a>\r\n\r\nWhile the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nYour teacher\u2019s band, <em>Derivative Work<\/em>, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.\r\n<div style=\"width: auto;\">\r\n<table style=\"width: 586px; height: 333px;\">\r\n<tbody>\r\n<tr>\r\n<td><\/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>374<\/td>\r\n<td>200<\/td>\r\n<td>223<\/td>\r\n<td>108<\/td>\r\n<td>178<\/td>\r\n<td>252<\/td>\r\n<td>285<\/td>\r\n<td>240<\/td>\r\n<td>356<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Astoria<\/td>\r\n<td>374<\/td>\r\n<td>-<\/td>\r\n<td>255<\/td>\r\n<td>166<\/td>\r\n<td>433<\/td>\r\n<td>199<\/td>\r\n<td>135<\/td>\r\n<td>95<\/td>\r\n<td>136<\/td>\r\n<td>17<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bend<\/td>\r\n<td>200<\/td>\r\n<td>255<\/td>\r\n<td>-<\/td>\r\n<td>128<\/td>\r\n<td>277<\/td>\r\n<td>128<\/td>\r\n<td>180<\/td>\r\n<td>160<\/td>\r\n<td>131<\/td>\r\n<td>247<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Corvallis<\/td>\r\n<td>223<\/td>\r\n<td>166<\/td>\r\n<td>128<\/td>\r\n<td>-<\/td>\r\n<td>430<\/td>\r\n<td>47<\/td>\r\n<td>52<\/td>\r\n<td>84<\/td>\r\n<td>40<\/td>\r\n<td>155<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Crater Lake<\/td>\r\n<td>108<\/td>\r\n<td>433<\/td>\r\n<td>277<\/td>\r\n<td>430<\/td>\r\n<td>-<\/td>\r\n<td>453<\/td>\r\n<td>478<\/td>\r\n<td>344<\/td>\r\n<td>389<\/td>\r\n<td>423<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Eugene<\/td>\r\n<td>178<\/td>\r\n<td>199<\/td>\r\n<td>128<\/td>\r\n<td>47<\/td>\r\n<td>453<\/td>\r\n<td>-<\/td>\r\n<td>91<\/td>\r\n<td>110<\/td>\r\n<td>64<\/td>\r\n<td>181<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Newport<\/td>\r\n<td>252<\/td>\r\n<td>135<\/td>\r\n<td>180<\/td>\r\n<td>52<\/td>\r\n<td>478<\/td>\r\n<td>91<\/td>\r\n<td>-<\/td>\r\n<td>114<\/td>\r\n<td>83<\/td>\r\n<td>117<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Portland<\/td>\r\n<td>285<\/td>\r\n<td>95<\/td>\r\n<td>160<\/td>\r\n<td>84<\/td>\r\n<td>344<\/td>\r\n<td>110<\/td>\r\n<td>114<\/td>\r\n<td>-<\/td>\r\n<td>47<\/td>\r\n<td>78<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Salem<\/td>\r\n<td>240<\/td>\r\n<td>136<\/td>\r\n<td>131<\/td>\r\n<td>40<\/td>\r\n<td>389<\/td>\r\n<td>64<\/td>\r\n<td>83<\/td>\r\n<td>47<\/td>\r\n<td>-<\/td>\r\n<td>118<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Seaside<\/td>\r\n<td>356<\/td>\r\n<td>17<\/td>\r\n<td>247<\/td>\r\n<td>155<\/td>\r\n<td>423<\/td>\r\n<td>181<\/td>\r\n<td>117<\/td>\r\n<td>78<\/td>\r\n<td>118<\/td>\r\n<td>-<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<p style=\"text-align: center;\"><em>To see the entire table, scroll to the right<\/em><\/p>\r\n<p style=\"text-align: left;\">Using NNA with a large number of cities, you might find it helpful to mark off the cities as they\u2019re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:<\/p>\r\n\r\n<\/div>\r\n<div align=\"center\">\r\n\r\nPortland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47\r\n\r\nSalem to Corvallis\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40\r\n\r\nCorvallis to Eugene\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47\r\n\r\nEugene to Newport\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 91\r\n\r\nNewport to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 117\r\n\r\nSeaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17\r\n\r\nAstoria to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 255\r\n\r\nBend to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 200\r\n\r\nAshland to Crater Lake\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 108\r\n\r\nCrater Lake to Portland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 344\r\n\r\nTotal trip length:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1266 miles\r\n\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: left;\">Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3.<\/p>\r\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232457\/Untitled28.png\"><img class=\" wp-image-1877 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232457\/Untitled28.png\" alt=\"\" width=\"263\" height=\"188\" \/><\/a><\/p>\r\n\r\n<div>\r\n<p style=\"text-align: center;\">We start adding the shortest edges:<\/p>\r\n<p style=\"text-align: center;\">Seaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17 miles<\/p>\r\n<p style=\"text-align: center;\">Corvallis to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40 miles<\/p>\r\n<p style=\"text-align: center;\">Portland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\r\n<p style=\"text-align: center;\">Corvallis to Eugene\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\r\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232601\/Untitled29.png\"><img class=\" wp-image-1878 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232601\/Untitled29.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Eugene and Corvallis, Salem and Corvallis, and Salem and Portland.\" width=\"298\" height=\"228\" \/><\/a><\/p>\r\n\r\n<div>\r\n\r\nThe graph after adding these edges is shown to the right.\u00a0\u00a0 The next shortest edge is from Corvallis to Newport at 52 miles, but adding that edge would give Corvallis degree 3.\r\n\r\n&nbsp;\r\n\r\nContinuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree 2.\r\n\r\nPortland to Seaside \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 78 miles\r\n\r\nEugene to Newport\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 91 miles\r\n\r\nPortland to Astoria\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (reject \u2013 closes circuit)\r\n\r\nAshland to Crater Lk\u00a0 108 miles\r\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232748\/Untitled30.png\"><img class=\" wp-image-1879 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232748\/Untitled30.png\" alt=\"\" width=\"331\" height=\"253\" \/><\/a><\/p>\r\n\r\n<div>\r\n\r\nThe graph after adding these edges is shown to the right. At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree 2.\r\n\r\n&nbsp;\r\n<p style=\"text-align: center;\">Newport to Astoria\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (reject \u2013 closes circuit)<\/p>\r\n<p style=\"text-align: center;\">Newport to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 180 miles<\/p>\r\n<p style=\"text-align: center;\">Bend to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 200 miles<\/p>\r\n&nbsp;\r\n<p style=\"text-align: left;\">At this point the only way to complete the circuit is to add:<\/p>\r\n<p style=\"text-align: left;\">Crater Lk to Astoria\u00a0\u00a0 433 miles. \u00a0The final circuit, written to start at Portland, is:<\/p>\r\n<p style=\"text-align: left;\">Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland. \u00a0Total trip length: 1241 miles.<\/p>\r\n<p style=\"text-align: left;\">While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in 1069 miles:<\/p>\r\n<p style=\"text-align: left;\">Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland<\/p>\r\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232906\/Untitled31.png\"><img class=\"wp-image-1880 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232906\/Untitled31.png\" alt=\"\" width=\"399\" height=\"305\" \/><\/a><\/p>\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<p style=\"text-align: left;\"><\/p>\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\nWatch the example of nearest neighbor algorithm for traveling from city to city using a table worked out in the video below.\r\n\r\nhttps:\/\/youtu.be\/GFp-046PQx0\r\n\r\nIn the next video we use the same table, but use sorted edges to plan the trip.\r\n\r\nhttps:\/\/youtu.be\/_gXyujMsrmw\r\n<div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\n<div>\r\n\r\nFind the circuit produced by the Sorted Edges algorithm using the graph below.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232952\/Untitled32.png\"><img class=\"aligncenter wp-image-1881\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232952\/Untitled32.png\" alt=\"graph with 6 vertices and 14 edges. between B and E is 13, between E and G is 45, between G and F is 19, between F and C is 37, between c and A is 33 between A and B is 11. Between B and C is 25, between B and F is 23, between E and A is 14, between E and F is 15. Between G and B is 13, and between G and C is 36. Between G and A is 27.\" width=\"325\" height=\"187\" \/><\/a>\r\n\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=6565&amp;theme=oea&amp;iframe_resize_id=mom1[\/embed]\r\n\r\n<\/div>\r\n<\/div>\r\n<h2>\u00a0Spanning Trees<\/h2>\r\nA company requires reliable internet and phone connectivity between their five offices (named A, B, C, D, and E for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233317\/Untitled33.png\"><img class=\" wp-image-1882 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233317\/Untitled33.png\" alt=\"graph with 5 vertices and 11 edges. between A and B is $4, between B and C is $10, between C and D is $7, between D and E is $13, between E and B is $6, between E and C is $11, between A and D is $6, between A and C is $8. Between B and E is $6, between B and D is $14.\" width=\"294\" height=\"176\" \/><\/a>\r\n\r\nIn this case, we don\u2019t need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Spanning Tree<\/h3>\r\n<\/div>\r\n<div>\r\n\r\nA <strong>spanning tree<\/strong> is a connected graph using all vertices in which there are no circuits.\r\n\r\nIn other words, there is a path from any vertex to any other vertex, but no circuits.\r\n\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n\r\nSome examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233719\/Screen-Shot-2017-03-16-at-4.37.02-PM.png\"><img class=\"alignnone wp-image-1883\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233719\/Screen-Shot-2017-03-16-at-4.37.02-PM-300x43.png\" alt=\"Five triangular graphs where there are no Euler circuits, but every vertex has a path to every other vertex.\" width=\"467\" height=\"67\" \/><\/a>\r\n\r\nUsually we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a <strong>subgraph<\/strong> \u2013 a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn\u2019t already exist.\r\n\r\nOf course, any random spanning tree isn\u2019t really what we want. We want the <strong>minimum cost spanning tree (MCST)<\/strong>.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Minimum Cost Spanning Tree (MCST)<\/h3>\r\n<\/div>\r\n<div>\r\n\r\nThe minimum cost spanning tree is the spanning tree with the smallest total edge weight.\r\n\r\n<\/div>\r\n<\/div>\r\nA nearest neighbor style approach doesn\u2019t make as much sense here since we don\u2019t need a circuit, so instead we will take an approach similar to sorted edges.\r\n<div class=\"textbox\">\r\n<div>\r\n<h3>Kruskal\u2019s Algorithm<\/h3>\r\n<\/div>\r\n<div>\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\nRepeat until a spanning tree is formed\r\n\r\n<\/div>\r\n<\/div>\r\n&nbsp;\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nUsing our phone line graph from above, begin adding edges:\r\n\r\nAB\u00a0\u00a0\u00a0\u00a0\u00a0 $4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK\r\n\r\nAE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK\r\n\r\nBE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $6\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject \u2013 closes circuit ABEA\r\n\r\nDC\u00a0\u00a0\u00a0\u00a0\u00a0 $7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK\r\n\r\nAC\u00a0\u00a0\u00a0\u00a0\u00a0 $8\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233916\/Untitled34.png\"><img class=\"aligncenter wp-image-1884\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233916\/Untitled34.png\" alt=\"A graph with five vertices labeled A through E. A to B is $4, A to E is $5, B to E is $6, D to C is $7, A to C is $8. AB, AC, AE, and DC are shown in red.\" width=\"362\" height=\"219\" \/><\/a>\r\n\r\nAt this point we stop \u2013 every vertex is now connected, so we have formed a spanning tree with cost $24 thousand a year.\r\n\r\n<\/div>\r\n<\/div>\r\nRemarkably, Kruskal\u2019s algorithm is both optimal and efficient; we are guaranteed to always produce the optimal MCST.\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\n<div>\r\n\r\nThe 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<div style=\"width: auto;\">\r\n<table style=\"width: 586px; height: 333px;\">\r\n<tbody>\r\n<tr>\r\n<td><\/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>374<\/td>\r\n<td>200<\/td>\r\n<td>223<\/td>\r\n<td>108<\/td>\r\n<td>178<\/td>\r\n<td>252<\/td>\r\n<td>285<\/td>\r\n<td>240<\/td>\r\n<td>356<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Astoria<\/td>\r\n<td>374<\/td>\r\n<td>-<\/td>\r\n<td>255<\/td>\r\n<td>166<\/td>\r\n<td>433<\/td>\r\n<td>199<\/td>\r\n<td>135<\/td>\r\n<td>95<\/td>\r\n<td>136<\/td>\r\n<td>17<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Bend<\/td>\r\n<td>200<\/td>\r\n<td>255<\/td>\r\n<td>-<\/td>\r\n<td>128<\/td>\r\n<td>277<\/td>\r\n<td>128<\/td>\r\n<td>180<\/td>\r\n<td>160<\/td>\r\n<td>131<\/td>\r\n<td>247<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Corvallis<\/td>\r\n<td>223<\/td>\r\n<td>166<\/td>\r\n<td>128<\/td>\r\n<td>-<\/td>\r\n<td>430<\/td>\r\n<td>47<\/td>\r\n<td>52<\/td>\r\n<td>84<\/td>\r\n<td>40<\/td>\r\n<td>155<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Crater Lake<\/td>\r\n<td>108<\/td>\r\n<td>433<\/td>\r\n<td>277<\/td>\r\n<td>430<\/td>\r\n<td>-<\/td>\r\n<td>453<\/td>\r\n<td>478<\/td>\r\n<td>344<\/td>\r\n<td>389<\/td>\r\n<td>423<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Eugene<\/td>\r\n<td>178<\/td>\r\n<td>199<\/td>\r\n<td>128<\/td>\r\n<td>47<\/td>\r\n<td>453<\/td>\r\n<td>-<\/td>\r\n<td>91<\/td>\r\n<td>110<\/td>\r\n<td>64<\/td>\r\n<td>181<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Newport<\/td>\r\n<td>252<\/td>\r\n<td>135<\/td>\r\n<td>180<\/td>\r\n<td>52<\/td>\r\n<td>478<\/td>\r\n<td>91<\/td>\r\n<td>-<\/td>\r\n<td>114<\/td>\r\n<td>83<\/td>\r\n<td>117<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Portland<\/td>\r\n<td>285<\/td>\r\n<td>95<\/td>\r\n<td>160<\/td>\r\n<td>84<\/td>\r\n<td>344<\/td>\r\n<td>110<\/td>\r\n<td>114<\/td>\r\n<td>-<\/td>\r\n<td>47<\/td>\r\n<td>78<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Salem<\/td>\r\n<td>240<\/td>\r\n<td>136<\/td>\r\n<td>131<\/td>\r\n<td>40<\/td>\r\n<td>389<\/td>\r\n<td>64<\/td>\r\n<td>83<\/td>\r\n<td>47<\/td>\r\n<td>-<\/td>\r\n<td>118<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>Seaside<\/td>\r\n<td>356<\/td>\r\n<td>17<\/td>\r\n<td>247<\/td>\r\n<td>155<\/td>\r\n<td>423<\/td>\r\n<td>181<\/td>\r\n<td>117<\/td>\r\n<td>78<\/td>\r\n<td>118<\/td>\r\n<td>-<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<div style=\"text-align: center;\"><em>To see the entire table, scroll to the right<\/em><\/div>\r\n<div style=\"text-align: center;\"><\/div>\r\n<div>\r\n\r\nUsing Kruskal\u2019s algorithm, we add edges from cheapest to most expensive, rejecting any that close a circuit. We stop when the graph is connected.\r\n<div align=\"center\">\r\n\r\nSeaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17 milesCorvallis to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40 miles\r\n\r\nPortland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles\r\n\r\nCorvallis to Eugene\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles\r\n\r\nCorvallis to Newport\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 52 miles\r\n\r\nSalem to Eugene \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 reject \u2013 closes circuit\r\n\r\nPortland to Seaside\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 78 miles\r\n<p style=\"text-align: center;\"><em>The graph up to this point is shown below.<\/em><\/p>\r\n<p style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234123\/Untitled35.png\"><img class=\"alignnone wp-image-1885\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234123\/Untitled35.png\" alt=\"\" width=\"298\" height=\"228\" \/><\/a><\/p>\r\n<p style=\"text-align: left;\">Continuing,<\/p>\r\nNewport to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nCorvallis to Portland\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nEugene to Newport\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nPortland to Astoria\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nAshland to Crater Lk\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 108 miles\r\n\r\nEugene to Portland\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nNewport to Portland\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nNewport to Seaside\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n<div>\r\n\r\nSalem to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nBend to Eugene\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 128 miles\r\n\r\nBend to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nAstoria to Newport \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nSalem to Astoria \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nCorvallis to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nPortland to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nAstoria to Corvallis\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject\r\n\r\nEugene to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 178 miles\r\n\r\n&nbsp;\r\n\r\nThis connects the graph. The total length of cable to lay would be 695 miles.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234225\/Untitled36.png\"><img class=\"alignnone wp-image-1886\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234225\/Untitled36.png\" alt=\"\" width=\"342\" height=\"260\" \/><\/a>\r\n\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\n<\/div>\r\nWatch the example above worked out in the following video, without a table.\r\n\r\nhttps:\/\/youtu.be\/gaXM0HNErc4\r\n\r\nNow we present the same example, with a table in the following video.\r\n\r\nhttps:\/\/youtu.be\/Pu2_2ftkwdo\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\nFind a minimum cost spanning tree on the graph below using Kruskal\u2019s algorithm.\r\n\r\n<a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234312\/Untitled37.png\"><img class=\"aligncenter wp-image-1887\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234312\/Untitled37.png\" alt=\"graph with 6 vertices and 14 edges. between B and E is 13, between E and G is 45, between G and F is 19, between F and C is 37, between c and A is 33 between A and B is 11. Between B and C is 25, between B and F is 23, between E and A is 14, between E and F is 15. Between G and B is 13, and between G and C is 36. Between G and A is 27.\" width=\"309\" height=\"178\" \/><\/a>\r\n\r\n[embed]https:\/\/www.myopenmath.com\/multiembedq.php?id=6581&amp;theme=oea&amp;iframe_resize_id=mom5[\/embed]\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<a href=\"#_ftnref1\">[1]<\/a> There are some theorems that can be used in specific circumstances, such as Dirac\u2019s theorem, which says that a Hamiltonian circuit must exist on a graph with <em>n<\/em> vertices if each vertex has degree <em>n<\/em>\/2 or greater.\r\n\r\n<\/div>","rendered":"<div class=\"textbox learning-objectives\">\n<h3>Learning Outcomes<\/h3>\n<ul>\n<li>Identify whether a graph has a Hamiltonian circuit or path<\/li>\n<li>Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm<\/li>\n<li>Identify a connected graph that is a spanning tree<\/li>\n<li>Use Kruskal&#8217;s algorithm to form a spanning tree, and a minimum cost spanning tree<\/li>\n<\/ul>\n<\/div>\n<h2>Hamiltonian Circuits and the Traveling Salesman Problem<\/h2>\n<p>In the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.<\/p>\n<div class=\"textbox examples\">\n<h3>putting all your study skills together<\/h3>\n<p>This section contains a bit of everything you&#8217;ve encountered so far: new vocabulary, new usages of familiar words, multi-step processes, and new ideas. Allow yourself ample time to work through the examples and problems multiple times so that you can develop a good understanding.<\/p>\n<\/div>\n<div class=\"textbox\">\n<div>\n<h3>Hamiltonian Circuits and Paths<\/h3>\n<\/div>\n<div>\n<p>A <strong>Hamiltonian circuit<\/strong> is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A <strong>Hamiltonian path<\/strong> also visits every vertex once with no repeats, but does not have to start and end at the same vertex.<\/p>\n<\/div>\n<\/div>\n<p>Hamiltonian circuits are named for William Rowan Hamilton who studied them in the 1800\u2019s.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>One Hamiltonian circuit is shown on the graph below. There are several other Hamiltonian circuits possible on this graph. Notice that the circuit only has to visit every vertex once; it does not need to use every edge.<\/p>\n<p>This circuit could be notated by the sequence of vertices visited, starting and ending at the same vertex: ABFGCDHMLKJEA. Notice that the same circuit could be written in reverse order, or starting and ending at a different vertex.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225006\/Screen-Shot-2017-03-16-at-3.48.22-PM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1862 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225006\/Screen-Shot-2017-03-16-at-3.48.22-PM.png\" alt=\"Rectangular graph with 12 vertices labeled a through M (without I)\" width=\"359\" height=\"186\" \/><\/a><\/p>\n<\/div>\n<\/div>\n<p>Unlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.<a href=\"#_ftn1\">[1]<\/a><\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Does a Hamiltonian path or circuit exist on the graph below?<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225240\/Untitled17.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1863 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225240\/Untitled17.png\" alt=\"Arrow shaped graph with 5 vertices labeled A- E, Edge from C to E is not part of the arrow shape. A and C are connected by two edges.\" width=\"231\" height=\"189\" \/><\/a><\/p>\n<p>We can see that once we travel to vertex E there is no way to leave without returning to C, so there is no possibility of a Hamiltonian circuit. If we start at vertex E we can find several Hamiltonian paths, such as ECDAB and ECABD<\/p>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p><iframe loading=\"lazy\" id=\"ohm6557\" class=\"resizable\" src=\"https:\/\/ohm.lumenlearning.com\/multiembedq.php?id=6557&theme=oea&iframe_resize_id=ohm6557&show_question_numbers\" width=\"100%\" height=\"150\"><\/iframe><\/p>\n<\/div>\n<p>With Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.<\/p>\n<p>Watch this video to see the examples above worked out.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Hamiltonian circuits\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/SjtVuw4-1Qo?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>This problem is called the <strong>Traveling salesman problem<\/strong> (TSP) because the question can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost?<\/p>\n<p>To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225500\/Untitled18.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1864 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16225500\/Untitled18.png\" alt=\"Star Shaped graph with 5 vertices named home (Seattle), Dallas, Atlanta, Chicago, LA and the following dollar amounts between the cities: home and dallas - $12, home and atlanta - $14, home and LA $70, LA and chicago - $100, chicago and atlanta - $75, atlanta and dallas - $85, dallas and chicago - $16, LA and atlanta - $170, chicago and dallas - $16\" width=\"487\" height=\"248\" \/><\/a><\/p>\n<p>question can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost?<\/p>\n<p>To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Brute Force Algorithm (a.k.a. exhaustive search)<\/h3>\n<\/div>\n<div>\n<p>1.\u00a0\u00a0\u00a0\u00a0 List all possible Hamiltonian circuits<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0 Find the length of each circuit by adding the edge weights<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0 Select the circuit with minimal total weight.<\/p>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1865\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"85\" height=\"78\" \/><\/a><\/p>\n<div>\n<p>To apply the Brute force algorithm, we list all possible Hamiltonian circuits and calculate their weight:<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Circuit<\/strong><\/td>\n<td><strong>Weight<\/strong><\/td>\n<\/tr>\n<tr>\n<td>ABCDA<\/td>\n<td>4+13+8+1 = 26<\/td>\n<\/tr>\n<tr>\n<td>ABDCA<\/td>\n<td>4+9+8+2 = 23<\/td>\n<\/tr>\n<tr>\n<td>ACBDA<\/td>\n<td>2+13+9+1 = 25<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>Note: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights.<\/p>\n<p>&nbsp;<\/p>\n<p>From this we can see that the second circuit, ABDCA, is the optimal circuit.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<\/div>\n<p>Watch these examples worked again in the following video.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-2\" title=\"TSP by brute force\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/wDXQ6tWsJxw?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p><iframe loading=\"lazy\" id=\"ohm78158\" class=\"resizable\" src=\"https:\/\/ohm.lumenlearning.com\/multiembedq.php?id=78158&theme=oea&iframe_resize_id=ohm78158&show_question_numbers\" width=\"100%\" height=\"150\"><\/iframe><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>The Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let\u2019s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a <strong>complete graph.<\/strong><\/p>\n<p>Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home.<\/p>\n<p>This can be shown visually:<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230435\/Untitled20.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1866 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230435\/Untitled20-300x83.png\" alt=\"\" width=\"570\" height=\"158\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<div>\n<p>Counting the number of routes, we can see thereare [latex]4\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes. For six cities there would be [latex]5\\cdot{4}\\cdot{3}\\cdot{2}\\cdot{1}[\/latex] routes.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Number of Possible Circuits<\/h3>\n<\/div>\n<div>\n<p>For <em>N<\/em> vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\\dots{3}\\cdot{2}\\cdot{1}[\/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\\frac{(n-1)!}{2}[\/latex] unique circuits.<\/p>\n<p>The exclamation symbol, !, is read \u201cfactorial\u201d and is shorthand for the product shown.<\/p>\n<\/div>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>How many circuits would a complete graph with 8 vertices have?<\/p>\n<p>A complete graph with 8 vertices would have = 5040 possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving 2520 unique routes.<\/p>\n<p>While this is a lot, it doesn\u2019t seem unreasonably huge. But consider what happens as the number of cities increase:<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Cities<\/strong><\/td>\n<td><strong>Unique Hamiltonian Circuits<\/strong><\/td>\n<\/tr>\n<tr>\n<td>9<\/td>\n<td>8!\/2 = 20,160<\/td>\n<\/tr>\n<tr>\n<td>10<\/td>\n<td>9!\/2 = 181,440<\/td>\n<\/tr>\n<tr>\n<td>11<\/td>\n<td>10!\/2 = 1,814,400<\/td>\n<\/tr>\n<tr>\n<td>15<\/td>\n<td>14!\/2 = 43,589,145,600<\/td>\n<\/tr>\n<tr>\n<td>20<\/td>\n<td>19!\/2 = 60,822,550,204,416,000<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>Watch these examples worked again in the following video.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-3\" title=\"Number of circuits in a complete graph\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/DwZw4t0qxuQ?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<p>As you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only 20 cities! Certainly Brute Force is <strong>not <\/strong>an efficient algorithm.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Nearest Neighbor Algorithm (NNA)<\/h3>\n<\/div>\n<div>\n<p>1.\u00a0\u00a0\u00a0\u00a0 Select a starting point.<\/p>\n<p>2.\u00a0\u00a0\u00a0\u00a0 Move to the nearest unvisited vertex (the edge with smallest weight).<\/p>\n<p>3.\u00a0\u00a0\u00a0\u00a0 Repeat until the circuit is complete.<\/p>\n<\/div>\n<\/div>\n<p>Unfortunately, no one has yet found an efficient <em>and<\/em> optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to <strong>heuristic algorithms<\/strong>; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Consider our earlier graph, shown to the right.<\/p>\n<p>Starting at vertex A, the nearest neighbor is vertex D with a weight of 1.<\/p>\n<p>From D, the nearest neighbor is C, with a weight of 8.<\/p>\n<p>From C, our only option is to move to vertex B, the only unvisited vertex, with a cost of 13.<\/p>\n<p>From B we return to A with a weight of 4.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1865 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"126\" height=\"116\" \/><\/a><\/p>\n<p>The resulting circuit is ADCBA with a total weight of [latex]1+8+13+4 = 26[\/latex].<\/p>\n<\/div>\n<\/div>\n<p>Watch the example worked out in the following video.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-4\" title=\"Nearest Neighbor ex1\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/SqOP5n9bNX4?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a <strong>greedy<\/strong> algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Consider again our salesman. Starting in Seattle, the nearest neighbor (cheapest flight) is to LA, at a cost of $70. From there:<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231425\/Untitled21.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1870 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231425\/Untitled21.png\" alt=\"\" width=\"438\" height=\"234\" \/><\/a><\/p>\n<p>LA to Chicago: $100<\/p>\n<p>Chicago to Atlanta: $75<\/p>\n<p>Atlanta to Dallas: $85<\/p>\n<p>Dallas to Seattle: $120<\/p>\n<p>Total cost: $450<\/p>\n<p>&nbsp;<\/p>\n<p>In this case, nearest neighbor did find the optimal circuit.<\/p>\n<\/div>\n<\/div>\n<p>Watch this example worked out again in this video.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-5\" title=\"Nearest Neighbor ex2\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/3Eq36iqjGKI?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<p>Going back to our first example, how could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn\u2019t a big deal.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>We will revisit the graph from Example 17.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1865 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"260\" height=\"238\" \/><\/a><\/p>\n<p>Starting at vertex A resulted in a circuit with weight 26.<\/p>\n<p>Starting at vertex B, the nearest neighbor circuit is BADCB with a weight of 4+1+8+13 = 26. This is the same circuit we found starting at vertex A. No better.<\/p>\n<p>Starting at vertex C, the nearest neighbor circuit is CADBC with a weight of 2+1+9+13 = 25. Better!<\/p>\n<p>Starting at vertex D, the nearest neighbor circuit is DACBA. Notice that this is actually the same circuit we found starting at C, just written with a different starting vertex.<\/p>\n<p>The RNNA was able to produce a slightly better circuit with a weight of 25, but still not the optimal circuit in this case. Notice that even though we found the circuit by starting at vertex C, we could still write the circuit starting at A: ADBCA or ACBDA.<\/p>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p>The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled A-F for convenience.<\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td>A<\/td>\n<td>B<\/td>\n<td>C<\/td>\n<td>D<\/td>\n<td>E<\/td>\n<td>F<\/td>\n<\/tr>\n<tr>\n<td>A<\/td>\n<td>&#8212;<\/td>\n<td>44<\/td>\n<td>34<\/td>\n<td>12<\/td>\n<td>40<\/td>\n<td>41<\/td>\n<\/tr>\n<tr>\n<td>B<\/td>\n<td>44<\/td>\n<td>&#8212;<\/td>\n<td>31<\/td>\n<td>43<\/td>\n<td>24<\/td>\n<td>50<\/td>\n<\/tr>\n<tr>\n<td>C<\/td>\n<td>34<\/td>\n<td>31<\/td>\n<td>&#8212;<\/td>\n<td>20<\/td>\n<td>39<\/td>\n<td>27<\/td>\n<\/tr>\n<tr>\n<td>D<\/td>\n<td>12<\/td>\n<td>43<\/td>\n<td>20<\/td>\n<td>&#8212;<\/td>\n<td>11<\/td>\n<td>17<\/td>\n<\/tr>\n<tr>\n<td>E<\/td>\n<td>40<\/td>\n<td>24<\/td>\n<td>39<\/td>\n<td>11<\/td>\n<td>&#8212;<\/td>\n<td>42<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>41<\/td>\n<td>50<\/td>\n<td>27<\/td>\n<td>17<\/td>\n<td>42<\/td>\n<td>&#8212;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div>\n<p>a.\u00a0\u00a0\u00a0\u00a0 Find the circuit generated by the NNA starting at vertex B.<\/p>\n<p>b.\u00a0\u00a0\u00a0\u00a0 Find the circuit generated by the RNNA.<\/p>\n<\/div>\n<\/div>\n<p>While certainly better than the basic NNA, unfortunately, the RNNA is still greedy and will produce very bad results for some graphs. As an alternative, our next approach will step back and look at the \u201cbig picture\u201d \u2013 it will select first the edges that are shortest, and then fill in the gaps.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Using the four vertex graph from earlier, we can use the Sorted Edges algorithm.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1865\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16230234\/Untitled19.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle.\" width=\"85\" height=\"78\" \/><\/a><\/p>\n<p>The cheapest edge is AD, with a cost of 1. We highlight that edge to mark it selected.<\/p>\n<\/div>\n<p>The next shortest edge is AC, with a weight of 2, so we highlight that edge.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231715\/Untitled22.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1871 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231715\/Untitled22.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. The edge between A and D is highlighted\" width=\"165\" height=\"151\" \/><\/a><\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231825\/Untitled23.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1872 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231825\/Untitled23.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"179\" height=\"164\" \/><\/a><\/p>\n<p>For the third edge, we\u2019d like to add AB, but that would give vertex A degree 3, which is not allowed in a Hamiltonian circuit. The next shortest edge is CD, but that edge would create a circuit ACDA that does not include vertex B, so we reject that edge. The next shortest edge is BD, so we add that edge to the graph.<\/p>\n<div id=\"attachment_1873\" style=\"width: 190px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231918\/Untitled24.png\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-1873\" class=\"wp-image-1873\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16231918\/Untitled24.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted. Edge between A and B is highlighted.\" width=\"180\" height=\"165\" \/><\/a><\/p>\n<p id=\"caption-attachment-1873\" class=\"wp-caption-text\">BAD<\/p>\n<\/div>\n<div id=\"attachment_1874\" style=\"width: 190px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232033\/Untitled25.png\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-1874\" class=\"wp-image-1874\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232033\/Untitled25.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"180\" height=\"165\" \/><\/a><\/p>\n<p id=\"caption-attachment-1874\" class=\"wp-caption-text\">BAD<\/p>\n<\/div>\n<div id=\"attachment_1875\" style=\"width: 234px\" class=\"wp-caption aligncenter\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232208\/Untitled26.png\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-1875\" class=\"wp-image-1875\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232208\/Untitled26.png\" alt=\"triangular graph with 4 vertices and 6 edges. There is one vertex in the center of the triangle. Edges between A and D and A and C are highlighted.\" width=\"224\" height=\"206\" \/><\/a><\/p>\n<p id=\"caption-attachment-1875\" class=\"wp-caption-text\">OK<\/p>\n<\/div>\n<div>\n<p>We then add the last edge to complete the circuit: ACBDA with weight 25.<\/p>\n<div>\n<p>Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232257\/Untitled27.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1876 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232257\/Untitled27.png\" alt=\"Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23.\" width=\"180\" height=\"165\" \/><\/a><\/p>\n<p>While the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Your teacher\u2019s band, <em>Derivative Work<\/em>, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.<\/p>\n<div style=\"width: auto;\">\n<table style=\"width: 586px; height: 333px;\">\n<tbody>\n<tr>\n<td><\/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>374<\/td>\n<td>200<\/td>\n<td>223<\/td>\n<td>108<\/td>\n<td>178<\/td>\n<td>252<\/td>\n<td>285<\/td>\n<td>240<\/td>\n<td>356<\/td>\n<\/tr>\n<tr>\n<td>Astoria<\/td>\n<td>374<\/td>\n<td>&#8211;<\/td>\n<td>255<\/td>\n<td>166<\/td>\n<td>433<\/td>\n<td>199<\/td>\n<td>135<\/td>\n<td>95<\/td>\n<td>136<\/td>\n<td>17<\/td>\n<\/tr>\n<tr>\n<td>Bend<\/td>\n<td>200<\/td>\n<td>255<\/td>\n<td>&#8211;<\/td>\n<td>128<\/td>\n<td>277<\/td>\n<td>128<\/td>\n<td>180<\/td>\n<td>160<\/td>\n<td>131<\/td>\n<td>247<\/td>\n<\/tr>\n<tr>\n<td>Corvallis<\/td>\n<td>223<\/td>\n<td>166<\/td>\n<td>128<\/td>\n<td>&#8211;<\/td>\n<td>430<\/td>\n<td>47<\/td>\n<td>52<\/td>\n<td>84<\/td>\n<td>40<\/td>\n<td>155<\/td>\n<\/tr>\n<tr>\n<td>Crater Lake<\/td>\n<td>108<\/td>\n<td>433<\/td>\n<td>277<\/td>\n<td>430<\/td>\n<td>&#8211;<\/td>\n<td>453<\/td>\n<td>478<\/td>\n<td>344<\/td>\n<td>389<\/td>\n<td>423<\/td>\n<\/tr>\n<tr>\n<td>Eugene<\/td>\n<td>178<\/td>\n<td>199<\/td>\n<td>128<\/td>\n<td>47<\/td>\n<td>453<\/td>\n<td>&#8211;<\/td>\n<td>91<\/td>\n<td>110<\/td>\n<td>64<\/td>\n<td>181<\/td>\n<\/tr>\n<tr>\n<td>Newport<\/td>\n<td>252<\/td>\n<td>135<\/td>\n<td>180<\/td>\n<td>52<\/td>\n<td>478<\/td>\n<td>91<\/td>\n<td>&#8211;<\/td>\n<td>114<\/td>\n<td>83<\/td>\n<td>117<\/td>\n<\/tr>\n<tr>\n<td>Portland<\/td>\n<td>285<\/td>\n<td>95<\/td>\n<td>160<\/td>\n<td>84<\/td>\n<td>344<\/td>\n<td>110<\/td>\n<td>114<\/td>\n<td>&#8211;<\/td>\n<td>47<\/td>\n<td>78<\/td>\n<\/tr>\n<tr>\n<td>Salem<\/td>\n<td>240<\/td>\n<td>136<\/td>\n<td>131<\/td>\n<td>40<\/td>\n<td>389<\/td>\n<td>64<\/td>\n<td>83<\/td>\n<td>47<\/td>\n<td>&#8211;<\/td>\n<td>118<\/td>\n<\/tr>\n<tr>\n<td>Seaside<\/td>\n<td>356<\/td>\n<td>17<\/td>\n<td>247<\/td>\n<td>155<\/td>\n<td>423<\/td>\n<td>181<\/td>\n<td>117<\/td>\n<td>78<\/td>\n<td>118<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p style=\"text-align: center;\"><em>To see the entire table, scroll to the right<\/em><\/p>\n<p style=\"text-align: left;\">Using NNA with a large number of cities, you might find it helpful to mark off the cities as they\u2019re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:<\/p>\n<\/div>\n<div style=\"margin: auto;\">\n<p>Portland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47<\/p>\n<p>Salem to Corvallis\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40<\/p>\n<p>Corvallis to Eugene\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47<\/p>\n<p>Eugene to Newport\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 91<\/p>\n<p>Newport to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 117<\/p>\n<p>Seaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17<\/p>\n<p>Astoria to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 255<\/p>\n<p>Bend to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 200<\/p>\n<p>Ashland to Crater Lake\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 108<\/p>\n<p>Crater Lake to Portland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 344<\/p>\n<p>Total trip length:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1266 miles<\/p>\n<\/div>\n<div>\n<p style=\"text-align: left;\">Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3.<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232457\/Untitled28.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1877 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232457\/Untitled28.png\" alt=\"\" width=\"263\" height=\"188\" \/><\/a><\/p>\n<div>\n<p style=\"text-align: center;\">We start adding the shortest edges:<\/p>\n<p style=\"text-align: center;\">Seaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17 miles<\/p>\n<p style=\"text-align: center;\">Corvallis to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40 miles<\/p>\n<p style=\"text-align: center;\">Portland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\n<p style=\"text-align: center;\">Corvallis to Eugene\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232601\/Untitled29.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1878 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232601\/Untitled29.png\" alt=\"ring of dots with city names in problem as labels. edges between Seaside and Astoria, Eugene and Corvallis, Salem and Corvallis, and Salem and Portland.\" width=\"298\" height=\"228\" \/><\/a><\/p>\n<div>\n<p>The graph after adding these edges is shown to the right.\u00a0\u00a0 The next shortest edge is from Corvallis to Newport at 52 miles, but adding that edge would give Corvallis degree 3.<\/p>\n<p>&nbsp;<\/p>\n<p>Continuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree 2.<\/p>\n<p>Portland to Seaside \u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 78 miles<\/p>\n<p>Eugene to Newport\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 91 miles<\/p>\n<p>Portland to Astoria\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (reject \u2013 closes circuit)<\/p>\n<p>Ashland to Crater Lk\u00a0 108 miles<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232748\/Untitled30.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1879 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232748\/Untitled30.png\" alt=\"\" width=\"331\" height=\"253\" \/><\/a><\/p>\n<div>\n<p>The graph after adding these edges is shown to the right. At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree 2.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center;\">Newport to Astoria\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (reject \u2013 closes circuit)<\/p>\n<p style=\"text-align: center;\">Newport to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 180 miles<\/p>\n<p style=\"text-align: center;\">Bend to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 200 miles<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: left;\">At this point the only way to complete the circuit is to add:<\/p>\n<p style=\"text-align: left;\">Crater Lk to Astoria\u00a0\u00a0 433 miles. \u00a0The final circuit, written to start at Portland, is:<\/p>\n<p style=\"text-align: left;\">Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland. \u00a0Total trip length: 1241 miles.<\/p>\n<p style=\"text-align: left;\">While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in 1069 miles:<\/p>\n<p style=\"text-align: left;\">Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland<\/p>\n<p style=\"text-align: left;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232906\/Untitled31.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1880 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232906\/Untitled31.png\" alt=\"\" width=\"399\" height=\"305\" \/><\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p style=\"text-align: left;\">\n<\/div>\n<\/div>\n<\/div>\n<p>Watch the example of nearest neighbor algorithm for traveling from city to city using a table worked out in the video below.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-6\" title=\"Nearest Neighbor from a table\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/GFp-046PQx0?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>In the next video we use the same table, but use sorted edges to plan the trip.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-7\" title=\"Sorted Edges from a table\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/_gXyujMsrmw?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<div>\n<p>Find the circuit produced by the Sorted Edges algorithm using the graph below.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232952\/Untitled32.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1881\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16232952\/Untitled32.png\" alt=\"graph with 6 vertices and 14 edges. between B and E is 13, between E and G is 45, between G and F is 19, between F and C is 37, between c and A is 33 between A and B is 11. Between B and C is 25, between B and F is 23, between E and A is 14, between E and F is 15. Between G and B is 13, and between G and C is 36. Between G and A is 27.\" width=\"325\" height=\"187\" \/><\/a><\/p>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6565&#38;theme=oea&#38;iframe_resize_id=mom1\">https:\/\/www.myopenmath.com\/multiembedq.php?id=6565&amp;theme=oea&amp;iframe_resize_id=mom1<\/a><\/p>\n<\/div>\n<\/div>\n<h2>\u00a0Spanning Trees<\/h2>\n<p>A company requires reliable internet and phone connectivity between their five offices (named A, B, C, D, and E for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233317\/Untitled33.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1882 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233317\/Untitled33.png\" alt=\"graph with 5 vertices and 11 edges. between A and B is $4, between B and C is $10, between C and D is $7, between D and E is $13, between E and B is $6, between E and C is $11, between A and D is $6, between A and C is $8. Between B and E is $6, between B and D is $14.\" width=\"294\" height=\"176\" \/><\/a><\/p>\n<p>In this case, we don\u2019t need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Spanning Tree<\/h3>\n<\/div>\n<div>\n<p>A <strong>spanning tree<\/strong> is a connected graph using all vertices in which there are no circuits.<\/p>\n<p>In other words, there is a path from any vertex to any other vertex, but no circuits.<\/p>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Some examples of spanning trees are shown below. Notice there are no circuits in the trees, and it is fine to have vertices with degree higher than two.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233719\/Screen-Shot-2017-03-16-at-4.37.02-PM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1883\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233719\/Screen-Shot-2017-03-16-at-4.37.02-PM-300x43.png\" alt=\"Five triangular graphs where there are no Euler circuits, but every vertex has a path to every other vertex.\" width=\"467\" height=\"67\" \/><\/a><\/p>\n<p>Usually we have a starting graph to work from, like in the phone example above. In this case, we form our spanning tree by finding a <strong>subgraph<\/strong> \u2013 a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn\u2019t already exist.<\/p>\n<p>Of course, any random spanning tree isn\u2019t really what we want. We want the <strong>minimum cost spanning tree (MCST)<\/strong>.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Minimum Cost Spanning Tree (MCST)<\/h3>\n<\/div>\n<div>\n<p>The minimum cost spanning tree is the spanning tree with the smallest total edge weight.<\/p>\n<\/div>\n<\/div>\n<p>A nearest neighbor style approach doesn\u2019t make as much sense here since we don\u2019t need a circuit, so instead we will take an approach similar to sorted edges.<\/p>\n<div class=\"textbox\">\n<div>\n<h3>Kruskal\u2019s Algorithm<\/h3>\n<\/div>\n<div>\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<\/div>\n<p>&nbsp;<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>Using our phone line graph from above, begin adding edges:<\/p>\n<p>AB\u00a0\u00a0\u00a0\u00a0\u00a0 $4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK<\/p>\n<p>AE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK<\/p>\n<p>BE\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $6\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject \u2013 closes circuit ABEA<\/p>\n<p>DC\u00a0\u00a0\u00a0\u00a0\u00a0 $7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK<\/p>\n<p>AC\u00a0\u00a0\u00a0\u00a0\u00a0 $8\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 OK<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233916\/Untitled34.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1884\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16233916\/Untitled34.png\" alt=\"A graph with five vertices labeled A through E. A to B is $4, A to E is $5, B to E is $6, D to C is $7, A to C is $8. AB, AC, AE, and DC are shown in red.\" width=\"362\" height=\"219\" \/><\/a><\/p>\n<p>At this point we stop \u2013 every vertex is now connected, so we have formed a spanning tree with cost $24 thousand a year.<\/p>\n<\/div>\n<\/div>\n<p>Remarkably, Kruskal\u2019s algorithm is both optimal and efficient; we are guaranteed to always produce the optimal MCST.<\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<div>\n<p>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><\/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>374<\/td>\n<td>200<\/td>\n<td>223<\/td>\n<td>108<\/td>\n<td>178<\/td>\n<td>252<\/td>\n<td>285<\/td>\n<td>240<\/td>\n<td>356<\/td>\n<\/tr>\n<tr>\n<td>Astoria<\/td>\n<td>374<\/td>\n<td>&#8211;<\/td>\n<td>255<\/td>\n<td>166<\/td>\n<td>433<\/td>\n<td>199<\/td>\n<td>135<\/td>\n<td>95<\/td>\n<td>136<\/td>\n<td>17<\/td>\n<\/tr>\n<tr>\n<td>Bend<\/td>\n<td>200<\/td>\n<td>255<\/td>\n<td>&#8211;<\/td>\n<td>128<\/td>\n<td>277<\/td>\n<td>128<\/td>\n<td>180<\/td>\n<td>160<\/td>\n<td>131<\/td>\n<td>247<\/td>\n<\/tr>\n<tr>\n<td>Corvallis<\/td>\n<td>223<\/td>\n<td>166<\/td>\n<td>128<\/td>\n<td>&#8211;<\/td>\n<td>430<\/td>\n<td>47<\/td>\n<td>52<\/td>\n<td>84<\/td>\n<td>40<\/td>\n<td>155<\/td>\n<\/tr>\n<tr>\n<td>Crater Lake<\/td>\n<td>108<\/td>\n<td>433<\/td>\n<td>277<\/td>\n<td>430<\/td>\n<td>&#8211;<\/td>\n<td>453<\/td>\n<td>478<\/td>\n<td>344<\/td>\n<td>389<\/td>\n<td>423<\/td>\n<\/tr>\n<tr>\n<td>Eugene<\/td>\n<td>178<\/td>\n<td>199<\/td>\n<td>128<\/td>\n<td>47<\/td>\n<td>453<\/td>\n<td>&#8211;<\/td>\n<td>91<\/td>\n<td>110<\/td>\n<td>64<\/td>\n<td>181<\/td>\n<\/tr>\n<tr>\n<td>Newport<\/td>\n<td>252<\/td>\n<td>135<\/td>\n<td>180<\/td>\n<td>52<\/td>\n<td>478<\/td>\n<td>91<\/td>\n<td>&#8211;<\/td>\n<td>114<\/td>\n<td>83<\/td>\n<td>117<\/td>\n<\/tr>\n<tr>\n<td>Portland<\/td>\n<td>285<\/td>\n<td>95<\/td>\n<td>160<\/td>\n<td>84<\/td>\n<td>344<\/td>\n<td>110<\/td>\n<td>114<\/td>\n<td>&#8211;<\/td>\n<td>47<\/td>\n<td>78<\/td>\n<\/tr>\n<tr>\n<td>Salem<\/td>\n<td>240<\/td>\n<td>136<\/td>\n<td>131<\/td>\n<td>40<\/td>\n<td>389<\/td>\n<td>64<\/td>\n<td>83<\/td>\n<td>47<\/td>\n<td>&#8211;<\/td>\n<td>118<\/td>\n<\/tr>\n<tr>\n<td>Seaside<\/td>\n<td>356<\/td>\n<td>17<\/td>\n<td>247<\/td>\n<td>155<\/td>\n<td>423<\/td>\n<td>181<\/td>\n<td>117<\/td>\n<td>78<\/td>\n<td>118<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<div style=\"text-align: center;\"><em>To see the entire table, scroll to the right<\/em><\/div>\n<div style=\"text-align: center;\"><\/div>\n<div>\n<p>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=\"margin: auto;\">\n<p>Seaside to Astoria\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 17 milesCorvallis to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 40 miles<\/p>\n<p>Portland to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\n<p>Corvallis to Eugene\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 47 miles<\/p>\n<p>Corvallis to Newport\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 52 miles<\/p>\n<p>Salem to Eugene \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 reject \u2013 closes circuit<\/p>\n<p>Portland to Seaside\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 78 miles<\/p>\n<p style=\"text-align: center;\"><em>The graph up to this point is shown below.<\/em><\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234123\/Untitled35.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1885\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234123\/Untitled35.png\" alt=\"\" width=\"298\" height=\"228\" \/><\/a><\/p>\n<p style=\"text-align: left;\">Continuing,<\/p>\n<p>Newport to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Corvallis to Portland\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Eugene to Newport\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Portland to Astoria\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Ashland to Crater Lk\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 108 miles<\/p>\n<p>Eugene to Portland\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Newport to Portland\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Newport to Seaside\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<div>\n<p>Salem to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Bend to Eugene\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 128 miles<\/p>\n<p>Bend to Salem\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Astoria to Newport \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Salem to Astoria \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Corvallis to Seaside\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Portland to Bend\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Astoria to Corvallis\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 reject<\/p>\n<p>Eugene to Ashland\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 178 miles<\/p>\n<p>&nbsp;<\/p>\n<p>This connects the graph. The total length of cable to lay would be 695 miles.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234225\/Untitled36.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1886\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234225\/Untitled36.png\" alt=\"\" width=\"342\" height=\"260\" \/><\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p>Watch the example above worked out in the following video, without a table.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-8\" title=\"Kruskal&#39;s ex 1\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/gaXM0HNErc4?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>Now we present the same example, with a table in the following video.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-9\" title=\"Kruskal&#39;s from a table\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Pu2_2ftkwdo?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p>Find a minimum cost spanning tree on the graph below using Kruskal\u2019s algorithm.<\/p>\n<p><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234312\/Untitled37.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1887\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/03\/16234312\/Untitled37.png\" alt=\"graph with 6 vertices and 14 edges. between B and E is 13, between E and G is 45, between G and F is 19, between F and C is 37, between c and A is 33 between A and B is 11. Between B and C is 25, between B and F is 23, between E and A is 14, between E and F is 15. Between G and B is 13, and between G and C is 36. Between G and A is 27.\" width=\"309\" height=\"178\" \/><\/a><\/p>\n<p><a href=\"https:\/\/www.myopenmath.com\/multiembedq.php?id=6581&#38;theme=oea&#38;iframe_resize_id=mom5\">https:\/\/www.myopenmath.com\/multiembedq.php?id=6581&amp;theme=oea&amp;iframe_resize_id=mom5<\/a><\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"#_ftnref1\">[1]<\/a> There are some theorems that can be used in specific circumstances, such as Dirac\u2019s theorem, which says that a Hamiltonian circuit must exist on a graph with <em>n<\/em> vertices if each vertex has degree <em>n<\/em>\/2 or greater.<\/p>\n<\/div>\n\n\t\t\t <section class=\"citations-section\" role=\"contentinfo\">\n\t\t\t <h3>Candela Citations<\/h3>\n\t\t\t\t\t <div>\n\t\t\t\t\t\t <div id=\"citation-list-1860\">\n\t\t\t\t\t\t\t <div class=\"licensing\"><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Original<\/div><ul class=\"citation-list\"><li>Revision and Adaptation. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Shared previously<\/div><ul class=\"citation-list\"><li>Hamiltonian circuits . <strong>Authored by<\/strong>: LIPPMAN, DAVID. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/SjtVuw4-1Qo\">https:\/\/youtu.be\/SjtVuw4-1Qo<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>TSP by brute force . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/wDXQ6tWsJxw\">https:\/\/youtu.be\/wDXQ6tWsJxw<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Number of circuits in a complete graph . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/DwZw4t0qxuQ\">https:\/\/youtu.be\/DwZw4t0qxuQ<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Nearest Neighbor ex2 . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/3Eq36iqjGKI\">https:\/\/youtu.be\/3Eq36iqjGKI<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Sorted Edges ex 2 . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/QxF23w3DpQc\">https:\/\/youtu.be\/QxF23w3DpQc<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Kruskal&#039;s ex 1 . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/gaXM0HNErc4\">https:\/\/youtu.be\/gaXM0HNErc4<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Kruskal&#039;s from a table . <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/Pu2_2ftkwdo\">https:\/\/youtu.be\/Pu2_2ftkwdo<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><\/div>\n\t\t\t\t\t\t <\/div>\n\t\t\t\t\t <\/div>\n\t\t\t <\/section>","protected":false},"author":21,"menu_order":23,"template":"","meta":{"_candela_citation":"[{\"type\":\"cc\",\"description\":\"Hamiltonian circuits \",\"author\":\"LIPPMAN, DAVID\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/SjtVuw4-1Qo\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"TSP by brute force \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/wDXQ6tWsJxw\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Number of circuits in a complete graph \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/DwZw4t0qxuQ\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Nearest Neighbor ex2 \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/3Eq36iqjGKI\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Sorted Edges ex 2 \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/QxF23w3DpQc\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Kruskal\\'s ex 1 \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/gaXM0HNErc4\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Kruskal\\'s from a table \",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/Pu2_2ftkwdo\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","CANDELA_OUTCOMES_GUID":"80215870-7383-4d4b-857c-1cd4400fa939","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-1860","chapter","type-chapter","status-web-only","hentry"],"part":1193,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1860","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/users\/21"}],"version-history":[{"count":21,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1860\/revisions"}],"predecessor-version":[{"id":3975,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1860\/revisions\/3975"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/parts\/1193"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/1860\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/media?parent=1860"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapter-type?post=1860"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/contributor?post=1860"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/slcc-mathforliberalartscorequisite\/wp-json\/wp\/v2\/license?post=1860"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}