Modeling Combinatorial Problems Using Flow Graphs: A Complete Guide

Network flow graphs provide a unified framework for solving combinatorial optimization problems by representing resources and constraints as vertices and edges with capacities, enabling solutions via maximum flow or minimum cut algorithms.

The hzwer/shareoi repository contains comprehensive educational materials on graph theory and competitive programming techniques. This article distills the core methodology for modeling combinatorial problems using flow graphs, drawing from the repository's lecture notes and practice problems to provide both theoretical foundations and runnable Python implementations.

Why Flow Graphs Solve Combinatorial Problems

Maximum flow and minimum cut problems form the computational backbone for numerous combinatorial tasks. By transforming a problem into a flow network, you convert discrete decision-making into a continuous optimization that standard algorithms can solve efficiently. This technique applies to bipartite matching, assignment problems, scheduling with constraints, project selection, and minimum cut partitioning.

The key insight is that capacities on edges act as hard constraints, while the flow itself represents the solution variables. Saturated edges in the final flow correspond to selected assignments or cuts in the original problem.

The Five-Step Modeling Framework

The teaching materials in 网络流建模 – 周尚彦 (PDF) outline a systematic approach to constructing flow graphs.

Step 1: Identify the Two Sides

Determine the bipartite or multi-partite structure of your problem. Common pairings include jobs versus workers, supply nodes versus demand nodes, or source states versus sink states. This partition dictates how you will connect to the super-source and super-sink.

Step 2: Connect the Super-Source

Create a source vertex S and add directed edges from S to every node on the supply side. Set edge capacities to represent the maximum units each node can provide. For unit matching problems, these capacities are typically 1.

Step 3: Connect the Super-Sink

Create a sink vertex T and add directed edges from every node on the demand side to T. Capacities here encode consumption limits or demand requirements. In standard matching models, these are also 1.

Step 4: Add Inter-Layer Edges

Connect the supply side to the demand side with edges representing feasible assignments or transitions. For simple matching, set capacity 1 on these edges. For problems allowing multiple assignments, use larger integers or the specific required capacity.

Step 5: Handle Additional Constraints

For complex constraints like node capacities, lower bounds, or precedence relations, apply standard transformations. To enforce a node capacity, split the vertex into an in-node and out-node connected by an edge with the desired capacity. For dependencies, use infinite capacity edges to force variables to stay on the same side of a cut.

Practical Implementation Examples

The following Python examples use the networkx library to demonstrate the modeling techniques found in the repository's lecture slides, specifically mirroring the approaches in 网络流 – 魏越闽 (PPT) and 线性规划与网络流 – 曹钦翔 (PPTX).

Bipartite Matching as Maximum Flow

This example models worker-task assignment. The construction follows the standard pattern from 网络流建模 – 周尚彦 (PDF), where unit capacities enforce the matching constraint.

import networkx as nx

# Build directed graph

G = nx.DiGraph()
source, sink = 'S', 'T'

workers = ['w1', 'w2', 'w3']
tasks   = ['t1', 't2', 't3']

# Source → workers (capacity 1)

for w in workers:
    G.add_edge(source, w, capacity=1)

# Tasks → sink (capacity 1)

for t in tasks:
    G.add_edge(t, sink, capacity=1)

# Worker → task edges (capacity 1 for each feasible assignment)

edges = [('w1', 't1'), ('w1', 't2'), ('w2', 't2'), ('w3', 't2'), ('w3', 't3')]
for w, t in edges:
    G.add_edge(w, t, capacity=1)

# Compute max flow

flow_value, flow_dict = nx.maximum_flow(G, source, sink)

print('Maximum matching size:', flow_value)

# Extract matched pairs

matching = [(w, t) for w in workers for t in tasks if flow_dict[w].get(t, 0) > 0]
print('Matched pairs:', matching)

Output

Maximum matching size: 3
Matched pairs: [('w1', 't1'), ('w2', 't2'), ('w3', 't3')]

The saturated edges from workers to tasks indicate the final assignment. The value of the flow equals the cardinality of the maximum matching.

Project Selection with Minimum Cut

This example solves the project selection problem (also known as the maximum closure problem). It demonstrates how to model profits and dependencies using a minimum s-t cut, as detailed in 线性规划与网络流 – 曹钦翔 (PPTX).

import networkx as nx

# Project data: name → profit (positive) / cost (negative)

projects = {
    'A':  8,   # profit

    'B': -5,   # cost

    'C':  3,
    'D': -2,
}

# Dependency edges: if X is chosen, Y must also be chosen

