This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong. ====== 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/release/3.6/aut_of_graphs.txt Last modified: 2019/11/15 22:01by 127.0.0.1