Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
user_guide:tutorials:aut_of_graphs [2019/01/28 17:40] – ↷ Links adapted because of a move operation oroehrig | user_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: | + | |
- | < | + | |
- | polytope > $c=cube(2); | + | |
- | polytope > $c-> | + | |
- | </ | + | |
- | {{user_guide: | + | |
- | + | ||
- | To study the automorphisms of this graph, we create a '' | + | |
- | <code> | + | |
- | polytope > $g=new props:: | + | |
- | </ | + | |
- | 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 '' | + | |
- | < | + | |
- | 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: | + | |
- | < | + | |
- | polytope > $aut=automorphisms($g); | + | |
- | </ | + | |
- | In this case, the automorphism group has two generators: | + | |
- | < | + | |
- | 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 '' | + | |
- | < | + | |
- | polytope > $autgroup=new group:: | + | |
- | </ | + | |
- | Now we can ask for basic properties of the group, e.g., the number of elements: | + | |
- | < | + | |
- | polytope > print $autgroup-> | + | |
- | 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: | + | |
- | < | + | |
- | polytope > $s0=new Set< | + | |
- | polytope > $stab0=group:: | + | |
- | </ | + | |
- | We learn that the node 0 is only fixed by the permutation '' | + | |
- | < | + | |
- | polytope > print $stab0-> | + | |
- | 2 | + | |
- | polytope > print $stab0-> | + | |
- | 0 2 1 3 | + | |
- | </ | + | |
- | In the second case, we look at the subgroup which leaves the set '' | + | |
- | < | + | |
- | polytope > $s12=new Set< | + | |
- | polytope > $stab12=group:: | + | |
- | </ | + | |
- | Now, we obtain a group of order 4: | + | |
- | < | + | |
- | polytope > print $stab12-> | + | |
- | 4 | + | |
- | polytope > print $stab12-> | + | |
- | 3 1 2 0 | + | |
- | 0 2 1 3 | + | |
- | </ | + | |
- | Finally, we compute the orbits of the indices under the three different groups: | + | |
- | < | + | |
- | polytope > print group:: | + | |
- | {0} | + | |
- | {1 2} | + | |
- | {3} | + | |
- | + | ||
- | polytope > print group:: | + | |
- | {0 3} | + | |
- | {1 2} | + | |
- | + | ||
- | polytope > print group:: | + | |
- | {0 1 2 3} | + | |
- | </ | + | |