CS6515 Exam 2 Questions with Verified Correct
Answers
Basic Properties of Trees
Tree's are undirected, connected and acyclic that connect all nodes.
1. Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than n-1 edges
means cycle)
2. In tree exactly one path between every pair of vertices (otherwise it's not connected)
- More than 1 path implies cycle
- less than 1 path implies not connected
3. Any connected G(V, E) with |E| = |V| - 1 is a tree
Kruskal's Algorithm
1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our current tree if it doesn't create a cycle
Running Time: O(m log n), m = |E|, n = |V|
Is there ever a reason to use cycles in a flow graph?
No
Flow Network Constraints: Capacity Constraint
For all edges, the flow must be larger than zero, but less than the capacity of that edge
Goal of Flow Problem
,Maximize the flow out of the source (or into the sink) of maximum size while satisfying the
capacity and conservation of flow constraints.
Flow Network Constraints: Conservation of Flow
For all vertices (other than the starting (source) and ending (sink) vertices), the flow into v
must equal the flow out of v.
Ford-Fulkerson Algo
1. Start with f_e = 0 for all edges
2. Build the residual network for current flow
3. Find st-path in residual network
- if no such path then output f
4. Let c(p) = min(c_e - f_e); this is available capacity along some path
5. Augment f by c(p) along p
- for forward edges increase flow by c(p)
- for backward edge, decrease flow by c(p)
6. Repeat
Residual Network
For flow network G = (V, E) with c_e for edges and f_e for flows:
1. If there exists an edge vw where f_vw < c_vw, add vw to residual network with capacity
c_vw - f_aw
2. If there exists an edge vw where f_vw > 0, then add wv to residual network with capacity
f_vw
Note: 1 shows available forwards capacities and 2 shows residual backward capacities.
, Ford-Fulkerson Runtime
Need to assume all capacities are integers. This will allow flow to always increase by at least
1 unit per round. If C is the maxflow, then there are at most C rounds. Each round of FF takes
O(m), so the total time is O(mC), which is pseudo-polynomial
What is the time to check whether or not a flow is a max flow
- O(n + m)
1. Build the residual graph takes O(n + m) time
2. Checking if there's a path from s to t using DFS, which takes linear time.
Capacity of a Cut
Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut
Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas
1. Take a tree T, add an edge e* will create a cycle. Removing any edge of the cycle we'll get
a new tree
2. A minimum weight edge across a cut is part of a MST
Runtime: Confirm a vertex exists
O(1)
Runtime: Confirm edge exists
O(m)
Answers
Basic Properties of Trees
Tree's are undirected, connected and acyclic that connect all nodes.
1. Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than n-1 edges
means cycle)
2. In tree exactly one path between every pair of vertices (otherwise it's not connected)
- More than 1 path implies cycle
- less than 1 path implies not connected
3. Any connected G(V, E) with |E| = |V| - 1 is a tree
Kruskal's Algorithm
1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our current tree if it doesn't create a cycle
Running Time: O(m log n), m = |E|, n = |V|
Is there ever a reason to use cycles in a flow graph?
No
Flow Network Constraints: Capacity Constraint
For all edges, the flow must be larger than zero, but less than the capacity of that edge
Goal of Flow Problem
,Maximize the flow out of the source (or into the sink) of maximum size while satisfying the
capacity and conservation of flow constraints.
Flow Network Constraints: Conservation of Flow
For all vertices (other than the starting (source) and ending (sink) vertices), the flow into v
must equal the flow out of v.
Ford-Fulkerson Algo
1. Start with f_e = 0 for all edges
2. Build the residual network for current flow
3. Find st-path in residual network
- if no such path then output f
4. Let c(p) = min(c_e - f_e); this is available capacity along some path
5. Augment f by c(p) along p
- for forward edges increase flow by c(p)
- for backward edge, decrease flow by c(p)
6. Repeat
Residual Network
For flow network G = (V, E) with c_e for edges and f_e for flows:
1. If there exists an edge vw where f_vw < c_vw, add vw to residual network with capacity
c_vw - f_aw
2. If there exists an edge vw where f_vw > 0, then add wv to residual network with capacity
f_vw
Note: 1 shows available forwards capacities and 2 shows residual backward capacities.
, Ford-Fulkerson Runtime
Need to assume all capacities are integers. This will allow flow to always increase by at least
1 unit per round. If C is the maxflow, then there are at most C rounds. Each round of FF takes
O(m), so the total time is O(mC), which is pseudo-polynomial
What is the time to check whether or not a flow is a max flow
- O(n + m)
1. Build the residual graph takes O(n + m) time
2. Checking if there's a path from s to t using DFS, which takes linear time.
Capacity of a Cut
Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut
Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas
1. Take a tree T, add an edge e* will create a cycle. Removing any edge of the cycle we'll get
a new tree
2. A minimum weight edge across a cut is part of a MST
Runtime: Confirm a vertex exists
O(1)
Runtime: Confirm edge exists
O(m)
