# Differences

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

— |
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> | ||