Graphs

Question 1

[SCC]
T/F
1) If a DFS tree has no back edges, the graph could still contain a cycle
2) A graph with a back edge must have exactly one cycle.
3) If you run DFS from a different starting vertex, some cycles in the graph might disappear.

Answer 1

1) False - cycles and back edges are equivalent

2) False - graph can have multiple back edges

3) False - cycles are a property of a graph, independent of DFS starting point

Question 2

[Graph]
In a directed graph, how to detect a back edge?

Answer 2

Run DFS. If the postorder number of the “tail” vertex (the source of the edge) is greater than the postorder number of the “head” vertex (the destination of the edge)

Question 3

[Graph]

How to find a back edge in an undirected graph?

Answer 3

Check the following:
prev[u] != v
prev[v] != u

Question 4

[Graph property]

Algorithmic way to find cross edge

Answer 4

Given vertex u and v,
1. pre value for u must be less than its post value.
2. Both values of u are less than pre/post values of v

Question 5

[Graph property]

Algorithmic way to find back edge

Answer 5

Given vertices v and w:
1. pre/post of v must be in between pre/post of w

Question 6

[SCC]
What is the relationship between cycles in a graph G and back edges in its DFS tree?

Answer 6

Graph G has a cycle if and only if its DFS tree has a back edge.

This property holds true:
- Regardless of which vertex DFS starts from
- Regardless of the order vertices are explored in the adjacency list

Question 7

[SCC]
T/F
1) If you change the order vertices are explored in the adjacency list, back edges could become tree edges
2) A graph has a cycle if and only if DFS finds a descendant with an edge to one of its ancestors

Answer 7

1) True - but doesn’t affect whether cycles exist in G
2) True - this is definition of a back edge

Question 8

[SCC]

How to topologically sort a DAG

Answer 8

1. Run DFS
2. Sort postorder number in descending order

Question 9

[SCC]

Topological sorting runtime

Answer 9

O(n+m)

Question 10

[SCC]

What are the two guaranteed vertex types in every DAG?

Answer 10

1) At least one source vertex (no incoming edges)
2) At least one sink vertex (no outgoing edges)

Question 11

[SCC]

Using DAG’s DFS postorder numbering, how can you identify 1) source and 2) sink vertices?

Answer 11

Source has highest postorder #

Sink has lowest postorder #

Question 12

[SCC]

T/F

1) A DAG could exist without any source vertices if every vertex has at least one incoming edge.

2) In a DAG’s DFS, a vertex with no outgoing edges must have the lowest postorder number among its neighbors.

Answer 12

1) False - every DAG must have at least one source vertex

2) True - these would be the last explored in DFS

Question 13

[SCC]

Minimum # of edges you must add to a directed, connected graph to make it strongly connected

Answer 13

Create an edge from any vertex in each sink SCC back to any vertex in source SCC

(By connecting any vertex from the sink SCC back to the source SCC, we can create the entire graph into a cycle)

Question 14

[SAT]
When is a 2-SAT formula guaranteed to be satisfiable based on its SCCs?

Answer 14

if for all i, x_i and x_i-bar are in different SCCs

Question 15

[SAT]
When is a 2-SAT formula NOT guaranteed to be satisfiable based on its SCCs?

Answer 15

if for some i, x_i and x_i-bar are in the same SCC

Question 16

[SAT]
6 steps of 2-SAT algo

Answer 16

1) Simplify formula by removing unit clauses
2) Build implication graph
3) Run SCC algorithm to get topological ordering
4) Set sink SCC to true, source SCC to false
5) Remove satisfied sink/source SCC pair
6) Repeat steps 4-5 until graph is empty

Question 17

[SAT]
Key fact needed before running 2-SAT

Answer 17

for all i, x_i and x_i-bar are in different SCCs

Question 18

[Paths]

Modifying graph by offsetting negative values is not valid for Dijkstra’s . Why?

Answer 18

A-B-C
A-B=-1, B-C, -1, A-C=-1
If we offset negative by one, best path changes from A-B-C to A-C

Question 19

[Paths]
How to detect cycle in an DIRECTED graph

Answer 19

Run SCC algorithm and check if number of vertices is equal to the number of SCCs

