- | Page
CS6515 EXAM 2 | QUESTIONS AND
CORRECT ANSWER S | LATEST
UPDATE | GRADED A+
Question : Basic Properties of Trees
CORRECT ANSWE R: Tree's are undirected, connected
and acyclic that connect all nodes.
Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than n-1 edges means cycle)
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
Any connected G(V, E) with |E| = |V| - 1 is a tree
- | Page
Question : Kruskal's Algorithm
CORRECT ANSWER : 1. Sort E by increasing weigt
- 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 : Is there ever a reason to use cycles in a flow
graph?
CORRECT ANSWER : No
Question : Flow Network Constraints: Capacity Constraint
CORRECT ANSWER : For all edges, the flow must be
larger than zero, but less than the capacity of that edge
Question : Goal of Flow Problem
CORRECT ANSWER : Maximize the flow out of the
source (or into the sink) of maximum size while
- | Page
satisfying the capacity and conservation of flow constraints.
Question : Flow Network Constraints: Conservation of Flow
CORRECT 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 : Ford-Fulkerson Algo
CORRECT ANSWER : 1. Start with f_e = 0 for all
edges
- Build the residual network for current flow
- Find st-path in residual network
if no such path then output f
Let c(p) = min(c_e - f_e); this is available capacity along some path
- | Page
Augment f by c(p) along p
for forward edges increase flow by c(p)
for backward edge, decrease flow by c(p)
Repeat
Question : Residual Network
CORRECT ANSWER : For flow network G = (V, E)
with c_e for edges and f_e for flows:
If there exists an edge vw where f_vw < c_vw, add vw to residual network with capacity c_vw - f_aw
If there exists an edge vw where f_vw > 0, then add wv to residual network with capacity f_vw