ম্যাক্সিমাম ফ্লো - ফোর্ড-ফুলকারসন এবং এডমন্ডস-কার্প#
এডমন্ডস-কার্প অ্যালগরিদম হল একটি ফ্লো নেটওয়ার্কে ম্যাক্সিমাল ফ্লো গণনার জন্য ফোর্ড-ফুলকারসন মেথডের একটি ইমপ্লিমেন্টেশন।
ফ্লো নেটওয়ার্ক#
প্রথমে সংজ্ঞায়িত করি ফ্লো নেটওয়ার্ক, ফ্লো, এবং ম্যাক্সিমাম ফ্লো কী।
একটি নেটওয়ার্ক হল একটি ডিরেক্টেড গ্রাফ $G$ যেখানে ভার্টেক্স $V$ এবং এজ $E$ আছে, সাথে একটি ফাংশন $c$ যা প্রতিটি এজ $e \in E$-কে একটি অঋণাত্মক পূর্ণ সংখ্যা মান প্রদান করে, যা $e$-এর ক্যাপাসিটি। এই ধরনের নেটওয়ার্ককে ফ্লো নেটওয়ার্ক বলা হয়, যদি আমরা অতিরিক্তভাবে দুটি ভার্টেক্সকে চিহ্নিত করি, একটিকে সোর্স এবং একটিকে সিংক হিসেবে।
একটি ফ্লো নেটওয়ার্কে ফ্লো হল একটি ফাংশন $f$, যা আবার প্রতিটি এজ $e$-কে একটি অঋণাত্মক পূর্ণ সংখ্যা মান প্রদান করে, অর্থাৎ ফ্লো। ফাংশনটিকে নিম্নলিখিত দুটি শর্ত পূরণ করতে হবে:
একটি এজের ফ্লো ক্যাপাসিটি অতিক্রম করতে পারে না।
$$f(e) \le c(e)$$এবং সোর্স ও সিংক ভার্টেক্স ছাড়া, একটি ভার্টেক্স $u$-এর ইনকামিং ফ্লোর যোগফল $u$-এর আউটগোয়িং ফ্লোর যোগফলের সমান হতে হবে।
$$\sum_{(v, u) \in E} f((v, u)) = \sum_{(u, v) \in E} f((u, v))$$সোর্স ভার্টেক্স $s$-এর শুধুমাত্র আউটগোয়িং ফ্লো আছে, এবং সিংক ভার্টেক্স $t$-এর শুধুমাত্র ইনকামিং ফ্লো আছে।
এটি দেখা সহজ যে নিম্নলিখিত সমীকরণটি সত্য:
$$\sum_{(s, u) \in E} f((s, u)) = \sum_{(u, t) \in E} f((u, t))$$একটি ফ্লো নেটওয়ার্কের জন্য একটি ভালো উপমা হল নিম্নলিখিত ভিজ্যুয়ালাইজেশন: আমরা এজগুলোকে পানির পাইপ হিসেবে উপস্থাপন করি, একটি এজের ক্যাপাসিটি হল পাইপ দিয়ে প্রতি সেকেন্ডে সর্বোচ্চ কতটুকু পানি প্রবাহিত হতে পারে, এবং একটি এজের ফ্লো হল বর্তমানে পাইপ দিয়ে প্রতি সেকেন্ডে কতটুকু পানি প্রবাহিত হচ্ছে। এটি প্রথম ফ্লো শর্তটি ব্যাখ্যা করে। একটি পাইপের ক্যাপাসিটির চেয়ে বেশি পানি প্রবাহিত হতে পারে না। ভার্টেক্সগুলো জংশন হিসেবে কাজ করে, যেখানে কিছু পাইপ থেকে পানি বের হয়, এবং তারপর এই ভার্টেক্সগুলো পানিকে কোনোভাবে অন্য পাইপে বিতরণ করে। এটি দ্বিতীয় ফ্লো শর্তটিও ব্যাখ্যা করে। প্রতিটি জংশনে সমস্ত ইনকামিং পানি অন্য পাইপে বিতরণ করতে হবে। এটি জাদুকরীভাবে অদৃশ্য বা আবির্ভূত হতে পারে না। সোর্স $s$ হল সমস্ত পানির উৎপত্তি, এবং পানি শুধুমাত্র সিংক $t$-এ নিষ্কাশিত হতে পারে।
নিম্নলিখিত ছবিটি একটি ফ্লো নেটওয়ার্ক দেখায়। প্রতিটি এজের প্রথম মান ফ্লোকে উপস্থাপন করে, যা প্রাথমিকভাবে ০, এবং দ্বিতীয় মান ক্যাপাসিটি উপস্থাপন করে।
একটি নেটওয়ার্কের ফ্লোর মান হল সোর্স $s$-এ উৎপন্ন সমস্ত ফ্লোর যোগফল, অথবা সমতুল্যভাবে সিংক $t$ দ্বারা গ্রাস করা সমস্ত ফ্লোর যোগফল। একটি ম্যাক্সিমাল ফ্লো হল সর্বোচ্চ সম্ভব মানের ফ্লো। একটি ফ্লো নেটওয়ার্কের এই ম্যাক্সিমাল ফ্লো খুঁজে বের করাই আমরা যে সমস্যাটি সমাধান করতে চাই।
পানির পাইপের ভিজ্যুয়ালাইজেশনে, সমস্যাটি নিম্নলিখিতভাবে তৈরি করা যায়: সোর্স থেকে সিংকে পাইপ দিয়ে আমরা সর্বোচ্চ কতটুকু পানি প্রবাহিত করতে পারি?
নিম্নলিখিত ছবিটি ফ্লো নেটওয়ার্কে ম্যাক্সিমাল ফ্লো দেখায়।
ফোর্ড-ফুলকারসন মেথড#
আরও একটি জিনিস সংজ্ঞায়িত করি। একটি ডিরেক্টেড এজের রেসিডুয়াল ক্যাপাসিটি হল ক্যাপাসিটি বিয়োগ ফ্লো। লক্ষ্য করুন যে কোনো ডিরেক্টেড এজ $(u, v)$ বরাবর ফ্লো থাকলে, বিপরীত এজের ক্যাপাসিটি ০ এবং আমরা এর ফ্লোকে $f((v, u)) = -f((u, v))$ হিসেবে সংজ্ঞায়িত করতে পারি। এটি সমস্ত বিপরীত এজের জন্যও রেসিডুয়াল ক্যাপাসিটি সংজ্ঞায়িত করে। আমরা এই সমস্ত এজ থেকে একটি রেসিডুয়াল নেটওয়ার্ক তৈরি করতে পারি, যা একই ভার্টেক্স এবং এজ সহ একটি নেটওয়ার্ক, তবে আমরা ক্যাপাসিটি হিসেবে রেসিডুয়াল ক্যাপাসিটি ব্যবহার করি।
ফোর্ড-ফুলকারসন মেথড নিম্নলিখিতভাবে কাজ করে। প্রথমে আমরা প্রতিটি এজের ফ্লো শূন্যে সেট করি। তারপর আমরা $s$ থেকে $t$-তে একটি অগমেন্টিং পাথ খুঁজি। একটি অগমেন্টিং পাথ হল রেসিডুয়াল গ্রাফে একটি সিম্পল পাথ যেখানে পাথ বরাবর সমস্ত এজের রেসিডুয়াল ক্যাপাসিটি ধনাত্মক। এই ধরনের পাথ পাওয়া গেলে, আমরা এই এজগুলো বরাবর ফ্লো বাড়াতে পারি। আমরা অগমেন্টিং পাথ খোঁজা এবং ফ্লো বাড়ানো চালিয়ে যাই। যখন আর অগমেন্টিং পাথ থাকে না, তখন ফ্লো ম্যাক্সিমাল।
আরও বিস্তারিতভাবে বর্ণনা করি, একটি অগমেন্টিং পাথ বরাবর ফ্লো বাড়ানো মানে কী। ধরি $C$ হল পাথের এজগুলোর মধ্যে সবচেয়ে ছোট রেসিডুয়াল ক্যাপাসিটি। তারপর আমরা নিম্নলিখিতভাবে ফ্লো বাড়াই: পাথের প্রতিটি এজ $(u, v)$-এর জন্য আমরা $f((u, v)) ~\text{+=}~ C$ এবং $f((v, u)) ~\text{-=}~ C$ আপডেট করি।
এখানে মেথডটি প্রদর্শনের জন্য একটি উদাহরণ। আমরা উপরের একই ফ্লো নেটওয়ার্ক ব্যবহার করি। প্রাথমিকভাবে আমরা ০ ফ্লো দিয়ে শুরু করি।
আমরা $s - A - B - t$ পাথ খুঁজে পাই রেসিডুয়াল ক্যাপাসিটি ৭, ৫, এবং ৮ সহ। এদের মিনিমাম ৫, তাই আমরা এই পাথ বরাবর ফ্লো ৫ বাড়াতে পারি। এটি নেটওয়ার্কের জন্য ৫ ফ্লো দেয়।
আবার আমরা একটি অগমেন্টিং পাথ খুঁজি, এবার আমরা $s - D - A - C - t$ পাই রেসিডুয়াল ক্যাপাসিটি ৪, ৩, ৩, এবং ৫ সহ। তাই আমরা ফ্লো ৩ বাড়াতে পারি এবং নেটওয়ার্কের জন্য ৮ ফ্লো পাই।
এবার আমরা $s - D - C - B - t$ পাথ পাই রেসিডুয়াল ক্যাপাসিটি ১, ২, ৩, এবং ৩ সহ, এবং তাই আমরা ফ্লো ১ বাড়াই।
এবার আমরা অগমেন্টিং পাথ $s - A - D - C - t$ পাই রেসিডুয়াল ক্যাপাসিটি ২, ৩, ১, এবং ২ সহ। আমরা ফ্লো ১ বাড়াতে পারি। তবে এই পাথটি খুবই আকর্ষণীয়। এটি বিপরীত এজ $(A, D)$ অন্তর্ভুক্ত করে। মূল ফ্লো নেটওয়ার্কে, আমরা $A$ থেকে $D$-তে কোনো ফ্লো পাঠাতে পারি না। কিন্তু যেহেতু আমাদের ইতিমধ্যে $D$ থেকে $A$-তে ৩ ফ্লো আছে, এটি সম্ভব। এর ব্যাখ্যা নিম্নরূপ: $D$ থেকে $A$-তে ৩ ফ্লো পাঠানোর বদলে, আমরা শুধু ২ পাঠাই এবং $s$ থেকে $A$-তে অতিরিক্ত ১ ফ্লো পাঠিয়ে এর ক্ষতিপূরণ করি, যা আমাদের $D - C - t$ পাথ বরাবর অতিরিক্ত ১ ফ্লো পাঠাতে সক্ষম করে।
এখন, $s$ এবং $t$-এর মধ্যে একটি অগমেন্টিং পাথ খুঁজে পাওয়া অসম্ভব, তাই $10$-এর এই ফ্লোই সর্বোচ্চ সম্ভব। আমরা ম্যাক্সিমাল ফ্লো পেয়ে গেছি।
লক্ষ্য করুন যে, ফোর্ড-ফুলকারসন মেথড অগমেন্টিং পাথ খোঁজার কোনো নির্দিষ্ট পদ্ধতি উল্লেখ করে না। সম্ভাব্য পদ্ধতিগুলো হল DFS বা BFS ব্যবহার করা যা উভয়ই $O(E)$-এ কাজ করে। নেটওয়ার্কের সমস্ত ক্যাপাসিটি পূর্ণ সংখ্যা হলে, প্রতিটি অগমেন্টিং পাথের জন্য নেটওয়ার্কের ফ্লো কমপক্ষে ১ বাড়ে (আরও বিস্তারিত জানতে দেখুন ইন্টিগ্রাল ফ্লো উপপাদ্য)। তাই ফোর্ড-ফুলকারসনের কমপ্লেক্সিটি $O(E F)$, যেখানে $F$ হল নেটওয়ার্কের ম্যাক্সিমাল ফ্লো। রেশনাল ক্যাপাসিটির ক্ষেত্রে অ্যালগরিদম সমাপ্তও হবে, কিন্তু কমপ্লেক্সিটি সীমাবদ্ধ নয়। ইররেশনাল ক্যাপাসিটির ক্ষেত্রে, অ্যালগরিদম কখনই সমাপ্ত নাও হতে পারে, এমনকি ম্যাক্সিমাল ফ্লোতে কনভার্জও নাও করতে পারে।
এডমন্ডস-কার্প অ্যালগরিদম#
এডমন্ডস-কার্প অ্যালগরিদম হল ফোর্ড-ফুলকারসন মেথডের একটি ইমপ্লিমেন্টেশন যা অগমেন্টিং পাথ খোঁজার জন্য BFS ব্যবহার করে। অ্যালগরিদমটি প্রথম ১৯৭০ সালে ইয়েফিম ডিনিৎজ প্রকাশ করেন, এবং পরে ১৯৭২ সালে স্বাধীনভাবে জ্যাক এডমন্ডস এবং রিচার্ড কার্প প্রকাশ করেন।
কমপ্লেক্সিটি ম্যাক্সিমাল ফ্লো থেকে স্বাধীনভাবে দেওয়া যায়। অ্যালগরিদমটি $O(V E^2)$ সময়ে চলে, এমনকি ইররেশনাল ক্যাপাসিটির জন্যও। ধারণাটি হল যে প্রতিবার আমরা একটি অগমেন্টিং পাথ খুঁজি, একটি এজ স্যাচুরেটেড হয়ে যায়, এবং $s$ থেকে সেই এজের দূরত্ব দীর্ঘতর হবে যদি এটি পরবর্তীতে আবার কোনো অগমেন্টিং পাথে দেখা যায়। সিম্পল পাথের দৈর্ঘ্য $V$ দ্বারা সীমাবদ্ধ।
ইমপ্লিমেন্টেশন#
capacity ম্যাট্রিক্স প্রতিটি ভার্টেক্স জোড়ার জন্য ক্যাপাসিটি সংরক্ষণ করে। adj হল আনডিরেক্টেড গ্রাফের অ্যাডজেসেন্সি লিস্ট, কারণ অগমেন্টিং পাথ খোঁজার সময় আমাদের ডিরেক্টেড এজের বিপরীত এজও ব্যবহার করতে হবে।
maxflow ফাংশনটি ম্যাক্সিমাল ফ্লোর মান রিটার্ন করবে। অ্যালগরিদমের সময়, capacity ম্যাট্রিক্স আসলে নেটওয়ার্কের রেসিডুয়াল ক্যাপাসিটি সংরক্ষণ করবে। প্রতিটি এজের ফ্লোর মান আলাদাভাবে সংরক্ষণ করা হবে না, তবে একটি অতিরিক্ত ম্যাট্রিক্স ব্যবহার করে ইমপ্লিমেন্টেশনটি সহজেই প্রসারিত করা যায় - ফ্লোও সংরক্ষণ এবং রিটার্ন করার জন্য।
int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;
int bfs(int s, int t, vector<int>& parent) {
fill(parent.begin(), parent.end(), -1);
parent[s] = -2;
queue<pair<int, int>> q;
q.push({s, INF});
while (!q.empty()) {
int cur = q.front().first;
int flow = q.front().second;
q.pop();
for (int next : adj[cur]) {
if (parent[next] == -1 && capacity[cur][next]) {
parent[next] = cur;
int new_flow = min(flow, capacity[cur][next]);
if (next == t)
return new_flow;
q.push({next, new_flow});
}
}
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
vector<int> parent(n);
int new_flow;
while (new_flow = bfs(s, t, parent)) {
flow += new_flow;
int cur = t;
while (cur != s) {
int prev = parent[cur];
capacity[prev][cur] -= new_flow;
capacity[cur][prev] += new_flow;
cur = prev;
}
}
return flow;
}ইন্টিগ্রাল ফ্লো উপপাদ্য#
উপপাদ্যটি বলে যে, নেটওয়ার্কের প্রতিটি ক্যাপাসিটি পূর্ণ সংখ্যা হলে, ম্যাক্সিমাম ফ্লোর আকার একটি পূর্ণ সংখ্যা, এবং এমন একটি ম্যাক্সিমাম ফ্লো বিদ্যমান যেখানে প্রতিটি এজের ফ্লোও একটি পূর্ণ সংখ্যা। বিশেষত, ফোর্ড-ফুলকারসন মেথড এই ধরনের ফ্লো খুঁজে পায়।
ম্যাক্স-ফ্লো মিন-কাট উপপাদ্য#
একটি $s$-$t$-কাট হল একটি ফ্লো নেটওয়ার্কের ভার্টেক্সগুলোর দুটি সেটে বিভাজন, যেখানে একটি সেটে সোর্স $s$ এবং অন্যটিতে সিংক $t$ অন্তর্ভুক্ত। একটি $s$-$t$-কাটের ক্যাপাসিটি হল সোর্স পক্ষ থেকে সিংক পক্ষে যাওয়া এজগুলোর ক্যাপাসিটির যোগফল।
স্পষ্টতই, আমরা যেকোনো $s$-$t$-কাটের ক্যাপাসিটির চেয়ে বেশি ফ্লো $s$ থেকে $t$-তে পাঠাতে পারি না। তাই, ম্যাক্সিমাম ফ্লো মিনিমাম কাট ক্যাপাসিটি দ্বারা সীমাবদ্ধ।
ম্যাক্স-ফ্লো মিন-কাট উপপাদ্য আরও এগিয়ে যায়। এটি বলে যে ম্যাক্সিমাম ফ্লোর ক্যাপাসিটি মিনিমাম কাটের ক্যাপাসিটির সমান হতে হবে।
নিম্নলিখিত ছবিতে, আপনি আমাদের আগে ব্যবহৃত ফ্লো নেটওয়ার্কের মিনিমাম কাট দেখতে পাবেন। এটি দেখায় যে কাট $\{s, A, D\}$ এবং $\{B, C, t\}$-এর ক্যাপাসিটি $5 + 3 + 2 = 10$, যা আমাদের পাওয়া ম্যাক্সিমাম ফ্লোর সমান। অন্যান্য কাটের ক্যাপাসিটি বেশি হবে, যেমন $\{s, A\}$ এবং $\{B, C, D, t\}$-এর মধ্যে ক্যাপাসিটি $4 + 3 + 5 = 12$।
ফোর্ড-ফুলকারসন মেথড ব্যবহার করে ম্যাক্সিমাম ফ্লো গণনার পরে একটি মিনিমাম কাট পাওয়া যায়। একটি সম্ভাব্য মিনিমাম কাট নিম্নরূপ: রেসিডুয়াল গ্রাফে $s$ থেকে পৌঁছানো যায় এমন সমস্ত ভার্টেক্সের সেট (ধনাত্মক রেসিডুয়াল ক্যাপাসিটিযুক্ত এজ ব্যবহার করে), এবং অন্য সমস্ত ভার্টেক্সের সেট। এই বিভাজন $s$ থেকে শুরু করে DFS ব্যবহার করে সহজেই পাওয়া যায়।