Network flow, min cut আর bipartite matching

১ · সমস্যা — চট্টগ্রাম বন্দর থেকে ঢাকার গুদামে কত ট্রাক?

চট্টগ্রাম বন্দরে একটি জাহাজ ভিড়েছে, তাতে হাজার হাজার কনটেইনার। সব যেতে হবে ঢাকার গুদামে। মাঝে কয়েকটি শহর আর তাদের মধ্যে মহাসড়ক — কিন্তু প্রতিটি রাস্তায় ঘণ্টায় নির্দিষ্ট সংখ্যার বেশি ট্রাক চলতে পারে না: সরু রাস্তা, ফেরিঘাট, সেতুর ওজন-সীমা। পরিবহন ব্যবস্থাপক জানতে চান: ঘণ্টায় সর্বোচ্চ কতগুলো ট্রাক বন্দর থেকে ঢাকায় পাঠানো যায়, আর কোন রাস্তা দিয়ে কয়টি?

প্রশ্নটি সংক্ষিপ্ত পথের প্রশ্ন নয় (সেটি পর্ব ৪৩-এর Dijkstra). এখানে প্রতিটি ট্রাক কত দ্রুত পৌঁছাল তা নয়, একসাথে কতটা মাল চলতে পারে তা জানতে চাই — অনেকগুলো পথ ভাগাভাগি করে। একই কাঠামো সবখানে: ওয়াসার পানির পাইপলাইনে প্রতিটি পাইপের ব্যাস একটি সীমা দেয়; ইন্টারনেটে সাবমেরিন কেবল থেকে ঢাকার ডেটা সেন্টারে যেতে প্রতিটি লিংকের bandwidth সীমিত; বিদ্যুতের গ্রিডে প্রতিটি লাইনের সীমা আছে। সব প্রশ্ন একটাই: “উৎস থেকে গন্তব্যে সর্বোচ্চ কতটা প্রবাহ সম্ভব?”

সংজ্ঞা — flow network

একটি flow network হলো একটি directed graph G = (V, E), যেখানে প্রতিটি edge (u, v)-এর একটি অঋণাত্মক capacity c(u, v) আছে, আর দুটি বিশেষ vertex: source s (যেখান থেকে প্রবাহ শুরু) আর sink t (যেখানে শেষ)। যে জোড়ার মধ্যে edge নেই, তার capacity ০ ধরা হয়। একটি flow হলো প্রতিটি edge-এ একটি সংখ্যা f(u, v), যা দুটি শর্ত মানে:

• Capacity constraint: প্রতিটি edge-এ 0 ≤ f(u, v) ≤ c(u, v) — কোনো রাস্তায় তার সীমার বেশি ট্রাক নয়।
• Flow conservation: s আর t ছাড়া প্রতিটি vertex v-তে, v-তে যত প্রবাহ ঢোকে, ঠিক তত বের হয়: Σ_u f(u, v) = Σ_w f(v, w). ফেনী বা কুমিল্লায় ট্রাক জমেও থাকে না, হঠাৎ তৈরিও হয় না।

Flow-এর মান |f| = s থেকে বের হওয়া মোট প্রবাহ − s-এ ঢোকা মোট প্রবাহ (সাধারণত দ্বিতীয়টি ০)। Conservation-এর কারণে এটি t-তে ঢোকা মোট প্রবাহের সমান। Maximum flow সমস্যা: সবচেয়ে বড় |f|-এর একটি বৈধ flow খুঁজুন। ওপরের ছবিতে S থেকে বের হওয়ার রাস্তা দুটি, মোট capacity 10 + 4 = 14 — তাই উত্তর ১৪-এর বেশি হতেই পারে না। কিন্তু এটিই কি উত্তর? ফেনী থেকে বের হওয়ার রাস্তা মাত্র 3 + 6 = 9, তাই S → F রাস্তার 10 পুরো ব্যবহার করা যাবে না। এই পর্ব শেষে দেখবেন উত্তর ১৩, আর কেন ১৩-এর বেশি অসম্ভব তার একটি ছোট “সার্টিফিকেট”ও পাবেন।

কোডে নেটওয়ার্ক রাখার দুটি উপায় পর্ব ৩৯-এ দেখেছেন: adjacency matrix (n × n অ্যারে, cap[u][v]) আর adjacency list. ছোট উদাহরণে matrix সবচেয়ে সহজ, আর এই পর্বের প্রথম কোডে সেটিই ব্যবহার করব; বড় গ্রাফে (V = 10⁴, E = 10⁵) list লাগে, কারণ matrix-এর Θ(V²) জায়গা আর প্রতি vertex-এ Θ(V) সময়ের scan তখন অচল।

২ · Greedy কেন আটকে যায় — residual graph আর ফেরত edge

প্রথম স্বাভাবিক চিন্তা: s থেকে t-তে এমন একটি পথ খুঁজুন, যার সব edge-এ এখনো জায়গা আছে; পথের সবচেয়ে কম জায়গাটুকু (bottleneck) পরিমাণ প্রবাহ পাঠান; আবার খুঁজুন; পথ না পাওয়া পর্যন্ত চালিয়ে যান। এটি একটি greedy পদ্ধতি — আর এটি ভুল উত্তর দিতে পারে। চারটি vertex-এর একটি ছোট নেটওয়ার্ক নিন: s → a, s → b, a → b, a → t, b → t, প্রতিটির capacity 10. সর্বোচ্চ প্রবাহ স্পষ্টতই ২০ (s → a → t আর s → b → t). কিন্তু ধরুন প্রথম পথটি দুর্ভাগ্যক্রমে s → a → b → t বাছা হলো।

