Homeworks Easy

I am attaching 4 homework assignments. They are way too easy to complete, I just don’t have time right now.

Let me know if you need any other information.

Consider the following directed graph for each of the problems:
1. Perform a breadth-first search on the graph assuming that the vertices and adjacency lists are
listed in alphabetical order. Show the breadth-first search tree that is generated.
2. Perform a depth-first search on the graph assuming that the vertices and adjacency lists are
listed in alphabetical order. Classify each edge as tree, forward, back or cross edge. Label
each vertex with its start and finish time.
3. Remove all the back edges from the graph so it becomes a DAG. Perform a depth-first search
recording the start and finish times. Using those finish times, provide the topological order
that is produced. Provide one breadth-first topological order for that graph.
4. Determine the strongly connected components of the graph using the algorithm provided in
the sample problems. Show the final depth-first search of the transpose graph labeled with its
start and finish times. Identify the strongly connected components based on that search.
1. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing
how the data structures evolve specifically indicating when the distance from a fringe
vertex to the tree is updated. Clearly indicate which edges become part of the minimum
spanning tree and in which order. Start at vertex F.
2. Execute Kruskal’s algorithm on the weighted tree shown below. Assume that edges of
equal weight will be in the priority queue in alphabetical order and each edge name is
ordered alphabetically. Clearly show what happens each time an edge is removed from
the priority queue and how the dynamic equivalence relation changes on each step and
show the final minimum spanning tree that is generated.
3. Examine the minimum spanning trees generated in the previous two problems. In both
cases, indicate whether the spanning tree is unique. If it is not unique provide all other
minimum spanning trees. Explain how you made the determination whether the minimum
spanning tree is unique.
4. Given the following adjacency lists (with edge weights in parentheses) for a directed
graph:
A: B(2), C(7), D(6)
B: C(3), F(1)
C: E(3)
D: E(3)
E: F(1)
F: C(3), D(1)
Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data
structures evolve, with A as the starting vertex. Clearly indicate which edges become part of
the shortest path tree and in which order.
1. Using Warshall’s algorithm, compute the reflexive-transitive closure of the relation below.
Show the matrix after the reflexive closure and then after each pass of the outermost for loop
that computes the transitive closure.
0
0
0
0
[0
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
1
1]
2. Using the matrix in the previous problem show the final result of executing Floyd’s
algorithm on that matrix to produce a matrix containing path lengths.
3. Show the graph that corresponds to the matrix in the first problem assuming the rows and
columns correspond to the vertices a, b, c, d and e. Show its condensation graph, renaming its
vertices. Determine any topological order of that graph and create an adjacency matrix with
the vertices ordered in that topological order. Finally compute the reflexive-transitive closure
of that matrix. What characteristic of that matrix indicates that it defines a total order?
4. Using Floyd’s algorithm, compute the distance matrix for the weight directed graph defined
by the following matrix:
0
[

 4 −2
2
2
3
−3
0
4  5
6

]
0
Show the intermediate matrices after each iteration of the outermost loop.