Problem 1: Short Answers Section
For this section, restrict answers to no more than a few sentences. Most answers can be
expressed in a single sentence. Unless otherwise stated, no proofs are necessary for this
sectio
...
Problem 1: Short Answers Section
For this section, restrict answers to no more than a few sentences. Most answers can be
expressed in a single sentence. Unless otherwise stated, no proofs are necessary for this
section.
(a) (1 pt) True or false: When run on a tree, DFS takes much longer than BFS because
it must reach a leaf before it can backtrack.
Answer: False.
(b) (2 pts) Let T be a BFS tree of a graph G, and let x and y be nodes in T, in layers
Li and Lj respectively. Furthermore, assume the edge (x, y) exists in G. What is the
maximum difference between i and j?
Answer: The maximum difference is 1. This is the content of Theorem (3.4) in
Kleinberg & Tardos.
(c) (2 pts) True or false: BFS and DFS will always explore every node in a graph. If true,
explain why. If false, provide a counterexample.
Answer: False. Counterexample: the graph with two nodes and no edges.
(d) (2 pts) Consider an undirected graph G = (V, E) where |V | = n. What is the
maximum possible value of |E| in terms of n? Briefly explain your reasoning.
Answer: |E| =
1
2
(n
2 − n). Each node can have n − 1 edges coming off of it to another
node, and there are n nodes, so n(n − 1) edges. We divide by 2 to account for the fact
that an edge from u to v is the same as an edge from v to u.
(e) (1 pt) Repeat the above question, but assuming that G is a directed graph.
Answer: |E| = (n
2 − n). Same logic as above, but edges are directed, so we no longer
need to divide by two (i.e. u → v is different from v → u)
(f) (2 pts) Consider an undirected graph G = (V, E). Construct its directed equivalent
G0 = (V
0
, E0
) as follows:
• V
0 = V
• For each pair of nodes x, y in V with (x, y) ∈ E, add the edges (x, y) and (y, x)
to E
0
.
Note that G0
is a directed graph, even though G was undirected. Now suppose that
that two particular nodes, u and v, have a path between them in G. Does this mean
that they are necessarily strongly connected in G0
? If not, provide a counterexample.
Answer: They are strongly connected in G’. The following is a proof of this fact (note: you
did not need
[Show More]
.png)
.png)