সমাধানের চাবি একটি ধারণা: residual graph G_f. বর্তমান flow f-এর জন্য প্রতিটি edge (u, v) থেকে দুটি সম্ভাবনা আসে:

• এগোনো edge u → v, residual capacity c(u, v) − f(u, v): আরও কতটা পাঠানো যায়।
• ফেরত edge (reverse edge) v → u, residual capacity f(u, v): ইতিমধ্যে পাঠানো প্রবাহের কতটা “ফিরিয়ে নেওয়া” যায়।

Residual graph-এ শুধু ধনাত্মক residual capacity-র edge থাকে। সেখানে s থেকে t-এর যেকোনো পথকে বলে augmenting path. পথটি কোনো ফেরত edge v → u ব্যবহার করলে আসলে মূল edge u → v-এর প্রবাহ কমানো হয় — অর্থাৎ আগের একটি সিদ্ধান্ত আংশিক বাতিল। নিচের ডায়াগ্রামে দেখুন, এই “বাতিল” কীভাবে greedy-র আটকে যাওয়া ঠিক করে।

একটি খুঁটিনাটি: augmenting path দিয়ে প্রবাহ বাড়ালে দুটি শর্তই বজায় থাকে। পথের প্রতিটি মাঝের vertex-এ একটি edge দিয়ে Δ ঢোকে আর একটি দিয়ে Δ বের হয় (ফেরত edge হলে “ঢোকা কমে”, যার হিসাবও মেলে), তাই conservation ঠিক থাকে; আর Δ ≤ bottleneck বলে কোনো edge capacity ছাড়ায় না বা ঋণাত্মক হয় না। প্রতিবার |f| ঠিক Δ বাড়ে, কারণ পথের প্রথম edge s থেকে বের হয়।

৩ · Ford-Fulkerson পদ্ধতি — augmenting path যতক্ষণ আছে

ওপরের ধারণাটিই Ford-Fulkerson পদ্ধতি. একে “অ্যালগরিদম” না বলে “পদ্ধতি” বলা হয়, কারণ augmenting path কীভাবে খোঁজা হবে তা এটি বলে না — DFS, BFS বা অন্য কিছু, যেকোনোটি চলে।

Pseudocode — Ford-Fulkerson method (vertices 0-based, s and t given)

f(u, v) = 0 for every edge
while the residual graph G_f has a path P from s to t:      // augmenting path
    delta = min residual capacity on P                       // bottleneck
    for each edge (u, v) on P:
        if (u, v) is a forward edge:  f(u, v) += delta
        else:                         f(v, u) -= delta       // cancel old flow
return f                                                     // f is a maximum flow

কতক্ষণ চলে?

সব capacity integer হলে প্রতিটি bottleneck অন্তত ১, তাই প্রতিটি ধাপে |f| অন্তত ১ বাড়ে। সর্বোচ্চ প্রবাহ |f*| হলে সর্বোচ্চ |f*| টি ধাপ, আর প্রতিটি ধাপে একটি DFS বা BFS — O(E). মোট O(E · |f*|). এটি একটি pseudo-polynomial সীমা: ইনপুটের আকার নয়, ইনপুটের সংখ্যার মান-এর ওপর নির্ভর করে। ক্লাসিক খারাপ উদাহরণ: অংশ ২-এর চার-vertex নেটওয়ার্ক, কিন্তু বাইরের চারটি edge-এর capacity 10⁶ আর মাঝের a → b-এর মাত্র 1. দুর্ভাগ্যক্রমে DFS যদি বারবার মাঝের edge দিয়ে যায় (একবার a → b, পরেরবার ফেরত b → a), প্রতিটি পথ মাত্র ১ বাড়ায় — সর্বোচ্চ 2 × 10⁶ প্রবাহে পৌঁছাতে ২০ লাখ ধাপ, যেখানে সঠিক দুটি পথে দুই ধাপেই হতো।

আরও খারাপ: capacity অমূলদ (irrational) হলে Ford-Fulkerson কখনো না-ও থামতে পারে — প্রতিটি পথ আগেরটির চেয়ে ছোট বাড়ায়, আর প্রবাহ এমনকি সর্বোচ্চের চেয়ে কম একটি মানের দিকে এগোতে থাকে। Ford আর Fulkerson নিজেই এমন একটি উদাহরণ দিয়েছিলেন। Integer (বা মূলদ, যাকে integer-এ গুণ করে নেওয়া যায়) capacity-তে এই সমস্যা নেই। কম্পিউটারে সাধারণত integer-ই থাকে, কিন্তু floating-point capacity দিলে সাবধান।

৪ · Edmonds-Karp — BFS দিয়ে সবচেয়ে ছোট augmenting path

