user_guide:tutorials:aut_of_graphs

# Differences

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

 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) 2019/01/28 17:40 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:aut_of_graphs to user_guide:tutorials:aut_of_graphs2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:aut_of_graphs to user_guide:aut_of_graphs2017/06/13 11:22 oroehrig added some formatting to enable automated tests2014/01/03 15:45 external edit2011/12/06 17:06 herr [First Example: The graph of a square] 2011/12/06 16:58 herr finished first example for automorphism tutorial2011/12/06 16:05 herr created 2019/01/28 17:40 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:38 oroehrig ↷ Page moved from user_guide:aut_of_graphs to user_guide:tutorials:aut_of_graphs2019/01/25 09:27 oroehrig ↷ Links adapted because of a move operation2019/01/25 09:27 oroehrig ↷ Page moved from tutorial:aut_of_graphs to user_guide:aut_of_graphs2017/06/13 11:22 oroehrig added some formatting to enable automated tests2014/01/03 15:45 external edit2011/12/06 17:06 herr [First Example: The graph of a square] 2011/12/06 16:58 herr finished first example for automorphism tutorial2011/12/06 16:05 herr created 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;​ + - ​ + - {{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): + - + - polytope > $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'':​ + - <​code>​ + - polytope > 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: + - <​code>​ + - polytope >$aut=automorphisms($g);​ + - ​ + - In this case, the automorphism group has two generators:​ + - <​code>​ + - polytope > 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'':​ + - <​code>​ + - polytope > $autgroup=new group::​Group(GENERATORS=>​$aut);​ + - ​ + - Now we can ask for basic properties of the group, e.g., the number of elements: + - <​code>​ + - polytope > 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: + - <​code>​ + - polytope >$s0=new Set<​Int>​(0);​ + - polytope > $stab0=group::​stabilizer_of_set($autgroup,​$s0);​ + - ​ + - We learn that the node 0 is only fixed by the permutation ''​0 2 1 3'':​ + - <​code>​ + - polytope > print$stab0->​ORDER;​ + - 2 + - polytope > print $stab0->​GENERATORS;​ + - 0 2 1 3 + - ​ + - 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);​ + - ​ + - Now, we obtain a group of order 4: + - <​code>​ + - polytope > print$stab12->​ORDER;​ + - 4 + - polytope > print $stab12->​GENERATORS;​ + - 3 1 2 0 + - 0 2 1 3 + - ​ + - 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} + - ​ +
• user_guide/tutorials/aut_of_graphs.txt