算法代写-CS 5200 PSET
时间:2022-03-01
CS 5200 PSET - 3
Avah Banerjee
Due on: March 2, 8:00 AM
Problem 1 For the graph G below run the DFS algorithm with the following vertex ordering
(a, b, c, d, e, f, g, h, i). Identify the four different types of edges (tree, forward, back and cross). Show
the DFS tree and identify all the connected component. Also determine the connected component
graph G .
a
b
c
d
e
f
g
h
i
Figure 1: The graph G
Problem 2 Let G1 = (V,E1, w1) and G2 = (V,E2, w2) be two positive edge weighted graphs on
the same vertex set V . We assume w(u, v) = ∞ if (u, v) is not an edge. Suppose s ∈ V is the
source vertex. Let G = G1 + G2 = (V,E,w) is the graph on the same vertex set V where the set
of edges and their weights are defined as follows:
E = {(u, v) | (u, v) ∈ E1 or (u, v) ∈ E2}
w((u, v)) = min(w1(u, v), w2(u, v))for all (u, v) ∈ E
Let d(s, u), d1(s, u), d2(s, u) be the shortest path distances between s and u inG,G1, G2 respectively.
Determine whether the following statement is true or false. Justify your answer.
∀u ∈ V : d(s, u) = min(d1(s, u), d2(s, u))
1
Problem 3 Exercise 4.12 from the textbook except assume all edges have the same length.
Problem 4 Determine the number of linear orderings of the following DAG.
a
b
c
d
e
f
g
2


essay、essay代写