(if any SCC contains more than one vertex, then the graph has a cycle)

Question 20

[Paths]
How to detect cycle in an UNDIRECTED graph

Answer 20

prev[u] != v AND prev[v] != u
for any (u,v)

If each were reached by a different path, then it doesn’t have a cycle.

Question 21

[MST]

Input & Output

Answer 21

Input: Undirected weighted graph

Output: Spanning tree where sum of edge weights is the smallest possible

Question 22

[MST]
Why is any bridge edge guaranteed to be in an MST?

Answer 22

Given a cut between S and V-S along that edge, that edge would be the only one that exists

Question 23

[MST]
Explain greedy approach in plain words

Answer 23

Start from smallest weight, and take edge. Continue incrementing weight and selecting same weights until hitting edge that would create a cycle. Step up weight, and continue taking edges until you can’t without creating a cycle.

Question 24

[Kruskal]

Algorithm

Answer 24

Input: Connected, weighted graph

Algo:
* Sort weight using mergesort
* Initialize X with empty set
* Go through edges in order (by lowest weight)
* If adding edge doesn’t create a cycle add to X
* Return X

Question 25

[Kruskals] Runtime

Answer 25

O(m log n) 1. sort weight = O(m log n) 2. check cycle = O(m log n) using union-find over all edges

Question 26

[Cut Property] Define "cut"

Answer 26

Set of edges that divides vertices into 2 disjoint subsets: S and its complement S bar. Requires an undirected graph.

Question 27

[Cut Property] Key proof of cut property

Answer 27

Adding e* to T forms cycle, removing any cycle edge yields new tree T‘

Question 28

[Cut Property] Key statement of cut property

Answer 28

It is always safe to add the lightest edge across any cut (ie. between vertex in S and one in V-S) provided X (edges that are part of MST) has no edges across the cut.

Question 29

[MST] T/F 1) There can be more than one MST 2) MST won't exist for a disjoint graph

Answer 29

1) True 2) False. "minimally spanning forest" denotes multiple MSTs for a disjoint graph.

Question 30

[Bellman Ford] BF will always find a negative weight cycle in a graph

Answer 30

False It will only find negative weight cycles reachable from start vertex.

Question 31

[Bellman Ford] How to find negative weight cycle

Answer 31

Check DP Table D(i, n-1) and D(i, n) and see if any v in V is different.

Question 32

[Bellman Ford] Subproblem

Answer 32

Let D(i,z) be the length of shortest path from s to z using at most i edges

Question 33

[Bellman Ford] Recurrence Relation Runtime Return logic

Answer 33

Recurrence: ``` D(0,s) = 0 D(0,z) = inf if z != s D(i,z) = min{ D(i-1, z), min{D(i-1,y) + w(y,z), ∀(y,z)∈E} } for 1 <= i < n ``` Runtime: O(nm), because 2d table Return logic: Return D(n-1, *) (1D table, shortest path from s to all v in V)

Question 34

[Floyd Warshall - All Pairs] Subproblem

Answer 34

Let D(i,s,t) be the length of the shortest path from s to t, using a subset of vertices V[1...i] as intermediate vertices

Question 35

[Floyd Warshall - All Pairs] Recurrence

Answer 35

``` D(0,s,t) = w(s,t) if (s,t) in E inf otherwise Recurrence D(i,s,t) = min{ D(i-1, s, t), D(i-1, s, i) + D(i-1, i, t) } for 0 <= i <= n, 1 <= s, t <= n ```

Question 36

[Floyd Warshall - All Pairs] Runtime

Answer 36

O(n^3) Triple nest loop (i,s,t)

Question 37

[Floyd Warshall - All Pairs] Return logic

Answer 37

D(n, *, *) 2D table, shortest path for all pairs

Question 38

[Floyd Warshall] FW will always find a negative weight cycle in a graph

Answer 38

True It checks all pairs in the graph (unlike BF) so it will always find a cycle if it exists.

Question 39

[Floyd Warshall] How to find a negative weight cycle

Answer 39

Check 2D table of D(n,*,*) to see if any of its diagonal entries are negative.

Question 40

[Bellman Ford] Runtime to get all pairs shortest paths using BF

Answer 40

