Models of Computation - Mathematics 352 - Fall 2009

For HW #19

For a graph G, V(G) and E(G) denote, respectively, the set of all vertices and edges of G. Vertices are often labeled by numbers, and edges are often denoted by their endpoints. For example, if e is an edge whose endpoints are vertices 5 and 8, then e = (5,8) or {5,8}.

Problems marked [Optional] are important and must be done, but turn them in only if you're not sure how to do them.

1. (The definition of the adjacency matrix can be found in Wilf, page 166.)

   1. Give the adjacency matrix of K₄, the complete graph on four vertices (i.e., all vertices are connected to each other).
   2. Draw a graph whose adjacency matrix is:
      0 1 0 0
      1 0 1 1
      0 1 0 0
      0 1 0 0
   3. Is every square matrix of 0's and 1's the adjacency matrix of some graph? Prove your answer.

    

2. [Optional] What does an instance of a problem mean? Give an instance of TSP.  
3. Wilf, page 170, line -4 (i.e., 4th line from the bottom) says: "Any suggestions for a certificate?"
   Yes, I have a suggestion:
   List all possible tours, and next to each, write its total length. This can be done algorithmically. This is my "certificate".
   Verifying the certificate is easy: add up the distances for each tour to check that the total given in the list for each tour is correct; then check that none of these totals is less than K.
   Question: Is there anything wrong with my certificate? Did I prove that the problem "There is no tour of length less than K"  is in NP?