১৯৭২ সালে Jack Edmonds আর Richard Karp একটি সরল নিয়ম দেন: প্রতিবার residual graph-এ BFS চালিয়ে সবচেয়ে কম edge-এর augmenting path নিন। এটিই Edmonds-Karp অ্যালগরিদম. প্রায় একই ধারণা (আরও উন্নত রূপে) ১৯৭০ সালেই সোভিয়েত গবেষক Yefim Dinitz প্রকাশ করেছিলেন — সেটি অংশ ৬-এ। মূল উদাহরণে চালিয়ে দেখুন:

কোড — প্রতিটি augmenting path, max flow আর min cut

নিচের কোড ছয়টি জায়গা আর নয়টি রাস্তার নেটওয়ার্কে Edmonds-Karp চালায়। Residual capacity একটি adjacency matrix cap-এ: পথ দিয়ে Δ পাঠালে cap[u][v] -= Δ আর cap[v][u] += Δ — দ্বিতীয় লাইনটিই ফেরত edge খোলে। শেষ BFS (যেটি t-তে পৌঁছায়নি) যাদের ছুঁয়েছে, তারাই min cut-এর S-পাশ।

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
int main() {
    vector<string> names = {"Port", "Feni", "Chandpur", "Cumilla", "Munshiganj", "Dhaka"};
    vector<tuple<int, int, int>> edges = {{0, 1, 10}, {0, 2, 4}, {1, 2, 3}, {1, 3, 6}, {2, 3, 2},
                                          {2, 4, 5}, {3, 4, 4}, {3, 5, 8}, {4, 5, 10}};
    const int n = 6, s = 0, t = 5;
    vector<vector<int>> cap(n, vector<int>(n, 0));           // residual capacities
    for (auto [u, v, c] : edges) cap[u][v] += c;
    int flow = 0, step = 0; vector<int> par(n);
    while (true) {
        fill(par.begin(), par.end(), -1); par[s] = s;        // BFS: shortest augmenting path
        queue<int> q({s});
        while (!q.empty() && par[t] == -1) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; ++v)
                if (par[v] == -1 && cap[u][v] > 0) { par[v] = u; q.push(v); }
        }
        if (par[t] == -1) break;                             // no augmenting path: flow is maximum
        vector<int> path = {t}; while (path.back() != s) path.push_back(par[path.back()]);
        reverse(path.begin(), path.end());
        int push = cap[s][path[1]];
        for (size_t i = 1; i + 1 < path.size(); ++i) push = min(push, cap[path[i]][path[i + 1]]);
        flow += push;
        cout << "path " << ++step << ": " << names[s];
        for (size_t i = 0; i + 1 < path.size(); ++i) {
            cap[path[i]][path[i + 1]] -= push;               // use forward capacity
            cap[path[i + 1]][path[i]] += push;               // open the cancelling back edge
            cout << " -> " << names[path[i + 1]];
        }
        cout << " | push " << push << '\n';
    }
    cout << "max flow = " << flow << "\nmin cut:"; string sep = " ";   // last BFS reached side S
    for (auto [u, v, c] : edges)
        if (par[u] != -1 && par[v] == -1) { cout << sep << names[u] << "->" << names[v] << " (" << c << ")"; sep = ", "; }
    cout << '\n';
}

path 1: Port -> Feni -> Cumilla -> Dhaka | push 6
path 2: Port -> Chandpur -> Cumilla -> Dhaka | push 2
path 3: Port -> Chandpur -> Munshiganj -> Dhaka | push 2
path 4: Port -> Feni -> Chandpur -> Munshiganj -> Dhaka | push 3
max flow = 13
min cut: Port->Chandpur (4), Feni->Chandpur (3), Feni->Cumilla (6)

from collections import deque
names = ["Port", "Feni", "Chandpur", "Cumilla", "Munshiganj", "Dhaka"]
edges = [(0, 1, 10), (0, 2, 4), (1, 2, 3), (1, 3, 6), (2, 3, 2),
         (2, 4, 5), (3, 4, 4), (3, 5, 8), (4, 5, 10)]
n, s, t = len(names), 0, 5
cap = [[0] * n for _ in range(n)]          # residual capacities
for u, v, c in edges:
    cap[u][v] += c
flow, step = 0, 0
while True:
    par = [-1] * n                         # BFS: shortest augmenting path
    par[s] = s
    q = deque([s])
    while q and par[t] == -1:
        u = q.popleft()
        for v in range(n):
            if par[v] == -1 and cap[u][v] > 0:
                par[v] = u
                q.append(v)
    if par[t] == -1:
        break                              # no augmenting path: flow is maximum
    path = [t]
    while path[-1] != s:
        path.append(par[path[-1]])
    path.reverse()
    push = min(cap[a][b] for a, b in zip(path, path[1:]))   # bottleneck
    for a, b in zip(path, path[1:]):
        cap[a][b] -= push                  # use forward capacity
        cap[b][a] += push                  # open the cancelling back edge
    flow, step = flow + push, step + 1
    print(f"path {step}:", " -> ".join(names[x] for x in path), f"| push {push}")

print("max flow =", flow)
cut = [f"{names[u]}->{names[v]} ({c})" for u, v, c in edges if par[u] != -1 and par[v] == -1]
print("min cut:", ", ".join(cut))         # last BFS reached exactly side S

