CSC 482B/582B Fall 2016 Assignment #1 Part C: Written questions

Due date for on-time submission: beginning of class on Wed. Sept. 28, 2016 [40 points]

Instructions for all assignments:

1. Draw boxes for your marks on the top of the first page of your submission. Place a 0 in the corresponding box for any questions you omit. For this assignment:

   Question	1	2	3	4
   Marks	0	0	0	0

2. Questions must be submitted in order.
3. Copying on an assignment will result in a mark of 0 for that assignment both for the person copying and also for the student who allowed their work to be copied and as per the university policy, could also result in failure in the course. Copying solutions from the web or other resources is also considered to be plagiarism and will result in a mark of 0 for that assignment.

`
1. For this question, you should work through the pseudocode by hand (you do not have to write a program). Enumerate all perfect matchings of G using the following backtracking approach:
   FindMatch(G)
   If G has no vertices, output the matching selected.
   Choose a vertex v of G of minimum degree. If there is more than one choice for v, choose a vertex whose label is minimized.
   Process the neighbours of v in numerical order according to the labels. For each neighbour u of vertex v of G do
   
   1. Add (u,v) to the matching.
   2. FindMatch(G-{u,v})
   3. Remove (u,v) from the matching.

   (a) [8] Show the computation tree resulting from using this approach on G.

   

   At each branch of the tree, draw a picture of G with the edges selected so far coloured with a red pen.

   Revision on Sept. 20: if you prefer, you can just show the computation tree, and instead of drawing pictures of the graph, label the edges with the edges of the graph that are added to the matching being constructed.

   (b) [4] On the Question 1 worksheet (click here to get it), show the perfect matchings listed in the order they are output by the algorithm. Print as many copies of the worksheet as you need.

2. [8] Two matchings are equivalent in G if there is some automorphism of G that preserves the matching edges. On the Question 2 worksheet (click here to get it), reorder the matchings so that the ones in the same equivalence class appear consecutively. Print as many copies of the worksheet as you need. Within an equivalence class, order them consecutively according to the lexicographic order with respect to the list of the edges of the matching given in sorted order.
   When you list the edges of one matching as
   (u1, v1), (u2, v2), (u3, v3), (u4, v4), (u5, v5)
   then having it sorted means that
   u1 < v1, u2 < v2, u3 < v3, u4 < v4, and u5 < v5.
   Having the edges sorted also means that
   u1 < u2 < u3 < u4 < u5.
   The sequence of integers in this case for the lexicographic comparison is:
   u1, v1, u2, v2, u3, v3, u4, v4, u5, v5.

   For each equivalence class: explain why they are equivalent by giving the automorphisms for mapping one to another. For example, if you have two matchings A and B, which automorphism maps A to B and also B to A. For the different equivalence classes, give me an explanation as to why the matchings are not equivalent to each other (based on their structural information and not just on the lack of an automorphism).

3. Consider this rotation system:
   

   0: 1 4
   1: 0 2 3
   2: 1 5 3
   3: 1 2 4
   4: 0 3
   5: 2 6 7
   6: 5 7
   7: 5 6
   

   (a) [5] Use the face walking algorithm described in class to walk all the faces of this embedding.
   (b) [2] What is the genus of the embedding and what surface does this correspond to?
   (c) [3] Draw a nice picture of this embedding.

4. [10] Apply clockwise BFS to label the vertices of this picture of the dodecahedron using root r, first child f and direction clockwise.

   

   You can click here to get a worksheet with a picture of this graph.