user_guide:tutorials:latest:aut_of_graphs

Differences

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

Link to this comparison view

user_guide:tutorials:latest:aut_of_graphs [2020/01/22 09:02] (current)
Line 1: Line 1:
 +====== Automorphisms of Graphs ======
 +
 +===== 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 perl>
 +> $c=cube(2);
 +> $c->​GRAPH->​VISUAL;​
 +</​code>​
 +{{:​tutorial:​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 [[apps_graph|tutorial on graphs]] for more details):
 +
 +<code perl>
 +> $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 on. For the complete adjacency information you can print ''​$c->​GRAPH->​ADJACENCY''​ or just the props::​Graph object ''​$g'':​
 +
 +<code perl>
 +> 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 (see the [[apps_group|tutorial on groups]] for more info):
 +
 +<code perl>
 +> $aut=automorphisms($g);​
 +</​code>​
 +In this case, the automorphism group has two generators:
 +
 +<code perl>
 +> 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 perl>
 +> $action = new group::​PermutationAction(GENERATORS => $aut);
 +> $autgroup = new group::​Group(PERMUTATION_ACTION => $action);
 +</​code>​
 +Now we can ask for basic properties of the group, e.g., the number of elements:
 +
 +<code perl>
 +> print $autgroup->​ORDER;​
 +8
 +</​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 perl>
 +> $s0=new Set<​Int>​(0);​
 +> $stab0=group::​stabilizer_of_set($action,​$s0);​
 +</​code>​
 +We learn that the node 0 is only fixed by the permutation ''​0 2 1 3'':​
 +
 +<code perl>
 +> print $stab0->​ORDER;​
 +2
 +> print $stab0->​PERMUTATION_ACTION->​GENERATORS;​
 +0 2 1 3
 +</​code>​
 +In the second case, we look at the subgroup which leaves the set ''​{1,​2}''​ invariant:
 +
 +<code perl>
 +> $s12=new Set<​Int>​(1,​2);​
 +> $stab12=group::​stabilizer_of_set($action,​$s12);​
 +</​code>​
 +Now, we obtain a group of order 4:
 +
 +<code perl>
 +> print $stab12->​ORDER;​
 +4
 +> print $stab12->​PERMUTATION_ACTION->​GENERATORS;​
 +3 1 2 0
 +0 2 1 3
 +</​code>​
 +Finally, we compute the orbits of the indices under the three different groups:
 +
 +<code perl>
 +> print $stab0->​PERMUTATION_ACTION->​ORBITS;​
 +{0}
 +{1 2}
 +{3}
 +> print $stab12->​PERMUTATION_ACTION->​ORBITS;​
 +{0 3}
 +{1 2}
 +> print $autgroup->​PERMUTATION_ACTION->​ORBITS;​
 +{0 1 2 3}
 +</​code>​
  
  • user_guide/tutorials/latest/aut_of_graphs.txt
  • Last modified: 2020/01/22 09:02
  • (external edit)