path 1: Port -> Feni -> Cumilla -> Dhaka | push 6
path 2: Port -> Chandpur -> Cumilla -> Dhaka | push 2
path 3: Port -> Chandpur -> Munshiganj -> Dhaka | push 2
path 4: Port -> Feni -> Chandpur -> Munshiganj -> Dhaka | push 3
max flow = 13
min cut: Port->Chandpur (4), Feni->Chandpur (3), Feni->Cumilla (6)

কেন O(VE²) — প্রমাণের নকশা

δ_f(s, v) দিয়ে বোঝাই residual graph G_f-এ s থেকে v-এর সবচেয়ে কম edge-এর পথের দৈর্ঘ্য। যুক্তিটি দুই ধাপের।

1. দূরত্ব কখনো কমে না। প্রতিটি augmentation-এর পর প্রতিটি v-এর জন্য δ(s, v) হয় একই থাকে, নয় বাড়ে। কারণ: BFS-এর পথ সবসময় এক স্তর থেকে পরের স্তরে যায় (δ(v) = δ(u) + 1). Augmentation নতুন যে edge খোলে, তা কেবল ফেরত edge v → u — যা এক স্তর পেছনে যায়। পেছনে যাওয়া edge কোনো শর্টকাট বানাতে পারে না। (আনুষ্ঠানিক প্রমাণ contradiction দিয়ে: যে v-এর দূরত্ব প্রথম কমল, তার আগের vertex নিয়ে।)
2. প্রতিটি edge সর্বোচ্চ O(V) বার “critical”. যে edge (u, v) একটি পথের bottleneck, সে ভরে যায় আর residual থেকে উধাও হয় — তাকে বলে critical. আবার ফিরতে হলে পরে কোনো পথকে v → u দিয়ে যেতে হবে; তখন δ(u) = δ(v) + 1 ≥ (আগের δ(u) + 1) + 1. অর্থাৎ দুবার critical হওয়ার মাঝে δ(s, u) অন্তত ২ বাড়ে। δ সর্বোচ্চ V − 1, তাই একটি edge সর্বোচ্চ প্রায় V/2 বার critical.

প্রতিটি augmentation-এ অন্তত একটি edge critical, আর residual-এ edge সর্বোচ্চ 2E টি — তাই মোট augmentation O(VE). প্রতিটি BFS O(E) (adjacency list-এ)। মোট সময় O(VE²), জায়গা O(V + E). সবচেয়ে বড় কথা: সীমাটি capacity-র মানের ওপর নির্ভর করে না — অংশ ৩-এর 10⁶ উদাহরণে Edmonds-Karp প্রথমেই দুটি ২-edge-এর পথ নিয়ে দুই ধাপে শেষ করে।

৫ · Max-flow min-cut theorem — সবচেয়ে সরু গলা

একটি s-t cut (S, T) হলো vertex-গুলোকে দুই ভাগে ভাগ করা, যাতে s ∈ S আর t ∈ T. Cut-এর capacity c(S, T) = S থেকে T-তে যাওয়া সব edge-এর capacity-র যোগফল — T থেকে S-এ ফেরার edge গোনা হয় না। উপমায়: বন্দর আর ঢাকার মাঝে একটি কাল্পনিক রেখা টানুন; রেখা পার হয়ে ঢাকার দিকে যাওয়া রাস্তাগুলোর মোট ধারণক্ষমতাই cut-এর capacity. সবচেয়ে ছোট capacity-র cut হলো minimum cut.

দুর্বল দ্বৈততা (weak duality): যেকোনো flow f আর যেকোনো cut (S, T)-এর জন্য |f| ≤ c(S, T). কারণ: conservation থেকে |f| = (S থেকে T-তে মোট প্রবাহ) − (T থেকে S-এ মোট প্রবাহ) — প্রতিটি s-t প্রবাহকে কোথাও রেখা পার হতে হয়। প্রথম পদ ≤ c(S, T), দ্বিতীয় পদ ≥ ০. তাই যেকোনো cut একটি ওপরের সীমা দেয়। অংশ ১-এ S থেকে বের হওয়া ১৪ ছিল cut {S}-এর capacity; F-কে S-এর পাশে নিলে সীমা নামে ১৩-এ।

Max-flow min-cut theorem (Ford ও Fulkerson; Elias, Feinstein ও Shannon — ১৯৫৬): একটি flow f-এর জন্য নিচের তিনটি বক্তব্য সমতুল্য —

1. f একটি maximum flow.
2. Residual graph G_f-এ কোনো augmenting path নেই।
3. কোনো cut (S, T)-এর জন্য |f| = c(S, T).

