{"id":461,"date":"2007-07-04T14:10:34","date_gmt":"2007-07-04T14:10:34","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/04\/graph-decomposition-and-turning-cycles\/"},"modified":"2007-07-04T14:10:34","modified_gmt":"2007-07-04T14:10:34","slug":"graph-decomposition-and-turning-cycles","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/04\/graph-decomposition-and-turning-cycles\/","title":{"rendered":"Graph Decomposition and Turning Cycles"},"content":{"rendered":"

One thing that we often want to do is break a graph into pieces in a way that preserves
\nthe structural relations between the vertices in any part. Doing that is called
\n*decomposing* the graph. Decomposition is a useful technique because many ways
\nof studying the structure of a graph, and many algorithms over graphs can work by
\ndecomposing the graph, studying the elements of the decomposition, and then combining
\nthe results.
\nTo be formal: a graph G can be decomposed into a set of subgraphs {G1<\/sub>, G2<\/sub>, G3<\/sub>, …}, where the edges of each of the Gi<\/sub>s are
\n*disjoint* subsets of the edges of G. So in a decomposition of G, *vertices* can be shared between elements of the decomposition, but *edges* cannot.<\/p>\n


\nSo, for example, here is K5<\/sub>, and a decomposition of it into three subgraphs. To make it clearer, the original graph has its edges colored to match the colors of the vertices in the subgraph it belongs to in the decomposition.
\n\"k5-decomp.jpg\"
\nWe can prove that any complete graph K2n+1<\/sub> can be decomposed into n hamiltonian cycles. (As a reminder, a hamiltonion cycle is a path through a graph with the same first and last vertex, and which visits every other vertex in the graph exactly once.)
\n\"cycle-turning.jpg\"
\nThe proof
\nis another turning proof. I’ll just show you the basic structure of the hamiltonian cycle that we’ll use, with K7<\/sub> (2n+1 for n=3) as an example. You can see the cycle nice and clearly. If you turn the graph so that x is matched with 1, you get another cycle; if you turn again so that x is matched with 2, you’ll get a third cycle. If you turn again, you’ll get x matched with three – which is a repeat of the cycle we started with. In any complete graph with 2n+1 vertices, after n turns, you’ll get a repeat. Further, we know that the complete graph for K2n+1<\/sub> has (2n+1) choose 2 – or n×(2n+1) edges. Each hamiltonion cycle has 2n+1 edges, so there *can’t* be more than N of them.
\nUsing a simple variation of this, we can also show that any complete graph K2n<\/sub>
\nhas N hamiltonian *paths*. (A hamiltonian path is a path that touches each vertex once, but it doesn’t have to be a cycle.) The way we can prove that is really clever. Take the turning proof for 2n+1 and the hamiltonian cycles – and *delete* node x. Then it will produce N hamiltonian paths on a complete graph with 2n vertices.<\/p>\n","protected":false},"excerpt":{"rendered":"

One thing that we often want to do is break a graph into pieces in a way that preserves the structural relations between the vertices in any part. Doing that is called *decomposing* the graph. Decomposition is a useful technique because many ways of studying the structure of a graph, and many algorithms over graphs […]<\/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-461","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7r","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/461","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=461"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/461\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}