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

বাইপার্টাইট ম্যাচিং (Bipartite Matching)

ইন্টার্নশিপগুলোর সাথে শিক্ষার্থীদের মেলান — সুখী জুটির সর্বোচ্চ সংখ্যা খুঁজে বের করুন
Hopcroft-Karp:\(O(E\sqrt{V})\)simple DFS:\(O(V \cdot E)\)König's theorem:ম্যাক্সিমাম ম্যাচিং (max matching) = মিনিমাম ভার্টেক্স কভার (min vertex cover)

১০০ জন শিক্ষার্থী, ১০০ টি কোম্পানি। প্রতিটি শিক্ষার্থী কয়েকটি কোম্পানিতে আবেদন করেছে এবং প্রতিটি কোম্পানি সর্বোচ্চ একজন শিক্ষার্থীকে নিয়োগ দিতে পারে। এখন প্রশ্ন হলো, সর্বোচ্চ কতজন শিক্ষার্থী চাকরি পেতে পারে?

এটাই হলো বাইপার্টাইট ম্যাচিং (bipartite matching) — যা কম্পিউটার বিজ্ঞানের সবচেয়ে গুরুত্বপূর্ণ ও ব্যবহারিক গ্রাফ সমস্যাগুলির মধ্যে অন্যতম। শিডিউলিং বা রুটিন তৈরি থেকে শুরু করে বিজ্ঞাপনের নিলাম (ad auctions) এবং এমনকি ডিএনএ (DNA) বিশ্লেষণের মতো কাজগুলোতেও এর ব্যাপক প্রয়োগ বা ব্যবহার রয়েছে।

কোন বিষয়টি একটি গ্রাফকে বাইপার্টাইট (Bipartite) করে তোলে?

একটি গ্রাফ তখনই বাইপার্টাইট (bipartite) হয়, যদি আপনি তার সমস্ত ভার্টেক্সগুলোকে দুটি গ্রুপে ভাগ করতে পারেন — ধরুন বাম (L) এবং ডান (R) — যেখানে প্রতিটি বয়োজোড় বা এজ (edge) কেবলমাত্র L এবং R-এর মধ্যেই সংযুক্ত থাকে। অর্থাৎ, L-এর ভেতরের বা R-এর ভেতরের নিজেদের ভার্টেক্সগুলোর মধ্যে কোনো এজ থাকা চলবে না। উদাহরণস্বরূপ, বাম দিকে শিক্ষার্থীরা রয়েছে, ডান দিকে কোম্পানিগুলো, এবং তাদের মধ্যকার চাকরির আবেদনগুলো হলো এজ বা সংযোগ।

একটি ম্যাচিং (matching) হলো এজগুলোর এমন একটি সাবসেট যেখানে কোনো ভার্টেক্স দুইবার আসে না — অর্থাৎ প্রতিটি শিক্ষার্থী সর্বোচ্চ একটি জুটিতে বা পেয়ারে এবং প্রতিটি কোম্পানিও সর্বোচ্চ একটি জুটিতে থাকে। আমরা সর্বোচ্চ বা ম্যাক্সিমাম ম্যাচিং (maximum matching) চাই: অর্থাৎ যতটা সম্ভব বেশি সংখ্যক জুটির মিল করা।

অগ্মেন্টিং পাথ বা বর্ধনশীল পথ (Augmenting Paths): এর মূল ধারণা

ধরা যাক, একটি আংশিক বা পার্শিয়াল ম্যাচিং দেওয়া আছে। এমন অবস্থায় একটি অগ্মেন্টিং পাথ (augmenting path) হলো এমন একটি পথ যা ম্যাচ করা বা মেলানো এজ এবং ম্যাচ না করা এজগুলোর মধ্যে পর্যায়ক্রমে (alternates) চলতে থাকে, যার শুরু এবং শেষ উভয়ই হয় দুটি অম্যাচ করা (unmatched) ভার্টেক্সে। আপনি যদি এই পথের সমস্ত এজগুলো উল্টে দেন বা ফ্লিপ করেন (ম্যাচ করা → অম্যাচ করা, অম্যাচ করা → ম্যাচ করা), তবে ম্যাচিংয়ে একটি অতিরিক্ত জুটি বা পেয়ার যুক্ত হবে।