প্রমাণের ধারণা. (১ ⇒ ২): augmenting path থাকলে তা দিয়ে প্রবাহ বাড়ানো যেত, তাই f সর্বোচ্চ হতো না। (৩ ⇒ ১): weak duality বলে কোনো flow c(S, T) ছাড়াতে পারে না; f সেই সীমা ছুঁয়েছে, তাই সর্বোচ্চ। মূল অংশ (২ ⇒ ৩): ধরুন augmenting path নেই। S = residual graph-এ s থেকে যাওয়া যায় এমন সব vertex, T = বাকিরা; t ∈ T, কারণ পথ নেই। এখন S থেকে T-তে যেকোনো মূল edge (u, v) নিন: এটি অবশ্যই ভরা (f = c), নইলে residual-এ u → v থাকত আর v-ও S-এ পড়ত। আর T থেকে S-এ যেকোনো মূল edge (v, u)-এ প্রবাহ অবশ্যই ০, নইলে ফেরত edge u → v residual-এ থাকত। তাহলে |f| = c(S, T) − 0. ∎ এই প্রমাণই অ্যালগরিদম: শেষ residual graph-এ s থেকে একটি BFS/DFS চালালেই min cut — ঠিক যা কোডের শেষ লাইনগুলো করেছে।

Integrality theorem — প্রবাহও integer

সব capacity integer হলে Ford-Fulkerson-এর প্রতিটি bottleneck integer, তাই প্রতিটি ধাপের পর প্রতিটি edge-এর প্রবাহ integer থাকে। ফল — integrality theorem: integer capacity-র নেটওয়ার্কে এমন একটি maximum flow আছে, যার প্রতিটি edge-এর প্রবাহ integer, আর Ford-Fulkerson-ধাঁচের যেকোনো অ্যালগরিদম ঠিক সেটিই দেয়। কথাটি নিরীহ শোনালেও এটিই পরের অংশগুলোর ভিত্তি: capacity 1 হলে প্রতিটি edge-এর প্রবাহ ০ বা ১ — “এই ছাত্র এই প্রজেক্ট পাবে কি না” ধরনের হ্যাঁ/না সিদ্ধান্ত। (সাবধান: এর মানে এই নয় যে সব maximum flow integer; মাঝামাঝি ভগ্নাংশের flow-ও সর্বোচ্চ হতে পারে।)

গভীরে তাকালে max-flow min-cut theorem আসলে linear programming duality-র একটি বিশেষ রূপ: max flow একটি linear program, আর তার dual হলো min cut-এর একটি linear program — দুইয়ের সর্বোত্তম মান সমান।

৬ · Dinic — level graph আর blocking flow

Edmonds-Karp প্রতিটি পথের জন্য নতুন BFS চালায় — একই দৈর্ঘ্যের দশটি পথ থাকলে দশটি BFS. Dinic-এর অ্যালগরিদম (Yefim Dinitz, ১৯৭০; পশ্চিমে “Dinic” বানানে পরিচিত) একটি BFS দিয়ে একই দৈর্ঘ্যের সব পথ একসাথে শেষ করে। প্রতিটি phase-এ দুটি কাজ:

1. BFS → level graph. Residual graph-এ s থেকে BFS চালিয়ে প্রতিটি vertex-এর level (দূরত্ব) বের করুন। Level graph-এ রাখুন শুধু সেই residual edge u → v, যেখানে level(v) = level(u) + 1 — অর্থাৎ শুধু “এক ধাপ সামনে” যাওয়া edge. t-তে পৌঁছানো না গেলে থামুন।
2. DFS → blocking flow. Level graph-এ DFS দিয়ে বারবার s থেকে t-তে পথ খুঁজে প্রবাহ পাঠান, যতক্ষণ না level graph-এ s থেকে t-তে আর কোনো পথ থাকে না। এমন প্রবাহকে বলে blocking flow — প্রতিটি s-t পথে অন্তত একটি edge ভরা। কৌশল: প্রতিটি vertex একটি current arc pointer রাখে — যে edge দিয়ে আর যাওয়া যায় না (ভরা বা কানাগলি), তাকে এই phase-এ আর কখনো দেখা হয় না।

Pseudocode — Dinic (0-based; level[], it[] are arrays over vertices)

maxflow = 0
while bfs_levels(s) reaches t:                 // phase: build level graph
    it[v] = first edge of v, for every v        // current-arc pointers
    while (d = dfs(s, INF)) > 0: maxflow += d   // blocking flow
return maxflow

dfs(u, pushed):
    if u == t: return pushed
    for (; it[u] < deg(u); it[u]++):            // never revisit a dead edge
        e = edge it[u] of u, going to v
        if level[v] == level[u] + 1 and rescap(e) > 0:
            d = dfs(v, min(pushed, rescap(e)))
            if d > 0: rescap(e) -= d; rescap(reverse(e)) += d; return d
    return 0

জটিলতা — O(V²E), আর unit নেটওয়ার্কে আরও কম

• Phase-এর সংখ্যা ≤ V − 1. Blocking flow-এর পর level graph-এর প্রতিটি সবচেয়ে ছোট পথে একটি edge ভরা; নতুন edge আসে শুধু ফেরত edge হিসেবে, যারা level-এ পেছনে যায়। তাই পরের phase-এ s থেকে t-র দূরত্ব কঠোরভাবে বাড়ে (ওপরে 3 → 4). দূরত্ব ১ থেকে V − 1-এর মধ্যে, তাই phase সর্বোচ্চ V − 1 টি।
• এক phase O(VE). প্রতিটি সফল DFS অন্তত একটি edge ভরায় (সর্বোচ্চ E টি পথ), আর প্রতিটি পথ O(V) দৈর্ঘ্যের। ব্যর্থ হাঁটাগুলোর মোট খরচ O(E), কারণ current arc প্রতিটি মৃত edge একবারই পার হয়। মোট O(VE + E) = O(VE).
• মোট O(V²E), জায়গা O(V + E). Unit-capacity নেটওয়ার্কে (সব capacity 1) সীমা নামে O(E · min(√E, V^2/3)), আর bipartite matching-এর নেটওয়ার্কে (প্রতিটি মাঝের vertex-এ একটি ঢোকা বা একটি বের হওয়ার edge) O(E√V) — Hopcroft-Karp-এর সমান।

