~: 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
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?
, Elscores 8/18/2024 6:16:34 PM
~: 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.
Flow Network Constraints: Conservation of Flow
~: 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
~: 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
, Elscores 8/18/2024 6:16:34 PM
Residual Network
~: 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.
Ford-Fulkerson Runtime
~: 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
What is the time to check whether or not a flow is a max flow
~: - 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.
Capacity of a Cut
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Examify. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.49. You're not tied to anything after your purchase.