বার্জের থিওরেম (Berge's theorem): একটি ম্যাচিং তখনই সর্বোচ্চ বা ম্যাক্সিমাম হয়, যদি এবং কেবল যদি তার মধ্যে আর কোনো অগ্মেন্টিং পাথ বা পথ বিদ্যমান না থাকে। সুতরাং এর অ্যালগরিদমটি হলো: যতক্ষণ পর্যন্ত পথে আর কোনো অগ্মেন্টিং পাথ অবশিষ্ট না থাকে, ততক্ষণ পর্যন্ত এমন নতুন পথ খুঁজে বের করুন এবং ম্যাচিংকে বাড়াতে থাকুন। প্রতিটি পথ খুঁজে পাওয়ার জন্য একটি সাধারণ ডিএফএস (DFS) বা বিএফএস (BFS) অ্যালগরিদম ব্যবহার করলে এর কমপ্লেক্সিটি দাঁড়ায় \(O(VE)\)।

হপক্রফট-কার্প (Hopcroft-Karp): আরও দ্রুতগতির একটি উপায়

একবার একটি করে অগ্মেন্টিং পাথ খোঁজার পরিবর্তে, হপক্রফট-কার্প (Hopcroft-Karp) অ্যালগরিদমটি প্রতিটি ধাপে সবগুলো ক্ষুদ্রতম বা সবচেয়ে ছোট অগ্মেন্টিং পাথ একসাথে খুঁজে বের করে:

  1. বিএফএস (BFS) ধাপ: সবগুলোর ক্ষুদ্রতম অগ্মেন্টিং পাথের দৈর্ঘ্য খুঁজে বের করুন এবং একটি লেয়ারড (layered) বা স্তরবিন্যস্ত গ্রাফ তৈরি করুন।
  2. ডিএফএস (DFS) ধাপ: এই লেয়ারড গ্রাফের মধ্যে থাকা ভার্টেক্স-ডিসজয়েণ্ট (vertex-disjoint) বা আলাদা ভার্টেক্সের অগ্মেন্টিং পাথগুলোর একটি বড় বা ম্যাক্সিমাল সেট খুঁজে বের করুন এবং সেগুলোর সবগুলোকে একসাথেই অগ্মেন্ট করুন বা বাড়িয়ে নিন।

প্রতিটি ধাপের পর, বাকি থাকা ক্ষুদ্রতম অগ্মেন্টিং পাথগুলোর দৈর্ঘ্য কঠোরভাবে বাড়তে থাকে। এটি সর্বোচ্চ \(O(\sqrt{V})\) বার ঘটে, যা থেকে আমরা পাই \(O(\sqrt{V})\) টি ধাপ × প্রতিটি ধাপে \(O(E)\) = \(O(E\sqrt{V})\)।

ম্যাক্স ফ্লো (Max Flow)-তে রূপান্তর (Reduction)

বাইপার্টাইট ম্যাচিং আসলে এক ধরনের ম্যাক্স ফ্লো (max flow) সমস্যা। প্রতিটি L ভার্টেক্সের সাথে সংযুক্ত একটি সুপার-সোর্স s (যার ধারণক্ষমতা বা ক্যাপাসিটি ১) যুক্ত করুন, প্রতিটি R ভার্টেক্স থেকে একটি সুপার-সিঙ্ক t (যার ক্যাপাসিটি ১) যুক্ত করুন এবং সমস্ত L-R এজগুলোকে ১ ক্যাপাসিটিতে রেখে দিন। এরপর যেকোনো ম্যাক্স ফ্লো অ্যালগরিদম রান বা চালান — প্রাপ্ত ফলাফলটি ঠিক ম্যাক্সিমাম ম্যাচিং বা সর্বোচ্চ ম্যাচিংয়ের সমান হবে।

এই ইউনিট-ক্যাপাসিটি (Unit-capacity network) নেটওয়ার্কের ওপর ডিনিকের (Dinic's) অ্যালগরিদম চালালে এর কমপ্লেক্সিটি হয় \(O(E\sqrt{V})\) — যা ঠিক হপক্রফট-কার্পের (Hopcroft-Karp) মতোই।

কোনিগের থিওরেম বা উপপাদ্য (König's Theorem)

একটি ভার্টেক্স কভার (vertex cover) হলো ভার্টেক্সগুলোর এমন একটি সেট যা প্রতিটি এজকে "স্পর্শ" করে (অর্থাৎ প্রতিটি এজের অন্তত একটি প্রান্ত এই কভারের মধ্যে থাকে)। বাইপার্টাইট গ্রাফের ক্ষেত্রে:

ম্যাক্সিমাম ম্যাচিং এর সাইজ = মিনিমাম ভার্টেক্স কভার এর সাইজ

এই চমৎকার ডুয়ালিটি (duality) বা দ্বৈততা — যাকে কোনিগের থিওরেম বলা হয় — সাধারণ গ্রাফের ক্ষেত্রে প্রযোজ্য নয় (যেখানে মিনিমাম ভার্টেক্স কভার বের করা একটি NP-hard বা বেশ কঠিন কাজ)। তবে একটি ম্যাক্সিমাম ম্যাচিং বা সর্বোচ্চ ম্যাচিং ব্যবহার করে অল্টারনেটিং-পাথ (alternating-path) কনস্ট্রাকশনের মাধ্যমে সহজেই একটি মিনিমাম ভার্টেক্স কভার খুঁজে পাওয়া সম্ভব।

দ্রষ্টব্য: অগ্মেন্টিং পাথ (Augmenting paths) শুনতে জটিল মনে হলেও এর ধারণাটি অত্যন্ত সহজ: একটি আনম্যাচ করা বা খালি (free) ভার্টেক্স থেকে আরেকটি আনম্যাচ করা বা খালি ভার্টেক্স পর্যন্ত পর্যায়ক্রমে ম্যাচ হওয়া বা না হওয়া এজগুলোর একটি শৃঙ্খল বা চেইন (chain) খুঁজুন, এরপর সেগুলোর প্রতিটিকে উল্টে বা ফ্লিপ করে দিন। একটি ফ্লিপ = আরও একটি অতিরিক্ত ম্যাচ হওয়া জোড়া বা জুটি।

বাইপার্টাইট ম্যাচিং — ডিএফএস অগ্মেন্টিং পাথ বা DFS Augmenting Paths

def bipartite_matching(left_n, right_n, edges):
    """edges: list of (l, r) where l in [0,left_n), r in [0,right_n)"""
    adj = [[] for _ in range(left_n)]
    for l, r in edges:
        adj[l].append(r)


    match_l = [-1] * left_n   # match_l[l] = r matched to l
    match_r = [-1] * right_n  # match_r[r] = l matched to r


    def dfs(l, visited):
        for r in adj[l]:
            if visited[r]: continue
            visited[r] = True
            if match_r[r] == -1 or dfs(match_r[r], visited):
                match_l[l] = r
                match_r[r] = l
                return True
        return False


    total = 0
    for l in range(left_n):
        visited = [False] * right_n
        if dfs(l, visited):
            total += 1


    return total, match_l


# 3 students, 3 companies
# student 0 -> companies 0, 1
# student 1 -> company 1
# student 2 -> companies 1, 2
edges = [(0,0),(0,1),(1,1),(2,1),(2,2)]
count, matching = bipartite_matching(3, 3, edges)
print('Matched:', count)      # 3
print('Assignment:', matching) # [0, 1, 2]
Output
Matched: 3
Assignment: [0, 1, 2]

Complexity

⚡ হপক্রফট-কার্প (Hopcroft-Karp)
\(O(\sqrt{V})\) সংখ্যক ধাপ (পাথ বা পথের দৈর্ঘ্য প্রতিটি ধাপে বাড়ে) × প্রতিটি ধাপে \(O(E)\); ঘন বা ডেন্স (dense) বাইপার্টাইট গ্রাফের জন্য এটি সবচেয়ে অপ্টিমাল
স্পার্স (sparse) গ্রাফের জন্য প্রায় লিনিয়ার (Near-linear) \(O(E\sqrt{V})\)
🔍 সাধারণ ডিএফএস (Simple DFS) অগ্মেন্টিং পাথ (augmenting paths)
সর্বোচ্চ V/2 টি অগমেন্টেশন (augmentations); প্রতিটি ডিএফএস-এর খরচ \(O(E)\); নিখুঁতভাবে ইমপ্লিমেন্ট (implement) বা প্রয়োগ করতে গেলে বেশ সহজ
ছোট গ্রাফের জন্য পর্যাপ্ত বা ভালো \(O(V \cdot E)\)
🌊 ডিনিকের ম্যাক্স ফ্লো এর মাধ্যমে (Via Dinic's max flow)
ইউনিট-ক্যাপাসিটি সংবলিত ফ্লো নেটওয়ার্ক; ডিনিকের অ্যালগরিদমটি স্বয়ংক্রিয়ভাবেই হপক্রফট-কার্পের মতো একই কমপ্লেক্সিটি অর্জন করে
হপক্রফট-কার্পের মতোই সমান কমপ্লেক্সিটি বা বাউন্ড \(O(E\sqrt{V})\)
👑 কোনিগের থিওরেমের ডেরিভেশন বা প্রতিপাদন (König's theorem derivation)
অম্যাচ বা আনম্যাচ করা L ভার্টেক্সগুলো থেকে অল্টারনেটিং বিএফএস (Alternating BFS) করে ম্যাক্সিমাম ম্যাচিং থেকে মিনিমাম ভার্টেক্স কভার (minimum vertex cover) আবিষ্কার করা যায়
ম্যাচিং পাওয়ার পর এটি লিনিয়ার (Linear) \(O(V+E)\)

ছোট কুইজ

একটি ম্যাচিং M এর সাপেক্ষে অগ্মেন্টিং পাথ বা বর্ধনশীল পথ (augmenting path) বলতে কী বোঝায়?

পড়া চালিয়ে যান

ম্যাক্স ফ্লো / মিন কাট (Max Flow / Min Cut)
আপনার পাইপের নেটওয়ার্ক দিয়ে কতটুকু পানি যেতে পারবে? সেটির সিদ্ধান্ত নেবে বটলনেক (bottleneck) বা সরু পথটি
→
ডিনিকের অ্যালগরিদম (Dinic's Algorithm)
এক ধাপে সমস্ত ক্ষুদ্রতম অগমেন্টিং পাথগুলো (augmenting paths) একসাথে বা ব্যাচে (batch) সম্পন্ন করে — যা একটি একটি করে বের করার চেয়ে নাটকীয়ভাবে দ্রুতগতির
→
হাঙ্গেরিয়ান অ্যালগরিদম (Hungarian Algorithm)
সর্বনিম্ন খরচে কর্মীদের কাজ বরাদ্দ করুন — নিখুঁত সমন্বয় বা পারফেক্ট ম্যাচ
→