Graphs Flashcards
[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.
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
[Graph]
In a directed graph, how to detect a back edge?
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)
[Graph]
How to find a back edge in an undirected graph?
Check the following:
prev[u] != v
prev[v] != u
[Graph property]
Algorithmic way to find cross edge
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
[Graph property]
Algorithmic way to find back edge
Given vertices v and w:
1. pre/post of v must be in between pre/post of w
[SCC]
What is the relationship between cycles in a graph G and back edges in its DFS tree?
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
[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
1) True - but doesn’t affect whether cycles exist in G
2) True - this is definition of a back edge
[SCC]
How to topologically sort a DAG
- Run DFS
- Sort postorder number in descending order
[SCC]
Topological sorting runtime
O(n+m)
[SCC]
What are the two guaranteed vertex types in every DAG?
1) At least one source vertex (no incoming edges)
2) At least one sink vertex (no outgoing edges)
[SCC]
Using DAG’s DFS postorder numbering, how can you identify 1) source and 2) sink vertices?
Source has highest postorder #
Sink has lowest postorder #
[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.
1) False - every DAG must have at least one source vertex
2) True - these would be the last explored in DFS
[SCC]
Minimum # of edges you must add to a directed, connected graph to make it strongly connected
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)
[SAT]
When is a 2-SAT formula guaranteed to be satisfiable based on its SCCs?
if for all i, x_i and x_i-bar are in different SCCs
[SAT]
When is a 2-SAT formula NOT guaranteed to be satisfiable based on its SCCs?
if for some i, x_i and x_i-bar are in the same SCC
[SAT]
6 steps of 2-SAT algo
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
[SAT]
Key fact needed before running 2-SAT
for all i, x_i and x_i-bar are in different SCCs
[Paths]
Modifying graph by offsetting negative values is not valid for Dijkstra’s . Why?
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
[Paths]
How to detect cycle in an DIRECTED graph
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)
[Paths]
How to detect cycle in an UNDIRECTED graph
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.
[MST]
Input & Output
Input: Undirected weighted graph
Output: Spanning tree where sum of edge weights is the smallest possible
[MST]
Why is any bridge edge guaranteed to be in an MST?
Given a cut between S and V-S along that edge, that edge would be the only one that exists
[MST]
Explain greedy approach in plain words
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.
[Kruskal]
Algorithm
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
[Kruskals]
Runtime
O(m log n)
- sort weight = O(m log n)
- check cycle = O(m log n) using union-find over all edges
[Cut Property]
Define “cut”
Set of edges that divides vertices into 2 disjoint subsets: S and its complement S bar.
Requires an undirected graph.
[Cut Property]
Key proof of cut property
Adding e* to T forms cycle, removing any cycle edge yields new tree T‘
[Cut Property]
Key statement of cut property
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.
[MST]
T/F
1) There can be more than one MST
2) MST won’t exist for a disjoint graph
1) True
2) False. “minimally spanning forest” denotes multiple MSTs for a disjoint graph.
[Bellman Ford]
BF will always find a negative weight cycle in a graph
False
It will only find negative weight cycles reachable from start vertex.
[Bellman Ford]
How to find negative weight cycle
Check DP Table D(i, n-1) and D(i, n) and see if any v in V is different.
[Bellman Ford]
Subproblem
Let D(i,z) be the length of shortest path from s to z using at most i edges
[Bellman Ford]
Recurrence Relation
Runtime
Return logic
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)
[Floyd Warshall - All Pairs]
Subproblem
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
[Floyd Warshall - All Pairs]
Recurrence
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[Floyd Warshall - All Pairs]
Runtime
O(n^3)
Triple nest loop (i,s,t)
[Floyd Warshall - All Pairs]
Return logic
D(n, *, *)
2D table, shortest path for all pairs
[Floyd Warshall]
FW will always find a negative weight cycle in a graph
True
It checks all pairs in the graph (unlike BF) so it will always find a cycle if it exists.
[Floyd Warshall]
How to find a negative weight cycle
Check 2D table of D(n,,) to see if any of its diagonal entries are negative.
[Bellman Ford]
Runtime to get all pairs shortest paths using BF
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)
[MST]
Given graph G=(V, E) give a formal statement of a “spanning tree”
ST != MST
- S is subset of G
- S = (V’, E’)
- where V’ = V (# vertices equal)
- where |E’| = |V| - 1 (n-1 edges)
[MST]
Given G=(V,E) how many spanning trees are possible
|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
[Runtime]
Big-O of O(n+m) operation on a clique and m >= n-1
O(n^2) because number of edges >= vertices
[Runtime]
Big-O of O(n+m) operation on a tree
n=vertices, m=edges
O(n) because tree property means m = n - 1 so O(n + n-1) which simplifies to O(n).
[Runtime]
Big-O of O(n+m) runtime of graph that is connected and m >= n-1
O(m)
O(n+m) = O(m+m) = O(2m) = O(m)
[Runtime]
Traversing a graph
O(n+m)
(Includes reversing, copying, subgraphing, or anything that requires working with all vertices and edges in a graph)
[Runtime]
Operating on a single vertex v
O(1)
(Includes find, read, removal)
[Runtime]
Operating on all (or a subset of) vertices V
O(n)
(Includes find, read, removal)
[Runtime]
Operating on a single edge e=(u,v)
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)
[Runtime]
Operating on all edges |E|
O(n + m)
(Includes find, read, removal)
[Runtime]
Accessing properties of an edge or vertex
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.)
[MST]
Why does Prim’s algorithm work with negative edge weights while Dijkstra’s algorithm doesn’t?
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.
[MST]
T/F
One can find a MST in a disconnected graph
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.
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)).
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
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.
1) False
2) False
3) True
4) True
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.
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.
[2SAT]
Create implication of this conditional:
a v b
a-bar -> b
b-bar -> a
