{"id":902,"date":"2022-04-07T12:43:27","date_gmt":"2022-04-07T12:43:27","guid":{"rendered":"https:\/\/highclasswriters.com\/blog\/?p=902"},"modified":"2022-04-07T12:43:28","modified_gmt":"2022-04-07T12:43:28","slug":"hamilton-circuit-minimal-spanning-tree","status":"publish","type":"post","link":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/","title":{"rendered":"Hamilton Circuit\/minimal spanning tree"},"content":{"rendered":"\n

Knowledge<\/strong><\/h1>\n\n\n\n

After completing this assignment you will understand:<\/p>\n\n\n\n

1. The difference between a Hamilton circuit and minimal spanning tree.<\/p>\n\n\n\n

2. How different paths or circuits can result in lower costs of travel.<\/p>\n\n\n\n

Skills<\/strong><\/h1>\n\n\n\n

After completing this assignment you will be able to:<\/p>\n\n\n\n

1. Find a Hamilton circuit using the Nearest Neighbor Algorithm.<\/p>\n\n\n\n

2. Create a graph given 5 cities to find a minimal spanning tree.<\/p>\n\n\n\n

Please show ALL work in order to receive full credit. (20 points)<\/strong><\/p>\n\n\n\n

Answers only will receive 1 point.<\/strong><\/p>\n\n\n\n

There are two parts to this project.  Each one worth 10 points.<\/h1>\n\n\n\n

1.  Darren works for US Paper Products in New York City.  His company is investigating locations for a new factory that will produce a line of disposable clothing.  The cities Darren needs to visit are Atlanta, Dallas, Philadelphia, and Washington, DC.  The one-way flight prices between these cities are given in the table below.<\/p>\n\n\n\n

Cities and Cost of Travel<\/strong><\/td><\/tr>
<\/td>Atlanta<\/strong><\/td>Dallas<\/strong><\/td>New York<\/strong><\/td>Philadelphia<\/strong><\/td>Washington<\/strong><\/td><\/tr>
Atlanta<\/strong><\/td>*<\/td>$182<\/td>$197<\/td>$159<\/td>$180<\/td><\/tr>
Dallas<\/strong><\/td>$182<\/td>*<\/td>$115<\/td>$115<\/td>$110<\/td><\/tr>
New York<\/strong><\/td>$197<\/td>$115<\/td>*<\/td>$55<\/td>$156<\/td><\/tr>
Philadelphia<\/strong><\/td>$159<\/td>$115<\/td>$55<\/td>*<\/td>$205<\/td><\/tr>
Washington<\/strong><\/td>$180<\/td>$110<\/td>$156<\/td>$205<\/td>*<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

  a.)  Represent the traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges.<\/p>\n\n\n\n

b.) Use the nearest neighbor method to approximate the optimal route for Darren to travel to each city and return to New York City.  Give the cost of the route determined.<\/p>\n\n\n\n

c.)  Create your own algorithm and see if you can find a route that costs less than the route you calculated in part b.<\/p>\n\n\n\n

2. Select 5 students in your class so that no two have the same hometown.  Use the internet to find the distances between each pair of towns (MapQuest is a good source to check). <\/p>\n\n\n\n

a.) Draw a complete, weighted graph that represents the five towns and the distances between them. <\/p>\n\n\n\n

b.) Use Kruskal\u2019s algorithm to determine the minimum cost spanning tree for the complete, weighted graph in part a.<\/p>\n\n\n\n

c.) Determine the total distance one would travel along the minimum-cost spanning tree found in part b.<\/p>\n","protected":false},"excerpt":{"rendered":"

