Summary - Network flow

Print the max flow in a mini task.

Summary - Network flow

In this group we covered the foundations of network flow: flow network, Ford-Fulkerson, Edmonds-Karp, max-flow min-cut and bipartite matching.

Ford-Fulkerson and Edmonds-Karp find the max flow via augmenting paths. The max-flow min-cut theorem links this to a cut problem; bipartite matching is an application.

We will now revisit source capacity with a small task.

Exercise source_capacity mini task

Write source_capacity(graph, source). Return the total capacity of edges leaving the source. Print 8 with print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's')).

Show example solution

def source_capacity(graph, source):
    # Total capacity leaving the source
    total = 0
    for u, v, c in graph:
        if u == source:
            total += c
    return total
print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's'))

Test yourself

Which method does Edmonds-Karp use?
- DFS
- Greedy
- BFS
- DP
Show answer

BFS — Edmonds-Karp uses BFS to find the shortest path.

maximum flow value

# max_flow = min_cut_capacity
# max_flow == ____

Show answer

# max_flow = min_cut_capacity
# max_flow == min_cut

Method-tool

Ford-Fulkerson

DFS
Edmonds-Karp

BFS
max-flow min-cut

Theorem
bipartite matching

Application

Next lesson: Minimax

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies