{"id":450,"date":"2007-06-24T19:40:22","date_gmt":"2007-06-24T19:40:22","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/06\/24\/the-first-graph-theory-problem\/"},"modified":"2007-06-24T19:40:22","modified_gmt":"2007-06-24T19:40:22","slug":"the-first-graph-theory-problem","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/06\/24\/the-first-graph-theory-problem\/","title":{"rendered":"The First Graph Theory Problem"},"content":{"rendered":"

Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreir\u00f3s book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory<\/a> on friday, and I’ve been promising forever to write about it, I figured this is a good time.<\/p>\n

My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.<\/p>\n

Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
\nthe city, there were seven bridges connecting the parts of the city. Is it possible to
\ntake a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?<\/p>\n


\n\"seven-bridges.jpg\"<\/p>\n

Over to the right is a schematic map of Königsberg when Euler lived there. For Königsberg, you can show that it’s impossible, by exhaustively listing all paths. It’s a lot<\/em> of possible paths, but not so many as to make it effectively impossible. But there’s a better way of figuring it out. It’s a property of the
\nstructure<\/em> of the city and how the graphs connect different parts of the city. And that’s the key to the problem: analyzing the structure. And the structure is a graph.<\/p>\n

\"seven-graph.jpg\"<\/p>\n

For this problem, you can look at the city as a simple structure. Each land-mass – the two banks, and the two islands – can be viewed as points (vertices). Each of the bridges are lines (edges) connecting the points – like in the image to the right. The question becomes: given a collection of vertices connected by edges, when is it possible to cross every edge exactly once? If there’s a way to do it, then the path is called an Eulerian path<\/em>. If there’s a way to do it so that the Eulerian path ends at the same vertex as where it started, then the path is called an Eulerian cycle, and the graph is called an Eulerian graph. <\/p>\n

The answer to this problem is, as I said, in the structure of the graph.<\/p>\n

If we want an Eulerian path, then we can easily show that there is an
\nEulerian cycle if and only if the graph has the property that you can partition its edges into a collection of disjoint loops (cycles). Look at the graph of Königsberg above: you can form cycles with 1\/3 and 2\/4, or 3\/5\/6 and 2\/4, or 1\/2\/7\/6, or… But you can’t partition all of the edges into disjoint cycles.<\/p>\n

Studying graph structure using some combinatoric techniques, you can show the more general result about Eulerian paths: if every vertex in the graph has an even<\/em> number of edges, or it has exactly<\/em> two vertices with an odd number of edges, then
\nthe graph has an Eulerian path. Again, look at the example: there are three nodes with 3 edges, and one node with 5 edges. So there are 4 nodes with odd numbers of edges. Therefore, there is no way to make an Eulerian path through Königsberg.<\/p>\n

How many bridges would you need to add to make a graph with an Eulerian path? You need to make two of the four nodes have even numbers of edges. We can do that by adding one edge. For example, if you add an edge from A to D, then you have one node with 5 edges, one with three edges, and two with four edges.<\/p>\n","protected":false},"excerpt":{"rendered":"

Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreir\u00f3s […]<\/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-450","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7g","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/450","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=450"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/450\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=450"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}