user_guide:tutorials:latest:aut_of_graphs

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