নেটওয়ার্ক ফ্লো৯ মিনিট পড়া

ম্যাক্স ফ্লো / মিন কাট (Max Flow / Min Cut)

আপনার পাইপের নেটওয়ার্ক দিয়ে কতটুকু পানি যেতে পারবে? সেটির সিদ্ধান্ত নেবে বটলনেক (bottleneck) বা সরু পথটি

Ford-Fulkerson:\(O(E · |f|)\)theorem:ম্যাক্স ফ্লো (max flow) = মিন কাট ক্যাপাসিটি (min cut capacity)Edmonds-Karp:\(O(VE^2)\)

কল্পনা করুন একটি পানির পাইপ নেটওয়ার্ক শহরের (sink) সাথে রিজার্ভার বা জলাধারকে (source) যুক্ত করেছে। প্রতিটি পাইপের নিজস্ব পানি প্রবাহের একটি সর্বোচ্চ মাত্রা আছে — যাকে এর ধারণক্ষমতা বা ক্যাপাসিটি (capacity) বলা হয়। প্রশ্ন হলো: প্রতি সেকেন্ডে নেটওয়ার্কটি দিয়ে মোট কতটুকু পানি প্রবাহিত হতে পারবে?

এটিই হলো ম্যাক্স ফ্লো প্রবলেম বা সর্বোচ্চ প্রবাহের সমস্যা। অবাক করা ব্যাপার হলো, এর উত্তর ন্যূনতম "কাট" (cut) ক্যাপাসিটির সমান হয় — অর্থাৎ সম্পূর্ণ পানি চলাচল বন্ধ করে দিতে আপনাকে সবচেয়ে কম খরচে যে পাইপগুলো কাটতে হবে, তার মোট ধারণক্ষমতার সমান। এই সম্পর্কটি কম্বিনেটরিক্সের (combinatorics) সবচেয়ে সুন্দর থিওরেমগুলোর মধ্যে একটি।

ফ্লো নেটওয়ার্ক (Flow Network) কী?

গাণিতিক ভাষায়: এটি এমন একটি নির্দেশিত গ্রাফ (directed graph) যেখানে প্রতিটি এজে (u→v) একটি ধারণক্ষমতা বা ক্যাপাসিটি c(u,v) ≥ 0 থাকে। আমরা একটি সোর্স বা উৎস (source) s এবং একটি সিংক বা গন্তব্য (sink) t বেছে নিই। একটি বৈধ ফ্লো প্রতিটি এজে f(u,v) মান নির্ধারণ করে যা নিচের শর্তগুলো মেনে চলে:

ক্যাপাসিটি কনস্ট্রেইন্ট (Capacity constraint): f(u,v) ≤ c(u,v) — পাইপের ধারণক্ষমতার চেয়ে বেশি প্রবাহিত হতে পারবে না।
সংরক্ষণ বা কনজারভেশন (Conservation): উৎস (s) এবং গন্তব্য (t) বাদে প্রতিটি ভার্টেক্সে, মোট ইনপুট ফ্লো = মোট আউটপুট ফ্লো — অর্থাৎ পানি কোথাও জমে থাকবে না বা হারিয়ে যাবে না।

ফ্লো-এর মূল মান বা value হলো s থেকে বের হওয়া মোট নেট প্রবাহ (যা সর্বদা t তে পৌঁছানো মোট নেট প্রবাহের সমান)।

অগমেন্টটিং পাথ (Augmenting Paths)

ফোর্ড-ফুলকারসন (Ford-Fulkerson) পদ্ধতি বারবার অগমেন্টটিং পাথ খোঁজার মাধ্যমে সর্বোচ্চ প্রবাহ (max flow) বের করে — এটি রেসিডিউয়াল গ্রাফের (residual graph) মধ্যে s থেকে t তে যাওয়ার এমন একটি রুট, যার প্রতিটি এজে কিছু অতিরিক্ত ধারণক্ষমতা (leftover capacity) বাকি থাকে। এরপর এই পথ দিয়ে ফ্লো বাড়ানো হয় (যা সবচেয়ে চাপা বা সংকীর্ণ পাইপের ধারণক্ষমতার সমান হয়), এবং এই প্রক্রিয়ার পুনরাবৃত্তি করা হয়।

যখন এমন কোনো অগমেন্টটিং পাথ খুঁজে পাওয়া যায় না, তখন কাজ বন্ধ হয়ে যায়। ওই বিন্দুতেই আপনি সর্বোচ্চ প্রবাহটি খুঁজে পেয়েছেন।

