5/10/25, 12:19 PM CS6515 Exam 2 2025 COMPREHENSIVE EXAM QUESTIONS |FREQUENTLY TESTED QUESTIONS |RECENTLY TESTING R…
CS6515 Exam 2 2025 COMPREHENSIVE EXAM
QUESTIONS |FREQUENTLY TESTED QUESTIONS
|RECENTLY TESTING REAL EXAM
QUESTIONS|VERIFIED SOLUTIONS (100%
CORRECT)
Save
Terms in this set (71)
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)
Basic Properties of Trees
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
1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our
Kruskal's Algorithm 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 No
use cycles in a flow
graph?
https://quizlet.com/1042188609/cs6515-exam-2-2025-comprehensive-exam-questions-frequently-tested-questions-recently-testing-real-exam-questio… 1/12
, 5/10/25, 12:19 PM CS6515 Exam 2 2025 COMPREHENSIVE EXAM QUESTIONS |FREQUENTLY TESTED QUESTIONS |RECENTLY TESTING R…
Flow Network Constraints: For all edges, the flow must be larger than zero, but
Capacity Constraint less than the capacity of that edge
Maximize the flow out of the source (or into the sink)
Goal of Flow Problem of maximum size while satisfying the capacity and
conservation of flow constraints.
For all vertices (other than the starting (source) and
Flow Network Constraints:
ending (sink) vertices), the flow into v must equal the
Conservation of Flow
flow out of v.
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
Ford-Fulkerson Algo
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
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
Residual Network
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.
Need to assume all capacities are integers. This will
allow flow to always increase by at least 1 unit per
Ford-Fulkerson Runtime 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
https://quizlet.com/1042188609/cs6515-exam-2-2025-comprehensive-exam-questions-frequently-tested-questions-recently-testing-real-exam-questio… 2/12
CS6515 Exam 2 2025 COMPREHENSIVE EXAM
QUESTIONS |FREQUENTLY TESTED QUESTIONS
|RECENTLY TESTING REAL EXAM
QUESTIONS|VERIFIED SOLUTIONS (100%
CORRECT)
Save
Terms in this set (71)
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)
Basic Properties of Trees
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
1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our
Kruskal's Algorithm 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 No
use cycles in a flow
graph?
https://quizlet.com/1042188609/cs6515-exam-2-2025-comprehensive-exam-questions-frequently-tested-questions-recently-testing-real-exam-questio… 1/12
, 5/10/25, 12:19 PM CS6515 Exam 2 2025 COMPREHENSIVE EXAM QUESTIONS |FREQUENTLY TESTED QUESTIONS |RECENTLY TESTING R…
Flow Network Constraints: For all edges, the flow must be larger than zero, but
Capacity Constraint less than the capacity of that edge
Maximize the flow out of the source (or into the sink)
Goal of Flow Problem of maximum size while satisfying the capacity and
conservation of flow constraints.
For all vertices (other than the starting (source) and
Flow Network Constraints:
ending (sink) vertices), the flow into v must equal the
Conservation of Flow
flow out of v.
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
Ford-Fulkerson Algo
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
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
Residual Network
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.
Need to assume all capacities are integers. This will
allow flow to always increase by at least 1 unit per
Ford-Fulkerson Runtime 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
https://quizlet.com/1042188609/cs6515-exam-2-2025-comprehensive-exam-questions-frequently-tested-questions-recently-testing-real-exam-questio… 2/12