বাস্তবে Dinic তাত্ত্বিক সীমার চেয়ে অনেক দ্রুত চলে, তাই কনটেস্টে (V কয়েক হাজার, E কয়েক লাখ) এটিই প্রায় সবার প্রথম পছন্দ। Edmonds-Karp বোঝা আর প্রমাণ করা সহজ — পরীক্ষার জন্য; Dinic লেখা প্রায় সমান সহজ, কিন্তু অনেক দ্রুত — কাজের জন্য।

৭ · Bipartite matching — ছাত্রদের প্রজেক্ট ভাগ করা

একটি প্রশিক্ষণ কেন্দ্রে চারজন শিক্ষার্থী — রাফি, নাদিয়া, তানভীর আর মিতু — আর চারটি প্রজেক্ট: Web, Robot, App, Data. প্রত্যেক শিক্ষার্থী কয়েকটি প্রজেক্টে কাজ করতে রাজি, আর প্রতিটি প্রজেক্টে ঠিক একজন। সবচেয়ে বেশি কতজনকে তাদের পছন্দের প্রজেক্ট দেওয়া যায়? চাকরির মেলায় প্রার্থী আর পদ, হাসপাতালে ডাক্তার আর শিফট, বিমানবন্দরে ফ্লাইট আর গেট — একই প্রশ্ন।

এটি একটি bipartite graph: বাঁ পাশে শিক্ষার্থী (L), ডান পাশে প্রজেক্ট (R), আর edge মানে “রাজি”. একটি matching হলো এমন কিছু edge, যাদের কোনো দুটি একই vertex ছোঁয় না। সবচেয়ে বেশি edge-এর matching হলো maximum matching; সবাই জোড়া পেলে perfect matching.

Flow-তে রূপান্তর

একটি নতুন source s আর sink t যোগ করুন। s → প্রতিটি শিক্ষার্থী, capacity 1 (একজন শিক্ষার্থী একটিই প্রজেক্ট); শিক্ষার্থী → রাজি থাকা প্রজেক্ট, capacity 1; প্রতিটি প্রজেক্ট → t, capacity 1 (একটি প্রজেক্টে একজন)। Maximum flow = maximum matching. একটি matching থেকে সহজেই সমান মানের একটি flow পাওয়া যায়; উল্টো দিকে integrality theorem বলে একটি integer max flow আছে, যেখানে প্রতিটি edge-এ ০ বা ১ — আর প্রবাহ ১ বহন করা মাঝের edge-গুলোই একটি matching, কারণ প্রতিটি শিক্ষার্থীতে ঢোকে সর্বোচ্চ ১, প্রতিটি প্রজেক্ট থেকে বের হয় সর্বোচ্চ ১.

Kuhn-এর অ্যালগরিদম — augmenting path সরাসরি

পুরো flow নেটওয়ার্ক না বানিয়েও একই কাজ করা যায়। Kuhn-এর অ্যালগরিদম-এ প্রতিটি শিক্ষার্থীর জন্য একটি DFS: তার পছন্দের প্রজেক্ট p খালি হলে সেটি তাকে দিন; খালি না হলে p-এর বর্তমান মালিককে জিজ্ঞেস করুন “অন্য কোনো প্রজেক্টে সরা যায় কি?” — recursive ভাবে। এই শিকলটিই flow নেটওয়ার্কের একটি augmenting path: matched edge-গুলো ফেরত edge হিসেবে ব্যবহার হয়, আর পথ পাওয়া গেলে শিকলের প্রত্যেকে এক ঘর সরে।

#include <cstdio>
#include <string>
#include <vector>
using namespace std;
vector<string> students = {"Rafi", "Nadia", "Tanvir", "Mitu"};
vector<string> projects = {"Web", "Robot", "App", "Data"};
vector<vector<int>> likes = {{0, 1}, {0}, {1, 2, 3}, {2}};   // project ids each student accepts
vector<int> owner(4, -1);                                      // owner[p] = student holding project p

bool tryKuhn(int st, vector<bool>& seen) {
    for (int p : likes[st]) {
        if (seen[p]) continue;
        seen[p] = true;
        // p is free, or its owner can move to another project
        if (owner[p] == -1 || tryKuhn(owner[p], seen)) { owner[p] = st; return true; }
    }
    return false;
}
int main() {
    int matched = 0;
    for (int st = 0; st < 4; ++st) {
        vector<bool> seen(4, false);
        bool ok = tryKuhn(st, seen);
        matched += ok;
        printf("%-6s %s |", students[st].c_str(), ok ? "matched" : "no path");
        const char* sep = " ";
        for (int p = 0; p < 4; ++p)
            if (owner[p] != -1) { printf("%s%s-%s", sep, students[owner[p]].c_str(), projects[p].c_str()); sep = ", "; }
        printf("\n");
    }
    printf("maximum matching = %d\n", matched);
}

