Exam 1 Graph Theory Quiz

Question 1

For the following statement: “Which of the following are true?” Why?

For a directed graph G, denote SCC(G) the metagraph of strongly connected components. Denote by REV(G) the graph resulting from reversing the directions of all edges in G.

Please select all statements which are always true

A. For all directed graphs G, SCC(G) is acyclic.

B. For all directed acyclic graphs G, SCC(G)=G

C. There is an algorithm to find SCC(G) that runs in linear time on the size of G.

D. Every directed graph is the SCC(G) for some other graph G.

E. For all directed graphs G, SCC(REV(G))=REV(SCC(G)).

Answer 1

Answers: A, B, C, E

Question 2

Choose the following that are true:

After running DFS on a directed graph G=(V,E), an edge e=(uv) satisfies post(u)>post(v).

Please select all statements which are always true

A. e is a back edge.

B. if there is a directed path from u to v (different from the edge e itself), then e is a forward edge

C. if u is the parent of v, then e is a tree edge.

D. If pre(u)>pre(v), then e is a cross edge.

Answer 2

Answers: C, D

Question 3

Let G = (V,E) be a connected, undirected, weighted graph. You are told that all edges in G have distinct weights, and that an edge e of maximum weight is part of the MST.

Which of the following statements must be true? Check ALL that apply.

A. All the weights are positive.

B. The edge e is the edge of minimum weight in some cut of G.

C. The edge e is not part of any cycle.

D. If we remove e from the graph, the resulting graph is disconnected.

Answer 3

Answers: B, C , D

Question 4

Let G=(V,E) be a connected, weighted graph. You modify the weights of all the edges by increasing their weight by one. This is, the new weights are wnew(e) = w(e) + 1

Which of the following is true? (choose one)

A. If T is an MST of the given graph, then T is also an MST of the modified graph

B. T is an MST of both the given graph and the modified graph if and only if T is the unique MST of G.

C.
The MST of both graphs are always distinct

D.
The MST of both graphs may be distinct.

Answer 4

Answer:
If T is an MST of the given graph, then T is also an MST of the modified graph

Question 5

Let {G=(V,E), s, t in V, c(e) for e in E} be a network. For a given valid flow f, you are told that the edge e=(uv) satisfies f(e)=c(e) (this is, the edge e is saturated).

Please select all statements that are always true.

A. The reversed edge (vu) is in the residual network Gf

B. The size of the flow f is at least c(e)

C. All paths from the source s to the sink t must traverse the edge e

D. There exists a path from s to t with capacity equal to c(e)

Answer 5

Answers:

A. The reversed edge (vu) is in the residual network Gf

B.
The size of the flow f is at least c(e)

Question 6

You run the Floyd-Warshall Algorithm in a weighted, simple graph G=(V,E) with n vertices. What is the value of the entry T[v,v,n]?

A.
T[v,v,n]=0, since the shortest distance from a vertex to itself is zero

B.
T[v,v,n] is the length of the shortest cycle that visits vertex v.

C. T[v,v,n] is equal to infinity since the algorithm does not account for paths with no edges.

D. T[v,v,n] is not computed by the algorithm

Answer 6

Answer: T[v,v,n] is the length of the shortest cycle that visits vertex v.

Question 7

Let {G=(V,E), s, t in V, c(e) for e in E} be a network and let f be a valid flow of maximum size. Consider a new network which is identical to the given one except that the capacities of all edges increase by one. This is, the new capacities are cnew(e) = c(e) + 1. Which of the following statements are true?

A. The flow f is a valid flow of maximum size in the new network

B. The size of the max flow in the new network has size at least size(f)+1

C. The size of the max flow increase only if there is a path of saturated edges from s to t

D. The size of the max flow in the new network is exactly equal to size(f)+1

Answer 7

Answer:

The size of the max flow in the new network has size at least size(f)+1