Exam 2 Flashcards
Study for exam 2
What must be present if there’s a back edge?
There must be a cycle in the graph if the DFS tree has a back edge
What is a DAG and what are its characteristics?
directed acyclic graphs
every vertex u where there is an edge to vertex v has one direction
has no cycles in the graph
Can be topologically sorted
Must have one or more source vertex
Must have one or more sink vertex
What is an alternative topological sorting algorithm?
Alternative topological sorting:
Find a sink vertex, output it, and then delete
Repeath this first step until the graph is empty
How do we find a sink vertex in a DAG?
Find the lowest postorder number vertex in a DAG
What is the pseudocode for the SCC algorithm?
- construct a reverse G of the original input graph G
- run DFS on G reverse
- order V by decreasing post order number
- run undirected connected components alg on G
What are the types of edges in a graph?
forward edge - is a forward edge if it points from a vertex to one of its descendants in the DFS tree, but is not a tree edge
- pre(u) < pre(v)
- post(u) > post(v)
-
back edge - an edge u-v is a back edge if it points from a vertex to one of its ancestors in the DFS tree
- creates a cycle in the DFS tree
- pre(u) > pre(v)
- post(v) > post(u) (only one where this is the case)
tree edge - edge u-v is a tree edge if v is a direct descendent of u in a DFS tree
- part of the DFS tree
- pre(u) < pre(v)
cross edge - edge u-v is a cross edge if it connects two vertices that are neither in a direct ancestor-descendant relationship nor part of the same DFS tree
- pre(u) and pre(v) have no distinct relationship
- the finish time of u and v also have no distinctive relationship
-
How do you find connected components in an undirected graph G? What is the runtime for doing this? What is the pseudocode?
Run DFS and keep track of component numbers #
O(n+m)
Psuedocode:
- Running explore from vertex
- Store z as visited because its the first time visiting
- Also store z in the current count for the connected components
- Now explore neighbors of z
If w or neighbor hasn’t been visited, the we call explore on that neighbor (recursively)
How can we use DFS to find a path between 2 vertices?
Run DFS and populate the previous values for each vertex in a previous array
We then have the previous array and use this to find a path between the pair of connected vertices
How do we find connectivity info on a directed graph?
We run DFS on the directed graph and add pre/post order numbers
Specifically:
We use clock values to track the pre and post orders
When first visiting vertex z, we store the preorder number
After visiting / exploring vertex z, we store the postorder number
What is required for there to be a cycle in a DFS tree?
There must be a back edge
Does a DAG have cycles or back edges
No cycles, no back edges
What happens when we topologically sort a DAG? Can there be more than one topological orderings?
Topological sort -> ordering from vertices from lower numbers to higher numbers
All edges should go from higher postorder number to lower postorder number
Thus, we order vertices by decreasing post order number
All post order numbers range between 1 and 2n
Therefore, we make an array of size 2n and insert each vertex in to the array in the appropriate place based on their post order number. We then iterate from highest to smallest and output the vertices. This step takes linear time
Yes, there can be more than one topological orderings
What are the source and sink vertices? How many do a DAG have?
Source = no incoming vertices; highest post order #
Sink = no outgoing edges; lowest post order #
Every DAG has one or more sink vertices
Vertices u and v are strongly connected if …
and only if there is a path u to v and v to u
How are SCC’s for an undirected graph found?
We find the SCC components in topological order
We visit any vertex from the sink vertex and visit nothing else
Then we find the strongly connected component
This even works for vertices like A where there are no other vertices in the SCC and they reach the whole graph
But once we find a sink vertex, we can run explore and get all parts of the SCC
What does BFS do? What is it’s runtime?
BFS explores graph in layers
- Specify start vertex as an input
- Returns the distance of every vertex from the start vertex
- O(n+m)
What does Dijkstra’s algorithm do? What is it’s runtime?
Dijkstra’ algorithm:
- More sophisticated version of BFS
= We are given a weights/length for every edge (needs to be positive)
- Output: shortest path from S to V
- Uses min-heap
- Runtime: O((n + m) * log n)
What is the general SCC algorithm? What does it do and what is it’s runtime?
input: directed graph G in adj list
Steps:
- construct a reverse graph Gr
- run DFS on the reverse graph Gr
- order the vertices by post order number by decreasing post order number
- run undirected connected components algorithm on the graph
Overall runtime: O(n+m)
Every directed graph is a …
DAG of its SCC’s
What is a satisfiability problem? What is the k-SAT problem? k-SAT is np-complete for all k values?
input: CNF formula with n variables and m clauses
output: assignment (T or F) to the variables satisfying each of the clauses if one exists
For the k-SAT problem:
input: CNF formula with n variables and m clauses (each of size <= k)
output: assignment (T or F) to the variables satisfying each of the clauses if one exists (no if none exists)
The K-sat problem is NP-complete for k >= 3
Solve this satisfiability problem:
(x2) ^ (xbar3 v x4) ^ (x3 v xbar5 v xbar1 v x2) ^ (xbar2 v xbar1)
Answer:
X1 = F
X2 = T
X3 = F
How can an input to the satisfiability problem be simplified?
Simplify:
- take any unit clause with 1 literal:
- satisfy it the single literal
- remove clauses containing that same literal and drop the bar of the literal (opossite)
- let f’ be the resulting formula
Thus, f formula input is satisfiable if f’ is satisfiable
Can assume this for all cases where size = 2
How is a graph related to a satisfiability problem? How is an SCC used?
Directed graphs to map out the implications for setting a given value to T or F indicating what you must set the next var to T or F
ex)
Take f with all clauses of size 2 with n variables and m clauses
2n vertices corresponding to the variables
2m edges corresponding to 2 “implications” per clause
If a literal var and its negation are in the same SCC, then f is not satisfiable
Its also true that any literal and its negation are in different SCCs, then there is a satisfying assignment
What is the algorithm for the satisfiability problem? Pseudocode? Runtime?
2-SAT problem (for k = 2)
Based on:
- if for all i, if xi and xbari are in different SCC
then S is a sink SCC <=> Sbar is a source SCC
Algorithm:
- construct a graph G for f
- Take a sink SCC S
- set S=T (and Sbar = F)
- remove S and Sbar
- repeat until empty
O(n + m) runtime
What is the MST problem? What are 2 algorithms for solving the MST problem?
input: given an undirected graph with weights
output: find the minimal size connected subgraph
- or minimum spanning tree of minimum weight
Both Kruskal’s algorithm works and Prim’s algorithm works for MST
What are the properties of a tree?
n vertices, n-1 edges
exactly one path between every pair of vertices
Any connected graph G (V,E) with |E| = |V| - 1
is a tree
How does Kruskal’s algorithm work? pseudocode/steps, runtime
input: undirected graph G (V,E) with weights
- sort each edge E by increasing weight (merge sort)
- set x != 0
- for each edge in the graph (in order):
- if x U e does not have a cycle:
x = x U E
- if x U e does not have a cycle:
return x
Total runtime: O(m log n )
What are cuts and what is the cut property? What algorithm takes advantage of the cut property?
Cuts are edges where one point is in S and the other is in S bar - they are the edges crossing between S and S bar
for any undirected graph:
you partition portions of the graph as S and Sbar
cut(S, Sbar) = edge crossing from S to Sbar
The cut property:
We are building a partial solution X we are building up
The green edges part of the MST T
We take subset S and look at cut between S and S bar
At of all the cut edges between S and S bar in purple, I want to find the minimum weight edge - this is e star
Any edge that’s a minimum across a cut is going to be part of some MST
Prim’s algorithm and Kruskal’s algorithm uses the cut property
Kruskal’s Algorithm: Considers edges in increasing order and uses the cut property to decide if an edge should be added to the MST.
Prim’s Algorithm: Grows the MST by adding the smallest edge crossing the cut that separates the MST from the rest of the graph
What is the max-flow problem?
Input: directed graph G (V,E) with s and t input vertices and capacities for each edge
Output: find the max flow for each edge where the capacity constraint is met and conservation of the flow is maintained (flow into v = flow out of v)
Fe is set for each edge in the input graph
Capacity Constraint: we need to have fe less than ce
Conservation of flow constraint: for all vertices minus s to t:
Flow in to v must be conserved or must equal the flow out of v
Flow into v:
Sum of the edges over w to v of the flow along this edge
Flow out of v:
Sum of the edges v to z of the flow along that edge
We are to find the valid flow of maximum size
Is it okay to have a cycle in the graph for a max-flow problem?
Yes
How do anti-parallel edges come into play in the max flow problem?
Simplification of the input network
We add edge capacities and now we find an equivalent flow network and the new network should not have anti parallel edges
We split the path from b to a into a 2 part path - b to f and f to a
What is the Ford-Fulkerson algorithm, runtime, and steps/pseudocode?
Steps:
Considering the residual network we build it first
We look for path from s to t
If there’s no path, then output f
If we find the path, we donate it as p
Given p, the min capacity along p is Gf is c(p)
We augment the current flow by c(p) units along P
We repeat from step 2 until no such st-path
Runtime: O(mc)
How does the Edmonds-Karp algorithm work? Runtime? Steps/pseudocode?
It uses Breadth-First Search (BFS) to find the shortest augmenting paths in terms of the number of edges. This guarantees that the algorithm runs in polynomial time
Steps:
- Construct the residual graph Gf based on the original capacities and current flows. Initially, it is the same as the original graph with capacities c(e)
- find the augmenting graph using BFS
- Update the flows in the following steps:
- determine the residual capacity of the augmenting graph
- increase the flow along the path P - for each edge in the path:
- update the flow by adding f(u,v)
f(u,v)=f(u,v)+cf (P)
cf(u,v)=c(u,v)−f(u,v)
Also update the reverse flow f(v, u) and the reverse residual capacity cf(v,u)
f(v,u)=f(v,u)−cf(P)
cf(v,u)=c(v,u)−f(v,u)
Repeat the process until no more augmenting paths can be found from s to t in the residual graph.
Runtime: O(VE^2) or O(m^2n)
What is the max-flow / min-s-t cut theorem?
A cut is a partition of the L U R
s-t cut is a cut where S E L, t E R
capacity(L,R) = sum Cvw = capacity from L to R
for any flow f and any S-T cut (L,R)
size f <= capacity(L,R)
max size f <= minimal capacity(L,R)
claim is size(f) = f(out) L - f(in) L
we want a size(f) <= capacity(L,R)
max-flow <= min s-t cut capacity
What is the residual network for the Ford Fulkerson algorith?
Residual network Gf
For the flow of flow graph G with edge capacities ce, for each edge in the graph and flow in the graph fe:
- if vw edge in and flow of wv edge are less than the capacity of vw edge, then add vw edge to the residual network graph Gf with capacity cvw - fvw
- if vw edge in and flow of wv edge are greater than 0, then add wv edge to the capacity Gf with capacity fvw
What is the main difference between Ford-Fulkerson and Edmond’s-Karp?
- Edmond’s-Karp uses BFS while Ford-Fulkerson uses BFS or DFS or other approaches
- Edmond’s-Karp uses BFS to ensure that the shortest path is found in each iteration. This guarantees that the number of augmenting steps is minimized
- Edmonds-Karp is O(m^2n) while the Ford-Fulkerson time complexity depends on whether DFS or BFS is used (Edmonds-Karp provides a predictable runtime)
You are given an unweighted, undirected graph G=(V, E) where V is a list of vertices and E is an adjacency list of edges. You are also given a vertex x and a value k such that you want to avoid x and any vertex within k distance of x. Lastly you are asked to find a shortest path from a given s to t. Assume that there is a path from s to t such that you can avoid x and vertices within k distance of x
Select the algorithm that is considered correct and optimal for this class. What is the runtime?
a.
We first run BFS from x such that we get shortest path costs to all other vertices. We then modify BFS such that if when we would visit a v in V that has a dist ≤ k from x, we avoid it instead of following that path. Run G through the modified BFS from s and return the shortest path from s to t.
b. We first run BFS from x such that we get shortest path costs to all other vertices. We then remove all v in V such that the dist from x is ≤ k. Run the updated G’ through BFS from s and return the shortest path from s to t.
c. dist = BFS(G, x).dist
G’ = G
for v in V:
if dist[v] ≤ k:
G’.remove(v)
prev = BFS(G’, s).prev
path_list = t
v = t
while prev[v] not null:
v = prev[v]
path_list = v + path_list
return path_list
d. Assuming all edges have a cost of 1, we first run Dijkstra’s from x such that we get shortest path costs to all other vertices. From all v in V that has dist to x ≤ k, set edges touching v to a cost of infinite. Run the updated G’ through Dijkstra’s from s and return the shortest path from s to t.
Correct answer b
By modifying the graph to remove any unwanted vertices, we create shortest paths that do not use the vertices we cannot travel through. BFS will find the shortest path for s to t.
runtime: The first BFS has a known runtime of O(n+m). Removing unwanted vertices and its edges is O(n+m). The second BFS is also O(n+m). This gives us a final runtime of O(n+m).
