{"id":47,"date":"2016-11-02T15:42:16","date_gmt":"2016-11-02T15:42:16","guid":{"rendered":"http:\/\/keithmellinger.com\/magma\/?page_id=47"},"modified":"2016-11-03T19:55:15","modified_gmt":"2016-11-03T19:55:15","slug":"graph-theory","status":"publish","type":"page","link":"https:\/\/keithmellinger.com\/magma\/graph-theory\/","title":{"rendered":"Graph Theory"},"content":{"rendered":"

Graphs can, of course, be used to model all sorts of problems in various areas of discrete mathematics. So it\u2019s worthwhile to look at what Magma<\/em> can do with graphs. Let\u2019s suppose you just wanted to create a small graph with just a few edges. You can do this by telling Magma<\/em> the order (number of vertices) and then listing the edges as unordered pairs:<\/p>\n

> G := Graph<5 | {1,3},{1,4},{1,5},{2,3},{2,4},{2,5}>;<\/code>
\n > G;<\/code>
\n Graph<\/code>
\n Vertex\u00a0 Neighbours<\/code>
\n 1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3 4 5 ;<\/code>
\n 2\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 3 4 5 ;<\/code>
\n 3\u00a0 \u00a0\u00a0\u00a0\u00a0\u00a01 2 ;<\/code>
\n 4\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1 2 ;<\/code>
\n 5\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 1 2 ;<\/code><\/p>\n

Once we have the graph, we can ask Magma for properties of it:<\/p>\n

> IsBipartite(G);<\/code>
\n true<\/code>
\n > VertexConnectivity(G);<\/code>
\n 2<\/code>
\n > ChromaticNumber(G);<\/code>
\n 2<\/code>
\n > IsPlanar(G);<\/code>
\n true<\/code><\/p>\n

Let\u2019s check if Magma knows Kuratowski\u2019s Theorem for planar graphs. Here I\u2019ll define G<\/em> to be the complete bipartite graph K<\/em>3,3<\/sub> and then ask if the graph is planar. Magma<\/em> can even try to solve problems which are NP-hard (such as the clique number for a graph), although for larger graphs it might take a while.<\/p>\n

> G := Graph<6 | {1,4},{1,5},{1,6},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6}>;<\/code>
\n > IsPlanar(G);<\/code>
\n false<\/code>
\n > CliqueNumber(G);<\/code>
\n 2<\/code><\/p>\n

Exercise:<\/em><\/strong> Define G to be the Peterson Graph on 10 vertices. You might first draw a picture of the Peterson Graph and then figure out how to list the edges (there are 10 vertices). Google it if you don’t know what it looks like.<\/p>\n

    \n
  1. Determine its chromatic number.<\/li>\n
  2. Determine whether or not the graph is planar.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Graphs can, of course, be used to model all sorts of problems in various areas of discrete mathematics. So it\u2019s worthwhile to look at what Magma can do with graphs. Let\u2019s suppose you just wanted to create a small graph with just a few edges. You can do this by telling Magma the order (number … Continue reading Graph Theory<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-47","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/pages\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/comments?post=47"}],"version-history":[{"count":3,"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/pages\/47\/revisions"}],"predecessor-version":[{"id":61,"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/pages\/47\/revisions\/61"}],"wp:attachment":[{"href":"https:\/\/keithmellinger.com\/magma\/wp-json\/wp\/v2\/media?parent=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}