রেসিডিউয়াল গ্রাফ (Residual Graph) — এবং অত্যন্ত গুরুত্বপূর্ণ ব্যাকওয়ার্ড এজ (Backward Edge)

প্রতিটি পাইপের (u→v) জন্য, যদি তার ক্যাপাসিটি c এবং বর্তমান প্রবাহ f হয়, তবে রেসিডিউয়াল গ্রাফে থাকবে:

একটি ফরওয়ার্ড এজ বা সামনের দিকের এজ (forward edge) (u→v) যার বাকি ধারণক্ষমতা হলো c−f।
একটি ব্যাকওয়ার্ড এজ বা পেছনের দিকের এজ (backward edge) (v→u) যার ধারণক্ষমতা হলো f — এটি আগে থেকে পাঠিয়ে দেওয়া ফ্লো-কে "আন্ডু (undo)" করার ক্ষমতা হিসেবে কাজ করে।

ব্যাকওয়ার্ড এজগুলোই হলো আসল চালাকি বা চমক। এগুলি ছাড়া, একটি গ্রিডি (greedy) অগমেন্টটিং কৌশল ভুল বা সাবঅপ্টিমাল রুটে গিয়ে আটকে যেতে পারে। ব্যাকওয়ার্ড এজগুলো অ্যালগরিদমকে ভুল দিকে পাঠানো প্রবাহ ফিরিয়ে আনতে বা রিরাউট (reroute) করতে সাহায্য করে।

ম্যাক্স-ফ্লো মিন-কাট থিওরেম (Max-Flow Min-Cut Theorem)

একটি কাট নেটওয়ার্কের সমস্ত ভার্টেক্সকে দুটি দলে ভাগ করে দেয়: S (যাতে উৎস বা সোর্স থাকে) এবং T (যাতে গন্তব্য বা সিংক থাকে)। এর ধারণক্ষমতা বা ক্যাপাসিটি হলো S থেকে T এর দিকে যাওয়া এজগুলোর মোট ক্যাপাসিটি (বিপরীত দিকের এজগুলো এখানে হিসেবে ধরা হয় না)।

থিওরেমটি বলছে: সর্বোচ্চ ফ্লো এর মান = ন্যূনতম কাটের ক্যাপাসিটি। এই ন্যূনতম কাটটিই মূলত আপনার সম্পূর্ণ সিস্টেমের প্রবাহকে সীমাবদ্ধকারী বটলনেক বা সরু পথ। ফোর্ড-ফুলকারসনের কাজ যখন শেষ হয়, তখন রেসিডিউয়াল গ্রাফে সোর্স (s) থেকে যেসব ভার্টেক্সে পৌঁছানো যায়, তারাই দল S গঠন করে — এবং তার সাথে সম্পর্কিত কাটটিই হলো মিন কাট (minimum cut)।

দ্রষ্টব্য: ব্যাকওয়ার্ড এজ (Backward edges) ব্যবহার করাটাকে এক ধরনের কারচুপি মনে হতে পারে — যেন আপনি একটি পাইপের ভেতরের পানি উল্টো দিকে পাঠিয়ে 'আন-সেন্ড' করছেন। কিন্তু এগুলো খুবই প্রয়োজনীয়। এগুলো ছাড়া, অ্যালগরিদম ভুল পথে যেতে পারে এবং আর ফিরতে পারে না। এগুলো থাকার কারণে এটি সর্বদা সঠিক সর্বোচ্চ প্রবাহ বা ম্যাক্স ফ্লো খুঁজে পায়।

ফোর্ড-ফুলকারসন ব্রেডথ ফার্স্ট সার্চ (BFS) বা এডমন্ডস-কার্প (Edmonds-Karp) সহ

from collections import deque

def max_flow(graph, source, sink):
    """graph[u][v] = capacity (0 if no edge). Returns max flow."""
    n = len(graph)
    total = 0

    while True:
        # BFS to find shortest augmenting path
        parent = [-1] * n
        parent[source] = source
        q = deque([source])
        while q and parent[sink] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and graph[u][v] > 0:
                    parent[v] = u
                    q.append(v)

        if parent[sink] == -1:
            break  # No augmenting path

        # Find bottleneck
        flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            flow = min(flow, graph[u][v])
            v = u

        # Update residual capacities
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= flow
            graph[v][u] += flow  # backward edge
            v = u

        total += flow

    return total

# 4-node network: 0=source, 3=sink
#   0->1 cap 3, 0->2 cap 2, 1->3 cap 2, 2->3 cap 3, 1->2 cap 1
g = [[0,3,2,0],[0,0,1,2],[0,0,0,3],[0,0,0,0]]
print(max_flow(g, 0, 3))  # 4