Homework 10 (last one)

CS 280 - Spring 2002

Due: Friday, May 3 (last day)

Assume that the term graph refers to a simple graph unless otherwise indicated.

Part A

  1. Your are given a directed graph G with 1000 vertices.  There is one weakly connected component of size 800 and several other weakly connected components of smaller size.  There is one strongly connected component of size 500 and several other strongly connected components of smaller size.
    1. Suppose a Breadth First Search starting at vertex u visits 600 vertices.  Is this vertex in the large weakly connected component?  Why?  Is this vertex in the large strongly connected component?  Why?
    2. Suppose a Breadth First Search starting at vertex v visits 600 vertices when the search is run normally and visits 700 vertices when the search is run on the graph in which all directed edges are reversed.  Is this vertex in the large weakly connected component?  Why?  Is this vertex in the large strongly connected component?  Why?
       
  2. Your relatives have decided that, as an expert in Computer Science, you should handle the difficult problem of planning seating assignments for the next meeting of your extended family.  The difficulty is that several of your relatives are feuding and refuse to eat a meal in the same room with various other relatives.  The event is being held in a banquet hall which has available many different dining rooms of many different sizes.  The goal is to fit your relatives into as few rooms as possible without placing any feuding pair in the same room.  Show how this problem can be solved using a graph coloring algorithm.  In other words, assume you have an algorithm that colors a graph with as few colors as possible and show how to build a graph such that the graph-coloring solution for this graph easily leads to a solution for seating relatives.  You should assume that the banquet hall has many rooms as you need and that, whatever size room you need, such a room is available.

Part B

  1. The Emperor has gone insane and has declared that from now on, every road will be a one-way road.  Further, the Emperor declares that if a traveler leaves a town then it should not be possible to return to it.  As the Emperor's Chief Advisor, you have the task of picking a direction for each road in the Empire (you are not allowed to close or destroy roads).  If you fail to complete the task the Emperor will be very unhappy and will probably order that something rather unpleasant be done to you.  You would prefer to avoid this - the Emperor is insane after all.   Is there a way to assign directions so that the Emperor's rules are satisfied?  Explain. To simplify the problem, you can assume that each road starts and ends at a town and that roads only cross at towns.
     
  2. A graph is self-complementary if it is isomorphic to its complement.  Gc, the complement of  graph G, has the same vertex set as G, but has an edge between vertices u and v if and only if in G there is no edge between u and v.  Give an example of a graph that is self-complementary.

Part C

  1. Consider the following tree:
            a
      /   \
     b      c
    /     /   \
   d     e      f
        / \       \
       g   h       i
        \
         j
    1. In what order are the nodes processed in a preorder traversal?
    2. In an inorder traversal?
    3. In a postorder traversal?
    4. Give an example of an ordered binary tree with 4 nodes for which nodes are processed in the same order for both the preorder traversal and the inorder traversal.
     
  2.  
    1. Give necessary and sufficient conditions on a graph G so that the depth-first tree and the breadth-first tree are the same.
    2. How many nonisomorphic spanning trees does K4 have?  Explain.