{"id":480,"date":"2007-08-01T11:07:32","date_gmt":"2007-08-01T11:07:32","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/08\/01\/weighted-graphs-and-the-minimum-spanning-tree\/"},"modified":"2007-08-01T11:07:32","modified_gmt":"2007-08-01T11:07:32","slug":"weighted-graphs-and-the-minimum-spanning-tree","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/08\/01\/weighted-graphs-and-the-minimum-spanning-tree\/","title":{"rendered":"Weighted Graphs and the Minimum Spanning Tree"},"content":{"rendered":"<p> Moving on from simple graphs, one of the things you can do to make things more interesting<br \/>\nis to associate numeric values with the edges, called the <em>weights<\/em> of those edges. This variation<br \/>\nof a graph is called a <em>weighted graph<\/em>.<\/p>\n<p> Weighted graphs are extremely useful buggers: many real-world optimization problems ultimately<br \/>\nreduce to some kind of weighted graph problem. A few examples include:<\/p>\n<ul>\n<li> The traveling salesman problem (TSP): given a set of cities, and information about travel-times<br \/>\nbetween pairs of cities, find the shortest route that visits all cities. This is actually an<br \/>\nincredibly commonly used problem; for example, in large data centers which manage backups,<br \/>\na set of backup-restore requests is served by computing the seek time between pairs<br \/>\nof requests (where seek time includes finding the correct tape, loading it into a drive, and<br \/>\nscanning to the correct point on tape), and then finding the optimum order in which to fulfill<br \/>\nthe requests by using a TSP algorithm <\/li>\n<li> Shortest path problem: a subset of the TSP; given a set of cities and information about<br \/>\ntravel-time between cities with direct transportation routes, find the shortest path between<br \/>\ntwo cities.<\/li>\n<li> The minimum spanning tree problem: given a weighted graph, find the spanning tree<br \/>\nwith minimum total edge-weight. Airlines use minimum spanning trees to work out their basic<br \/>\nroute system: flights between hubs are low-cost; other flights have varying prices depending on how many people fly them, what airplanes the airports can support, fuel transport costs, etc. The best<br \/>\nset of routes is the minimum spanning tree.<\/li>\n<\/ul>\n<p><!--more--><\/p>\n<p> Formally, a weighted graph is defined by a triple: (V, E, W), where:<\/p>\n<ul>\n<li> V is a set of vertices;<\/li>\n<li> E is a set of edges {v,w} where v,w&isin;V.<\/li>\n<li> W is a map from edges to numbers. (Depending on the specifics of a problem,<br \/>\nthe numbers might be restricted to positive numbers, natural numbers,<br \/>\nintegers, &#8230;)<\/li>\n<\/ul>\n<p> For today, we&#8217;ll look at the last of those in a bit more detail: finding the minimum spanning tree. This is one of the problems that constantly comes up in infrastructure design &#8211; from building layouts, to<br \/>\nnetwork structure to warehouse location. One great example of the use of this is in telecommunications. When AT&amp;T and Sprint were laying fiber optic cable to replace their copper-wire backbone, they<br \/>\ntook their primary routing stations, and arranged them in a graph. Then they worked out the cost of<br \/>\nconnecting each pair of routing stations by fiber, and applied those costs as edge-weights. Then they<br \/>\ncomputed the <em>minimum spanning tree<\/em> of the resulting graph &#8211; and that defined the least-expensive<br \/>\nway to lay the fiber for a new backbone.<\/p>\n<p> So let&#8217;s start by making the definition of the minimum spanning tree problem more precise.<\/p>\n<ol>\n<li> Suppose we have a simple graph, G=(V,E). A <em>spanning tree<\/em> S<sub>G<\/sub>= (V,E&#8217;) is a subtree (acyclic subgraph) of G, where E&#8217;&sube;E.<\/li>\n<li> If G is a weighted graph G=(V,E,W), then the <em>weight<\/em> of G = &Sigma;<sub>e&isin;E<\/sub>W(e) &#8211; that is, the sum of the weights of all of the edges in the graph.<\/li>\n<li> If G is a weighted graph, then the minimum spanning tree Span(G) is the spanning tree over<br \/>\nG with minimum weight.<\/li>\n<\/ol>\n<p> Given that just about every interesting graph problem that we&#8217;ve seen has turned out to be NP-complete, you might expect finding a minimum spanning tree to be NP-complete as well. But graphs are often counterintuitive: things that seem like they should be simple turn out to be very difficult; things that look like they&#8217;ll be difficult sometimes turn out to be simple. In fact, there&#8217;s a very simple algorithm which is O(n lg n) where n is the number of edges.<\/p>\n<p> It&#8217;s called Kruskal&#8217;s algorithm. And it&#8217;s a really beautiful algorithm &#8211; an extraordinarily clear,<br \/>\nsimple, easy way of solving the problem. It&#8217;s based on what&#8217;s known as a <em>greedy<\/em> approach. In a<br \/>\ngreedy approach, you aggressively grab the thing that looks best, try it out, and see if it fits.<\/p>\n<p> In Kruskal&#8217;s algorithm, you greedily grab edges &#8211; you always grab the lowest weight edge, and see if it<br \/>\nhelps build a spanning tree; if so, you add it, if not you discard it; and you keep doing that until<br \/>\nyou have the spanning tree. (From that description, you might think that it&#8217;s really O(N) in the number of  edges &#8211; because you consider each edge once. But the edges have to be in sorted order, and sorting the edges is O(N lg N).)<\/p>\n<p> So here&#8217;s the algorithm more precisely:<\/p>\n<pre>\nFindMST(G=(V,E,W))\nlet Result = a set of trees, each consisting of one node from G\nlet SortedEdges = sort(E,W)\nfor each MinEdge in SortedEdges:\nif MinEdge connects two disconnected trees in Result:\nmerge the trees in Result by adding MinEdge\nelse:\ndiscard MinEdge\nend if\nend for\n<\/pre>\n<p> Let&#8217;s walk through an example. Here&#8217;s a graph with weighted edges:<\/p>\n<p><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" alt=\"mst-initial-graph.png\" src=\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_227.png?resize=211%2C240\" width=\"211\" height=\"240\" \/><\/p>\n<p> Now we&#8217;ll go through Kruskal&#8217;s algorithm to generate the MST:<\/p>\n<p><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" alt=\"mst-merges.png\" src=\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_228.png?resize=324%2C729\" width=\"324\" height=\"729\" \/><\/p>\n<p> So the final weight of the minimum spanning tree for this graph is 31.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Moving on from simple graphs, one of the things you can do to make things more interesting is to associate numeric values with the edges, called the weights of those edges. This variation of a graph is called a weighted graph. Weighted graphs are extremely useful buggers: many real-world optimization problems ultimately reduce to some [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-480","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7K","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/480","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=480"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/480\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=480"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=480"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=480"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}