deps = [('A', 'B'), ('A', 'C'), ('C', 'D')]

G = nx.DiGraph()
source, sink = 'S', 'T'

INF = 10**9    # effectively infinite capacity for dependency edges

# Add source/sink edges based on profit/cost

for p, val in projects.items():
    if val >= 0:
        G.add_edge(source, p, capacity=val)   # profit edges go from source

    else:
        G.add_edge(p, sink, capacity=-val)   # cost edges go to sink

# Add dependency edges with infinite capacity

for u, v in deps:
    G.add_edge(u, v, capacity=INF)

# Minimum s‑t cut = total positive profit - max achievable profit

cut_value, (S, T) = nx.minimum_cut(G, source, sink)
total_profit = sum(v for v in projects.values() if v > 0)
max_profit = total_profit - cut_value

print('Maximum achievable profit:', max_profit)

# Recover selected projects (those reachable from source after the cut)

selected = [node for node in S if node not in (source, sink)]
print('Selected projects:', selected)

Explanation

• Positive-profit projects connect to the source with capacity equal to their profit.
• Negative-profit projects (costs) connect to the sink with capacity equal to their absolute cost.
• Dependency edges carry infinite capacity, forcing the minimum cut to place both projects on the same side (either both selected or both excluded) to avoid paying the infinite penalty.
• The minimum cut value represents the total profit of unselected positive projects plus the cost of selected negative projects. Subtracting this from the total possible profit yields the optimal achievable profit.

Learning Resources from the hzwer/shareoi Repository

The hzwer/shareoi repository provides extensive teaching materials that bridge theory and implementation. These documents, primarily in Chinese, offer step-by-step guidance on flow graph construction.

Resource	File Path	Description
Flow Modeling Guide	图论/网络流建模_周尚彦.pdf	Core reference for converting matching, project selection, and circulation problems into flow networks.
Theory & Algorithms	图论/网络流_周聿浩 & 黄哲威.pdf	Comprehensive coverage of max-flow/min-cut theory, augmenting path algorithms, and complexity analysis.
Visual Examples	图论/网络流_魏越闽.ppt	Slide deck with visual walkthroughs of bipartite matching and scheduling models.
Linear Programming Connection	图论/线性规划与网络流_曹钦翔.pptx	Demonstrates how LP formulations translate into flow networks, essential for problems with fractional capacities.
Exercise Collection	图论/图论基础与网络流习题集锦_朱睿.pptx	Practice problems with detailed flow model constructions and solutions.

Summary

• Flow graphs unify diverse combinatorial problems by encoding constraints as edge capacities and solutions as flow values.
• The five-step modeling framework (identify sides, connect source/sink, add inter-layer edges, handle constraints) provides a systematic way to construct networks for matching, scheduling, and selection problems.
• Maximum flow algorithms yield solutions for assignment and matching problems, while minimum cut formulations solve profit maximization and partitioning tasks.
• The hzwer/shareoi repository offers authoritative reference materials, including 网络流建模_周尚彦.pdf and 线性规划与网络流_曹钦翔.pptx, bridging theoretical foundations with competitive programming implementations.

Frequently Asked Questions

What types of combinatorial problems can be modeled using flow graphs?

Maximum flow and minimum cut formulations apply to bipartite matching, assignment problems, network connectivity, scheduling with resource constraints, project selection with dependencies, and image segmentation. Any problem involving assigning limited resources to competing demands or partitioning a set while minimizing connection costs can typically be expressed as a flow problem.

How do I handle additional constraints like node capacities or lower bounds?

For node capacities, split the vertex into an in-node and out-node connected by an edge carrying the capacity limit. For lower bounds on flow, transform the network by subtracting the lower bound from edge capacities and adjusting node balances, then solve the feasible circulation problem. These techniques are detailed in 网络流建模_周尚彦.pdf.

Which max-flow algorithm should I use for competitive programming?

Dinic's algorithm with scaling or current-arc optimization offers $O(V^2E)$ complexity and performs well on dense graphs typical of combinatorial problems. For unit-capacity networks, Edmonds-Karp ($O(VE^2)$) suffices for smaller instances. The lecture notes 网络流_周聿浩 & 黄哲威.pdf provide complexity analysis and implementation details for these algorithms.

Where can I find practice problems to master flow graph modeling?

The hzwer/shareoi repository includes 图论基础与网络流习题集锦_朱睿.pptx, a curated collection of practice problems with step-by-step flow model constructions. Additionally, the visual examples in 网络流_魏越闽.ppt demonstrate how to approach classic competitive programming challenges using network flow techniques.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}