Cs 6515 Exam 2 Questions With Solutions
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 Running Time: O(m log n), m = |E|, n = |V| 2. Go through edges in order and add an edge to our current tree if it doesn't create a cycle 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.
Document information
- Uploaded on
- May 25, 2025
- Number of pages
- 14
- Written in
- 2024/2025
- Type
- Exam (elaborations)
- Contains
- Questions & answers
