Exam 2 Flashcards
Tree edge
edge in DFS graph
DFS output is a tree/forest (T/F)
true
Types of edges not in DFS tree
back, forward, and cross edges: these edges are not in the DFS tree but are in the original graph
post-ordering of edge z->w
post(z) > post(w) except for back edges
How do we know if G has a cycle?
G has a cycle if and only if its DFS tree has a back edge
Post order number
When doing DFS, when we first visit a node, we give it a number (pre-order) and increase our counter, when we leave a node, we give it a number and increase our counter (post order)
How to do topological sorting (2 ways)
- Run DFS on a DAG
- We know that for all z->w, post(z) > post(w) ==> order vertices by decreasing post order number - Find a sink vertex, output it, delete it. Repeat. Will build ordering backwards
What is special about the first and last vertices in a topological sorting?
First vertex must be a source vertex and last must be a sink
Source vertex and its post-order #
has no incoming edges, highest post-order #
Sink vertex and its post-order #
has not outgoing edges, lowest post-order #
def: strongly connected
two vertices are strongly connected if there is a path from w to v and from v to w (in a directed graph)
def: SCC
Maximal set of strongly connected vertices. only in directed graph
metavertex/metagraph
can replace SCCs with metavertices to create a metagraph. metagraph is always a DAG
SCC Algorithm general idea
find a sink SCC, output it, remove it, and repeat
Why use sink SCC in algorithm?
Running explore on a vertex in sink will return all vertices in that SCC (and no others)
How do we find a vertex in a source SCC and how does this help with the SCC Algorithm?
Vertex with highest post number lies in a source SCC. If we reverse the graph, that vertex will be in a sink SCC
SCC Algorithm
SCC(G):
1. Construct a reverse graph
2. Run DFS on reverse G
3. Order vertices by decreasing post order number
4. Run undirected connected components algorithm on G (i.e. DFS)
Output = topological ordering of SCCs
SCC runtime
O(m+n)
CNF formula
conjunctive normal form formula. AND of several clauses
clause
OR of several literals
literals
x1, !x1, etc
SAT
input: CNF
output: T/F if it can be satisfied (and the assignments)
K-SAT
each clause has size at most k. k>= 3 in NP-Complete
How to simplify a 2-SAT
- Pick a unit clause (clause with 1 literal) and satisfy it
- Remove the unit clause and simplify all other clauses with that literal
- Repeat
==> End result is CNF where all clauses are of size 2
How to convert a 2-SAT to a directed graph
- 2n vertices for each literal
- 2m edges for each “implication” of each clause:
Implication example:
(!x1 OR !x2) => x1=T, then x2=>F ==> x1->!x2
=> X2=T then x1=F ==> x2 ->!x1
How do we know if a 2-SAT graph is satifiable?
For every x, x and !x must be in different SCCs
2-SAT Runtime
O(m+n)
What is an MST and what type of graph is it used on?
minimum sized, connected subgraph of minimum weight. Unconnected and weighted graph
A tree with N vertices has how many edges?
N-1
how many paths are between a pair of vertices on a tree?
1
How do we know if a connected graph is a tree?
it has |E| = |V| - 1
What is Kruskal’s Algorithm?
For finding an MST:
- Sort edges by increasing weight
- For each edge in sorted list, add the edge to the current tree if it doesn’t create a cycle
Kruskal’s Algorithm runtime
|E| * log |V|
What are the cut edges
The set of edges that connect two components
What are the cut edges
The set of edges that connect two components
Max-Flow Problem (input, goal, constraints, output)
Input: direct graph with capacity for each edge + source/sink vertices
Goal: Want to maximize the flow from s->t (flow out of s and into t)
Constraint: flow into a vertex must equal the flow out
Output: a flow for each edge
Anti-parallel edge (max-flow)
if we have two parallel edges (i.e. v->w and w->v), we must create an anti-parallel edge:
- take on edge and split into 2 edges with an extra vertex in between
- New two edges have same weight as previous one edge
How to create a residual network (max-flow)
Input: graph and flow set
Add forward edges: if f[e] < c[e], then add that edge with weight c[e] - f[e]
Add backwards edges: if there is an edge v->w and flow > 0, add an edge w->v with capacity f[e]
Ford-Fulkerson Algorithm
- Set all flows = 0
- Create residual graph for current flow
- Check for a path s->t in residual graph
- If no path, output flows
- Let c(P) be the minimum capacity along the path in the residual network
- augment flows by c(P) (if e is a forward edge, increase flow by c(P), if e is a backward edge, decrease flow by c(P))
- Repeat steps 2-6 until no path
Ford-Fulkerson runtime
C = size of max flow
M = length of s->t path
O(mC) time
ST-Cut
Any cut of the graph that separates s into one half (L) and t into the other (R)
Capacity(L, R)
capacity of all edges from L->R
Min ST-Cut Problem
Want to find an st-cut with minimum capacity
Max-Flow Min-Cut Theorem
size of the max-flow = minimum capacity of an st-cut
Image segmentation problem
separate an image into objects
Image segmentation formulation
- Each pixel is a vertex in the graph
- Edge between neighboring pixels
- For each vertex there is a probability that it is in the foreground and a probability that it is in the background
- For each edge, there is a separation penalty
What is a demand for Max-Flow?
The demand for an edge is the minimum flow (so 0 <= demand <= flow <= capacity)
what is a Feasible flow ?
a flow where every edge meets the demand
Finding a feasible flow overarching idea
transform feasible flow problem into a max-flow problem
How to create G’ for finding a feasible flow
- Add two extra vertices to G: s’ and t’
- C’(e) = c(e) - d(e) I.e. new capacities are the difference between the demand and old capacity
- Add new edges: from s’ to all vertices (except t’) and from all vertices (except s’) to t’
○ Capacity for all edges s’->v == the total incoming demand for v
○ Capacity for all edges v->t’ == the total outgoing demand for v - Add an edge from t->s with capacity infinity
What is a Saturated flow?
size(f’) == sum of all outgoing demand of s’ (and incoming demand of t’)
How do we know if G has a feasible flow?
G has a feasible flow if and only if G’ has a saturated flow
How do we know if G has a feasible flow?
G has a feasible flow if and only if G’ has a saturated flow
Differences between Edmund-Karp and Ford-Fulkerson
E-K uses BFS only to find st-path
E-K does not require integer capacities
E-K runtime
O(m^2*n)
