Consider a 4-cycle, G, with vertices V = {A; B; C; D}, and edges {A; B},

{B; C}, {C; D}, {D; A}. Note that you can have an isomorphism that maps G

to itself. Such a map is called an automorphism.

The most obvious automorphism of G maps A to A, B to B, C to C, and

D to D. This is called the identity map. But there are less trivial ones:

for example, let f map A to B, B to C, C to D, and D to A.

Extra Credit Exercise 1: Find all 8 automorphims of G.

Note that if you have two automorphisms, f and g, then f g (which just means ?rst do g then do f) is also an automorphism. For example, if f is the automorphism given above, (f f)(A) = f(f(A)) = f(B) = C, (f f)(B) =

f(f(B)) = f(C) = D, and so on. The automorphisms of G form a group

with this operation. Recall a group operation has an identity, (in this case, the

identity map given above), and inverses.

Extra Credit Exercise 2: What is the inverse of f? That is, of the eight

automorphisms you listed in the previous exercise which of them is a map g

such that f g is the identity map.

Extra Credit Exercise 3: Find two automorphisms of G, say g1 and g2 so

that g1 g2 6= g2 g1.

Extra Credit Exercise 4: Find two automorphism which generate all eight

automorphisms of G. Draw a Cayley graph of the automorphisms of G.

Extra Credit Exercise 5: Give a proof by induction that an in-order traversal of a binary search tree puts the things stored in the search tree in order

Subject | Mathematics |

Due By (Pacific Time) | 05/07/2013 10:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |