CS6515 EXAM 2 | QUESTIONS AND ANSWERS | WITH
COMPLETE SOLUTION
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
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|
Is there ever a reason to use cycles in a flow graph? Answer - No
Flow Network Constraints: Capacity Constraint Answer - For all edges, the flow
must be larger than zero, but less than the capacity of that edge
, 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.
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.
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
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.
COMPLETE SOLUTION
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
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|
Is there ever a reason to use cycles in a flow graph? Answer - No
Flow Network Constraints: Capacity Constraint Answer - For all edges, the flow
must be larger than zero, but less than the capacity of that edge
, 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.
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.
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
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.
