CS6515 EXAM 2 UPDATED ACTUAL QUESTIONS AND CORRECT ANSWERS

CS6515 EXAM 2 UPDATED ACTUAL QUESTIONS AND
CORRECT ANSWERS

Question:
1. Basic Properties of Trees
Answer:
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

Question:
2. Kruskal's Algorithm
Answer:
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|

Question:
3. Is there ever a reason to use cycles in a flow graph?
Answer:
No

Question:
4. Flow Network Constraints: Capacity Constraint
Answer:
For all edges, the flow must be larger than zero, but less than the capacity of that edge

Question:
5. Goal of Flow Problem
Answer:
Maximize the flow out of the source (or into the sink) of maximum size while satisfying the capacity and
conservation of flow constraints.

Question:
6. Flow Network Constraints: Conservation of Flow
Answer:
For all vertices (other than the starting (source) and ending (sink) vertices), the flow into v must equal the
flow out of v.

Question:
7. Ford-Fulkerson Algo

, Answer:
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

Question:
8. Residual Network
Answer:
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.

Question:
9. Ford-Fulkerson Runtime
Answer:
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

Question:
10. What is the time to check whether or not a flow is a max flow
Answer:
- 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.

Question:
11. Capacity of a Cut
Answer:
Sum of capacities (edges) going from cut L to cut R

Question:
12. Max-flow = Min st-cut
Answer:
Size of Max-flow = min capacity of a st-cut

Question:
13. Cut Property: Key Ideas