Rafi   matched | Rafi-Web
Nadia  matched | Nadia-Web, Rafi-Robot
Tanvir matched | Nadia-Web, Rafi-Robot, Tanvir-App
Mitu   matched | Nadia-Web, Rafi-Robot, Mitu-App, Tanvir-Data
maximum matching = 4

students = ["Rafi", "Nadia", "Tanvir", "Mitu"]
projects = ["Web", "Robot", "App", "Data"]
likes = [[0, 1], [0], [1, 2, 3], [2]]     # project ids each student accepts
owner = [-1] * len(projects)              # owner[p] = student holding project p

def try_kuhn(st, seen):
    for p in likes[st]:
        if not seen[p]:
            seen[p] = True
            # p is free, or its owner can move to another project
            if owner[p] == -1 or try_kuhn(owner[p], seen):
                owner[p] = st
                return True
    return False

matched = 0
for st in range(len(students)):
    ok = try_kuhn(st, [False] * len(projects))
    matched += ok
    pairs = [f"{students[owner[p]]}-{projects[p]}"
             for p in range(len(projects)) if owner[p] != -1]
    print(f"{students[st]:6} {'matched' if ok else 'no path'} | {', '.join(pairs)}")
print("maximum matching =", matched)

Rafi   matched | Rafi-Web
Nadia  matched | Nadia-Web, Rafi-Robot
Tanvir matched | Nadia-Web, Rafi-Robot, Tanvir-App
Mitu   matched | Nadia-Web, Rafi-Robot, Mitu-App, Tanvir-Data
maximum matching = 4

Hopcroft-Karp, Hall আর König

Hopcroft-Karp অ্যালগরিদম (John Hopcroft ও Richard Karp, ১৯৭৩) Dinic-এর ধারণাই matching-এ প্রয়োগ করে: প্রতিটি phase-এ BFS দিয়ে সবচেয়ে ছোট augmenting path-গুলোর দৈর্ঘ্য বের করে, তারপর সেই দৈর্ঘ্যের পরস্পর-বিচ্ছিন্ন সব পথ একসাথে নেয়। O(√V) টি phase যথেষ্ট, মোট O(E√V). V = 10⁵, E = 10⁶-এর মতো ইনপুটে Kuhn-এর O(VE)-র তুলনায় এটিই চলে।

কখন perfect matching অসম্ভব? Hall-এর theorem (Philip Hall, ১৯৩৫): বাঁ পাশের সবাইকে জোড়া দেওয়া যায় ঠিক তখনই, যখন বাঁ পাশের প্রতিটি উপসেট A-এর জন্য A-এর পছন্দের মোট প্রজেক্ট-সংখ্যা ≥ |A|. ওপরের উদাহরণে Tanvir যদি Data না চাইতেন, তাহলে চারজনের পছন্দ মিলিয়ে মাত্র তিনটি প্রজেক্ট (Web, Robot, App) — A = চারজনই নিলে Hall-এর শর্ত ভাঙে, perfect matching অসম্ভব।

একটি vertex cover হলো এমন vertex-এর সেট, যা প্রতিটি edge-এর অন্তত এক প্রান্ত ছোঁয়। প্রতিটি matching edge-কে আলাদা vertex দিয়ে ঢাকতে হয়, তাই যেকোনো গ্রাফে matching ≤ vertex cover. König-এর theorem (Dénes Kőnig, ১৯৩১): bipartite গ্রাফে maximum matching-এর আকার = minimum vertex cover-এর আকার. প্রমাণ max-flow min-cut থেকেই আসে: শেষ residual graph-এ s থেকে যাওয়া যায় এমন সেট Z নিন; তাহলে (L \ Z) ∪ (R ∩ Z) একটি vertex cover, আর তার আকার min cut-এর capacity = max matching. সাধারণ (bipartite নয়) গ্রাফে minimum vertex cover NP-hard (পর্ব ৬৪, ৬৬) — bipartite কাঠামোই সমস্যাটিকে সহজ করে।

৮ · আরও প্রয়োগ — edge-disjoint path আর project selection

Edge-disjoint path — নেটওয়ার্ক কতটা মজবুত

একটি অফিসের দুটি রাউটারের মধ্যে এমন কয়টি পথ আছে, যাদের কোনো দুটি একই কেবল ভাগ করে না? প্রতিটি edge-এর capacity 1 দিয়ে max flow চালান: integrality-র কারণে প্রবাহ ০/১, আর প্রবাহ বহন করা edge-গুলো ঠিক |f| টি edge-disjoint path-এ ভাগ হয়। উল্টো দিকে, min cut = সবচেয়ে কম কয়টি কেবল কাটলে দুই রাউটার বিচ্ছিন্ন হয়। দুই মিলে Menger-এর theorem (Karl Menger, ১৯২৭): edge-disjoint পথের সর্বোচ্চ সংখ্যা = s আর t-কে বিচ্ছিন্ন করতে সবচেয়ে কম যতগুলো edge সরাতে হয়। Vertex-disjoint পথ চাইলে প্রতিটি vertex v-কে দুই ভাগ করুন — v_in → v_out, capacity 1 — যাতে প্রতিটি vertex একটিই পথ বহন করে। Undirected গ্রাফে প্রতিটি edge-কে দুই দিকে capacity 1-এর দুটি directed edge বানালেই চলে।

