user_guide:tutorials:aut_of_graphs

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
user_guide:tutorials:aut_of_graphs [2019/01/28 17:40] – ↷ Links adapted because of a move operation oroehriguser_guide:tutorials:aut_of_graphs [2019/02/11 23:09] (current) – external edit 127.0.0.1
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; +
-</code> +
-{{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:tutorials:apps_graph|tutorial on graphs]] for more details): +
-<code> +
-polytope > $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 onFor 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 +
-</code> +
-Now, we compute the generators of the automorphism group of this graph: +
-<code> +
-polytope > $aut=automorphisms($g); +
-</code> +
-In this case, the automorphism group has two generators: +
-<code> +
-polytope > 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> +
-polytope > $autgroup=new group::Group(GENERATORS=>$aut); +
-</code> +
-Now we can ask for basic properties of the group, e.g., the number of elements: +
-<code> +
-polytope > print $autgroup->ORDER; +
-+
-</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> +
-polytope > $s0=new Set<Int>(0); +
-polytope > $stab0=group::stabilizer_of_set($autgroup,$s0); +
-</code> +
-We learn that the node 0 is only fixed by the permutation ''0 2 1 3'': +
-<code> +
-polytope > print $stab0->ORDER; +
-+
-polytope > print $stab0->GENERATORS; +
-0 2 1 3 +
-</code> +
-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); +
-</code> +
-Now, we obtain a group of order 4: +
-<code> +
-polytope > print $stab12->ORDER; +
-+
-polytope > print $stab12->GENERATORS; +
-3 1 2 0 +
-0 2 1 3 +
-</code> +
-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} +
-</code>+
  
  • user_guide/tutorials/aut_of_graphs.1548697236.txt.gz
  • Last modified: 2019/01/28 17:40
  • by oroehrig