Knowledge After completing this assignment you will understand: 1. The difference between a Hamilton circuit and minimal spanning tree. 2. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[1],"tags":[],"class_list":["post-902","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"acf":[],"yoast_head":"\nHamilton Circuit\/minimal spanning tree - Highclasswriters<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hamilton Circuit\/minimal spanning tree - Highclasswriters\" \/>\n<meta property=\"og:description\" content=\"Knowledge After completing this assignment you will understand: 1. The difference between a Hamilton circuit and minimal spanning tree. 2. […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/\" \/>\n<meta property=\"og:site_name\" content=\"Highclasswriters\" \/>\n<meta property=\"article:published_time\" content=\"2022-04-07T12:43:27+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-04-07T12:43:28+00:00\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/\",\"url\":\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/\",\"name\":\"Hamilton Circuit\/minimal spanning tree - Highclasswriters\",\"isPartOf\":{\"@id\":\"https:\/\/highclasswriters.com\/blog\/#website\"},\"datePublished\":\"2022-04-07T12:43:27+00:00\",\"dateModified\":\"2022-04-07T12:43:28+00:00\",\"author\":{\"@id\":\"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/06412d8249aafcb0c75ea9958c98aaae\"},\"breadcrumb\":{\"@id\":\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/highclasswriters.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Hamilton Circuit\/minimal spanning tree\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/highclasswriters.com\/blog\/#website\",\"url\":\"https:\/\/highclasswriters.com\/blog\/\",\"name\":\"Highclasswriters\",\"description\":\"Essay Writing Service\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/highclasswriters.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/06412d8249aafcb0c75ea9958c98aaae\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/99ccb26aea1053c4c33c76cde1eee45f1ec58485d03e72c412d111c386e42174?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/99ccb26aea1053c4c33c76cde1eee45f1ec58485d03e72c412d111c386e42174?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"sameAs\":[\"https:\/\/highclasswriters.com\/blog\"],\"url\":\"https:\/\/highclasswriters.com\/blog\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hamilton Circuit\/minimal spanning tree - Highclasswriters","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/","og_locale":"en_US","og_type":"article","og_title":"Hamilton Circuit\/minimal spanning tree - Highclasswriters","og_description":"Knowledge After completing this assignment you will understand: 1. The difference between a Hamilton circuit and minimal spanning tree. 2. […]","og_url":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/","og_site_name":"Highclasswriters","article_published_time":"2022-04-07T12:43:27+00:00","article_modified_time":"2022-04-07T12:43:28+00:00","author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/","url":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/","name":"Hamilton Circuit\/minimal spanning tree - Highclasswriters","isPartOf":{"@id":"https:\/\/highclasswriters.com\/blog\/#website"},"datePublished":"2022-04-07T12:43:27+00:00","dateModified":"2022-04-07T12:43:28+00:00","author":{"@id":"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/06412d8249aafcb0c75ea9958c98aaae"},"breadcrumb":{"@id":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/highclasswriters.com\/blog\/hamilton-circuit-minimal-spanning-tree\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/highclasswriters.com\/blog\/"},{"@type":"ListItem","position":2,"name":"Hamilton Circuit\/minimal spanning tree"}]},{"@type":"WebSite","@id":"https:\/\/highclasswriters.com\/blog\/#website","url":"https:\/\/highclasswriters.com\/blog\/","name":"Highclasswriters","description":"Essay Writing Service","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/highclasswriters.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/06412d8249aafcb0c75ea9958c98aaae","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/highclasswriters.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/99ccb26aea1053c4c33c76cde1eee45f1ec58485d03e72c412d111c386e42174?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/99ccb26aea1053c4c33c76cde1eee45f1ec58485d03e72c412d111c386e42174?s=96&d=mm&r=g","caption":"admin"},"sameAs":["https:\/\/highclasswriters.com\/blog"],"url":"https:\/\/highclasswriters.com\/blog\/author\/admin\/"}]}},"_links":{"self":[{"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/posts\/902","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/comments?post=902"}],"version-history":[{"count":1,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/posts\/902\/revisions"}],"predecessor-version":[{"id":903,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/posts\/902\/revisions\/903"}],"wp:attachment":[{"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/media?parent=902"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/categories?post=902"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/highclasswriters.com\/blog\/wp-json\/wp\/v2\/tags?post=902"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}