Worst case O(n^4) - BF is O(nm) - Running BF on all V is O(n^2m) - In case of dense graph where |E| = |V|, becomes O(n^2n^2), simplifies to O(n^4)

Question 41

[MST] Given graph G=(V, E) give a formal statement of a "spanning tree" ST != MST

Answer 41

- S is subset of G - S = (V', E') - where V' = V (# vertices equal) - where |E'| = |V| - 1 (n-1 edges)

Question 42

[MST] Given G=(V,E) how many spanning trees are possible

Answer 42

|E| C_{|V|-1} - number of cycles Ex G=(6,10) 6 vertices and 10 edges. 10 C_5 = "the number of ways to select 5 edges from 10 total edges", and then subtract number of cycles

Question 43

[Runtime] Big-O of O(n+m) operation on a clique and m >= n-1

Answer 43

O(n^2) because number of edges >= vertices

Question 44

[Runtime] Big-O of O(n+m) operation on a tree n=vertices, m=edges

Answer 44

O(n) because tree property means m = n - 1 so O(n + n-1) which simplifies to O(n).

Question 45

[Runtime] Big-O of O(n+m) runtime of graph that is connected and m >= n-1

Answer 45

O(m) O(n+m) = O(m+m) = O(2m) = O(m)

Question 46

[Runtime] Traversing a graph

Answer 46

O(n+m) (Includes reversing, copying, subgraphing, or anything that requires working with all vertices and edges in a graph)

Question 47

[Runtime] Operating on a single vertex v

Answer 47

O(1) (Includes find, read, removal)

Question 48

[Runtime] Operating on all (or a subset of) vertices V

Answer 48

O(n) (Includes find, read, removal)

Question 49

[Runtime] Operating on a single edge e=(u,v)

Answer 49

O(n) This is due to the need to traverse up to n vertices in the adjacency list for vertex u, to find and operate on adjacency v. (Includes find, read, removal)

Question 50

[Runtime] Operating on all edges |E|

Answer 50

O(n + m) (Includes find, read, removal)

Question 51

[Runtime] Accessing properties of an edge or vertex

Answer 51

O(1) This assumes you already have access to the vertex or edge itself - that is, you have paid the runtime costs above for finding that vertex/edge, (e.g. weight, color, cost, capacity, etc.)

Question 52

[MST] Why does Prim's algorithm work with negative edge weights while Dijkstra's algorithm doesn't?

Answer 52

Dijkstra's might get trapped in negative weight cycles. Prim's builds an MST. Since MST is a tree, it avoids cycles. Cut property also shows that crossing a cut is part of some MST. This property holds regardless of negative edge weight.

Question 53

[MST] T/F One can find a MST in a disconnected graph

Answer 53

False - Spanning tree by definition must "span" or reach all vertices in the graph. - Since a disconnected graph has vertices that cannot be reached from each other, it's impossible to construct a single spanning tree, minimum or otherwise.

Question 54

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. 1) For all directed graphs G, SCC(G) is acyclic. 2) For all directed acyclic graphs G, SCC(G)=G. 3) There is an algorithm to find SCC(G) that runs in linear time on the size of G. 4) Every directed graph is the SCC(G) for some other graph G. 5) For all directed graphs G, SCC(REV(G))=REV(SCC(G)).

Answer 54

1) True. Covered in lectures 2) True. DAG = SCC 3) True. SCC algo 4) False. G with a cycle can't be a SCC 5) True. We get the same graph

Question 55

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. 1) e is a back edge. 2) if there is a directed path from u to v (different from the edge e itself), then e is a forward edge. 3) if u is the parent of v, then e is a tree edge. 4) If pre(u)>pre(v), then e is a cross edge.

Answer 55

1) False 2) False 3) True 4) True

Question 56

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. 1) All the weights are positive. 2) The edge e is the edge of minimum weight in some cut of G. 3) The edge e is not part of any cycle. 4) If we remove e from the graph, the resulting graph is disconnected.

Answer 56

1) False 2) True. 3) True. If there is a cycle, the cut e would never be chosen as minimum weight edge 4) True. The cut with edge e would only be chosen if edge e is a bridge edge.

Question 57

[2SAT] Create implication of this conditional: a v b

Answer 57

a-bar -> b b-bar -> a