Project selection — min cut দিয়ে লাভ সর্বোচ্চ

ঢাকার একটি সফটওয়্যার ফার্ম দুটি প্রজেক্টের কথা ভাবছে। প্রজেক্ট P1 (লাভ ৯ লাখ টাকা) চালাতে লাগবে সার্ভার A (খরচ ৪) আর লাইসেন্স B (খরচ ৩); প্রজেক্ট P2 (লাভ ৫) লাগবে B আর প্রশিক্ষণ C (খরচ ৪)। কোনগুলো নিলে নিট লাভ সর্বোচ্চ? শুধু P1: 9 − 7 = 2. শুধু P2: 5 − 7 = −2, লোকসান। দুটিই: 14 − 11 = 3 — কারণ B ভাগাভাগি হয়। এই project selection (বা maximum closure) সমস্যা min cut দিয়ে সমাধান হয়:

• s → প্রতিটি প্রজেক্ট, capacity = তার লাভ; প্রতিটি সরঞ্জাম → t, capacity = তার খরচ।
• প্রজেক্ট → তার দরকারি প্রতিটি সরঞ্জাম, capacity ∞ — যাতে এই edge কখনো cut-এ না পড়ে: প্রজেক্ট নিলে তার সরঞ্জামও নিতে হবে।
• যেকোনো সীমিত cut (S, T)-এ S-এর প্রজেক্ট আর সরঞ্জামগুলোই “বাছাই”; cut-এর capacity = (না-নেওয়া প্রজেক্টের লাভ) + (নেওয়া সরঞ্জামের খরচ)। তাই সর্বোচ্চ নিট লাভ = সব লাভের যোগফল − min cut. এখানে 14 − 11 = 3.

একই ছাঁচে পড়ে “কোন কাজগুলো একসাথে করা যায়, পূর্বশর্ত মেনে”, খনিতে কোন ব্লকগুলো খুঁড়লে লাভ (open-pit mining), আর ছবি থেকে সামনের বস্তু আলাদা করা (image segmentation, ভাবনার প্রশ্ন ৪)। কোডে ∞-কে একটি বড় সংখ্যা (যেমন 10¹⁸) দিন, যা সব লাভের যোগফলের চেয়ে বড় — আর যোগফল long long-এ রাখুন, নইলে integer overflow.

৯ · AI-এর যুগে network flow — দেখতে ঠিক, চলতে ভুল

“Max flow-এর কোড লিখে দাও” — AI সহকারী মুহূর্তে একটি Dinic দেবে, আর ছোট উদাহরণে উত্তরও প্রায়ই ঠিক আসবে। কিন্তু flow-এর ভুলগুলো খুব নিঃশব্দ: ফেরত edge-এর index এক ঘর সরে যাওয়া, ফেরত edge-এর capacity 0-এর বদলে মূল capacity দেওয়া, বা bipartite matching-এর DFS-এ seen তালিকা প্রতিবার নতুন না করা — এগুলো compile হয়, অনেক ইনপুটে ঠিক উত্তর দেয়, আর কোনো এক অদ্ভুত ইনপুটে ভুল বা অসম্ভব ধীর হয়। আর মডেলিং-এর প্রশ্নে (“এই সমস্যাকে flow-তে রূপান্তর করো”) AI প্রায়ই একটি capacity ভুল বসায়, বা প্রমাণ ছাড়াই একটি greedy প্রস্তাব করে।

Network flow-এর কোডে AI সাধারণত যেসব ভুল করে

Flow-এর কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি augmentation-এ এগোনো edge থেকে Δ কমিয়েছি আর ফেরত edge-এ Δ বাড়িয়েছি; ফেরত edge-এর শুরুর capacity 0
• শেষে প্রতিটি মাঝের vertex-এ conservation, প্রতিটি edge-এ 0 ≤ f ≤ c, আর |f| = min cut-এর capacity — তিনটিই assert করেছি
• Edge case চালিয়েছি: s থেকে t-তে কোনো পথ নেই, s থেকে সরাসরি t-তে edge, একই জোড়ায় একাধিক edge, u → v আর v → u দুটিই আছে, capacity 0
• ছোট এলোমেলো নেটওয়ার্কে সব cut গুনে (2^V−2 টি) সবচেয়ে ছোটটির সাথে আমার max flow মিলিয়েছি — brute force দিয়ে stress testing
• মডেলিং-এ প্রতিটি capacity-র অর্থ এক বাক্যে লিখেছি (“এটি কেন 1?”, “এটি কেন ∞?”), আর integrality theorem কেন উত্তরকে বৈধ সিদ্ধান্ত বানায় তা যাচাই করেছি
• AI-এর complexity দাবিতে কোন পথ-খোঁজা (DFS, BFS, level graph) ধরা হয়েছে, তা জিজ্ঞেস করেছি