CSC 482/582: Fall 2016 Assignment #4
Due at the beginning of class, Fri. Dec. 2, 2016

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:
    Question12345
    Marks 0 0 0 0 0
  2. Questions must be submitted in order.
  3. Written submissions can be handed in up to 4 days late with a 10% penalty for each day past the deadline. If you want to submit your written work on a day that we do not have class, please write the day and time submitted on your first page and slip it under my office door (ECS 552).
  1. Consider the following graph:

    Click here to get a worksheet for drawing your solutions.

    (a) [10] Perform clockwise-BFS starting at the node marked r, with first child f in direction clockwise and label the nodes with the BFI's. On the picture, color the BFS tree edges in red and orient them so they are directed towards the BFS parents.

    (b) [10] Finish orienting the edges (using blue or black pen) from your picture from (a) to give the Pfaffian orientation of the planar graph proposed by Jerrum (as presented in class).

  2. Consider the following Pfaffian orientation of a graph G:

    (a) [5] List all the perfect matchings of G.

    (b) [5] Write down the skew-symmetric adjacency matrix A which corresponds to this Pfaffian orientation. Note: skew symmetric means that if ai,j = c, then aj,i = -c.

    (c) [10] Compute the determinant of your matrix from (c) by applying Gaussian elimination to the matrix until it is upper triangular keeping track of what each operation is doing to the determinant as you go along. Make sure you indicate what you are doing at every step, and how it affects the determinant.

  3. Consider this signed rotation system for a graph: 
      0: [  7, + ] [  1, + ] [  4, - ]
  1: [  2, + ] [  5, - ] [  0, + ]
  2: [  1, + ] [  3, + ] [  6, - ]
  3: [  2, + ] [  4, + ] [  7, - ]
  4: [  3, + ] [  5, + ] [  0, - ]
  5: [  4, + ] [  6, + ] [  1, - ]
  6: [  5, + ] [  7, + ] [  2, - ]
  7: [  0, + ] [  3, - ] [  6, + ]
    For each vertex, the neighbours are listed together with the signs of the corresponding arcs.
    (a) [10] Walk the faces of this embedding showing all your work.
    (b) [5] Use the genus formula to determine the non-orientable genus of this embedding. Then draw a picture of the embedding.
    (c) [5] Is this graph planar? To justify your answer, either show a planar embedding or indicate a subgraph that is homeomorphic to either K5 or to K3,3.
  4. Consider the face f that has repeated vertices and looks like this:

    Click here to get a worksheet for drawing your solutions. Print as many copies of the worksheet as you need.

    (a) [5] How many ways can you extend a torus embedding with a face f like this by adding chord (1, 3) to the embedding? Draw these.

    (b) [5] How many ways can you extend a torus embedding with a face f like this by adding chords (1, 3) and (2,4) to the embedding? Draw these.

    (c) [5] For each picture from (b), how many ways can a chord (3,5) be added to the embedding and how many total embeddings are there with these 3 chords?

    (d) [5] Extrapolate from these example to determine the number of embeddings of k chords for an example where f has vertices 0 to k+2 repeated on the boundary, and the chords to be added are (1, 3), (2, 4), (3, 5), ... ,(k, k+2).

  5. Consider the following tree T:

    (a) [5] What is the ( ) canonical form using the algorithm presented in class for the tree T-a?

    (b) [5] What is the ( ) canonical form using the algorithm presented in class for the tree T-b?

    (c) [5] What is the ( ) canonical form using the algorithm presented in class for the tree T-c?

    (d) [5] If the rule for choosing the parent of T is that we should pick the minimum canonical form for T-u such that u is a leaf of T, then which tree is the parent of T?