Homework: Graphs

   < Previous  Next >
Write your answers to the following questions in a flat text file hwkGraphs.txt (not a Word document nor a Rich Text Format file).

Graph 1 Graph 2 Graph 3 Graph 4
  1. Give the adjacency matrix for the following graphs:
    1. Graph 1
    2. Graph 2
  2. Give the adjacency list for the following graphs:
    1. Graph 1
    2. Graph 2
  3. Will the adjacency matrix be symmetrical for
    1. a directed and undirected graph?
    2. a weighted and unweighted graph?
  4. List the vertices in the order in which each traversal visits them (starting at vertex A) using a
    1. depth-first strategy for Graph 1
    2. depth-first strategy for Graph 3
    3. breath-first strategy for Graph 1
    4. breath-first strategy for Graph 3
  5. Write the topological order of the vertices for each digraph above (using the algorithm required for the lab, except to find the next vertex that does not have a successor, iterate over vertices in alphabetical order, starting over each time). If this is not possible, state why.
  6. Calculate the shortest path from vertex A to every other vertex for Graph 3.
  7. Produce the DFS spanning tree rooted at vertex A for the Graph 3. Write the vertices in the order visited. For each vertex, write in parentheses the vertex on the other side of the edge used. For example, for a graph with vertices α and β (and an edge between them), for a search starting at α, write the following: "α β(α)"
  8. Produce the minimum spanning tree (starting at vertex A) for Graph 3.
    1. Write the vertices in the order visited (e.g., A -> B -> ...).
    2. Write the total weight.
  9. For each undirected graph above, produce an Euler circuit (starting at vertex A). If this is not possible, state why.

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points       Question
----------   --------------------------------------------------------------
_____ /  2   1
_____ /  2   2
_____ /  1   3       
_____ /  2   4
_____ /  1   5
_____ /  2   6
_____ /  1   7
_____ /  1   8
_____ /  1   9
        	       
_____ / 13   Total

Last Modified: