user_guide:tutorials:aut_of_graphs

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
user_guide:tutorials:aut_of_graphs [2019/01/25 09:38]
oroehrig ↷ Page moved from user_guide:aut_of_graphs to user_guide:tutorials:aut_of_graphs
user_guide:tutorials:aut_of_graphs [2019/02/11 23:09] (current)
Line 1: Line 1:
-====== Automorphisms of Graphs ====== +{{page>.:latest:@FILEID@}}
- +
- +
- +
-===== First Example: The graph of a square ===== +
-Let's look at the graph of a square. Since a square is a 2-cube, we can create the polytope and look at its graph: +
-<​code>​ +
-polytope > $c=cube(2);​ +
-polytope > $c->​GRAPH->​VISUAL;​ +
-</​code>​ +
-{{user_guide:​square.png?​200|}} +
- +
-To study the automorphisms of this graph, we create a ''​props::​Graph''​ object refering to the ''​C++''​ class named ''​Graph''​ (see the [[user_guide:​apps_graph|tutorial on graphs]] for more details): +
-<code> +
-polytope > $g=new props::​Graph($c->​GRAPH->​ADJACENCY);​ +
-</​code>​ +
-The picture of the graph shows that the node with label 0 is adjacent to the nodes 1 and 2, Node 1 is adjacent to 0 and 3, and so onFor the complete adjacency information you can print ''​$c->​GRAPH->​ADJACENCY''​ or just the props::Graph object ''​$g'':​ +
-<​code>​ +
-polytope > print rows_labeled($g);​ +
-0:1 2 +
-1:0 3 +
-2:0 3 +
-3:1 2 +
-</​code>​ +
-Now, we compute the generators of the automorphism group of this graph: +
-<​code>​ +
-polytope > $aut=automorphisms($g);​ +
-</​code>​ +
-In this case, the automorphism group has two generators:​ +
-<​code>​ +
-polytope > print $aut; +
-0 2 1 3 +
-1 0 3 2 +
-</​code>​ +
-Each generator is a permutation on the nodes. The first generator fixes the nodes 0 and 3, and exchanges the nodes 1 and 2, i.e., it describes the reflection along the diagonal through 0 and 3. The second generator is the reflection along the horizontal line. +
- +
-In order to be able to work with the group, we create a new Group object, which lives in the application ''​group'':​ +
-<​code>​ +
-polytope > $autgroup=new group::​Group(GENERATORS=>​$aut);​ +
-</​code>​ +
-Now we can ask for basic properties of the group, e.g., the number of elements: +
-<​code>​ +
-polytope > print $autgroup->​ORDER;​ +
-+
-</​code>​ +
-Sometimes, it is useful to know which elements of the group fix a specific set of indices, that is, we are interested in the subgroup which is the stabilizer of the given set. In the first case, we just fix the index 0: +
-<​code>​ +
-polytope > $s0=new Set<​Int>​(0);​ +
-polytope > $stab0=group::​stabilizer_of_set($autgroup,​$s0);​ +
-</​code>​ +
-We learn that the node 0 is only fixed by the permutation ''​0 2 1 3'':​ +
-<​code>​ +
-polytope > print $stab0->​ORDER;​ +
-+
-polytope > print $stab0->​GENERATORS;​ +
-0 2 1 3 +
-</​code>​ +
-In the second case, we look at the subgroup which leaves the set ''​{1,​2}''​ invariant:  +
-<​code>​ +
-polytope > $s12=new Set<​Int>​(1,​2);​ +
-polytope > $stab12=group::​stabilizer_of_set($autgroup,​$s12);​ +
-</​code>​ +
-Now, we obtain a group of order 4: +
-<​code>​ +
-polytope > print $stab12->​ORDER;​ +
-+
-polytope > print $stab12->​GENERATORS;​ +
-3 1 2 0 +
-0 2 1 3 +
-</​code>​ +
-Finally, we compute the orbits of the indices under the three different groups: +
-<​code>​ +
-polytope > print group::​compute_domain_orbits($stab0);​ +
-{0} +
-{1 2} +
-{3} +
- +
-polytope > print group::​compute_domain_orbits($stab12);​ +
-{0 3} +
-{1 2} +
- +
-polytope > print group::​compute_domain_orbits($autgroup);​ +
-{0 1 2 3} +
-</​code>​+
  
  • user_guide/tutorials/aut_of_graphs.txt
  • Last modified: 2019/02/11 23:09
  • (external edit)