[FrontPage] [TitleIndex] [WordIndex

This assignment is due Friday, December 10 at 3pm on paper in AC312. (Note unusual time; I want to get these graded ASAP and may have to leave campus early....) Electronic submissions are welcome as a supplement.

Graph Facts

For all of the problems in this section, you need consider only simple graphs, i.e., no self-edges and no duplicate edges. The graphs are also all 'connected' - ie, every node has an edge to at least one other node.

  1. A complete graph is one in which every node has an edge to every other node.
    1. How many edges are in a complete (fully connected) undirected graph with n vertices?

    2. How many edges are in a complete directed graph with n vertices?

  2. Two graphs are distinct if there's no relabeling of node names that makes them the same.
    1. How many distinct undirected graphs with four vertices exist?
    2. How many distinct directed graphs with three vertices exist?
  3. The degree of a vertex is the number of its neighbors. An undirected graph is a tree if (a) every vertex is connected to every other vertex either directly or indirectly and (b) it contains no cycles, i.e., loops. Note that, by this definition, a tree need not be binary. Find all trees that contain
    1. that contain no vertices of degree one
    2. that contain exactly one vertex of degree one
    3. that contain exactly two vertices of degree one
    4. that contain exactly three vertices of degree one.

Graph Algorithms

  1. Consider the following directed graph:
    •     V = {A, B, C, D, E, F, S}
          E = {(S, A, 7), (S, B, 3), (S, C, 5)
             (A, D, 5)
             (B, A, 5), (B, C, 1), (B, E, 1)
             (C, B, 2),
             (E, A, 2),
             (F, E, 8)}
    Draw the graph. Run through Dijkstra's algorithm to find the shortest paths from S to each of the other nodes in this graph. Dijkstra's algorithm loops over nodes, starting with S, considering each node in order of minimum cost, updating distance estimates to each reachable and non-finalized node. Show the graph after each step, i.e., after each node has been finalized. Include cost estimates to each node at that point in the execution of the algorithm.

    Dijkstra's algorithm is described in all algorithms textbooks (including Cormen p. 595, with Relax on p. 586) and also at Wikipedia, among other places.

NP

  1. Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability (i.e., given a propositional logic formula, is there some truth assignment that makes it true or does no such truth assignment exist?). Describe how to use this algorithm to find satisyfing assignments -- i.e., to identify one such truth assignment -- in polynomial time.

    What you are given is a procedure -- say, IsSatisfiable -- that takes a boolean formula as an argument and returns either yes (if the argument formula is satisfiable) or no (if it is not). IsSatisfiable does not take truth assignments along with its formula or return truth assignments. For example:

    • IsSatisfiable( p ^ not( p ) ) 
    would return no (or false), while
    • IsSatisfiable( (p v q) ^ (not(q) v r) ^ (p ^ not(r)) ) 

    would return true, because both the truth assignment {(p, true), (q, false), (r, true)} and the truth assignment {(p, true), (q, false), (r, false)}make (p v q) ^ (not(q) v r) ^ (p ^ not(r)) true. However, IsSatisfiable doesn't produce {(p, true), (q, false), (r, true)} or {(p, true), (q, false), (r, false)}; it just answers yes.

    Your task is to come up with a way to find satisfying truth assignments. Like IsSatisfiable, your procedure should take a boolean formula as an argument. Unlike IsSatisfiable, your procedure will return a truth assignment. Because your method needs to run in polynomial time, you will need to make use of the magic IsSatisfiable polynomial-time decision procedure. Your method may call IsSatisfiable on any boolean formula you want. You may call IsSatisfiable more than once.  You may, however, only call it a polynomial number of times. (Calling it an exponential number of times would make your procedure exponential even if IsSatisfiable` works its magic in polynomial time.)

    Your answer should consist of a pseudocode algorithm (which is allowed to call IsSatisfiable( boolean_formula ) up to a polynomial number of times) as well as an informal English argument that this algorithm runs in polynomial time (assuming that IsSatisfiable does).


2013-07-17 10:43