Max Flow Problem একটি গ্রাফ তত্ত্বের একটি গুরুত্বপূর্ণ সমস্যা যা একটি উৎস (source) থেকে গন্তব্য (sink) পর্যন্ত সর্বাধিক প্রবাহ নির্ধারণ করে। এটি সাধারণত একটি পরিচালিত গ্রাফে বিবেচনা করা হয় যেখানে প্রতিটি প্রান্তের একটি ধারণক্ষমতা (capacity) থাকে। Ford-Fulkerson Algorithm এই সমস্যার সমাধানের জন্য ব্যবহৃত হয়।
Max Flow Problem
সমস্যা বিবরণ:
- একটি পরিচালিত গ্রাফ \( G(V, E) \) যেখানে:
- \( V \) হলো শীর্ষের সেট (vertices),
- \( E \) হলো প্রান্তের সেট (edges)।
- একটি উৎস \( s \) এবং একটি গন্তব্য \( t \) নির্ধারণ করুন।
- প্রতিটি প্রান্ত \( u \to v \) এর একটি নন-নেগেটিভ ধারণক্ষমতা \( c(u, v) \) রয়েছে।
- উদ্দেশ্য হলো সর্বাধিক প্রবাহ \( f \) খুঁজে বের করা, যা উৎস থেকে গন্তব্য পর্যন্ত পৌঁছায়।
Ford-Fulkerson Algorithm
Ford-Fulkerson Algorithm সর্বাধিক প্রবাহ নির্ধারণের জন্য একটি ধাপপদ্ধতিগত পদ্ধতি। এটি গ্রাফে "augmenting paths" খোঁজার মাধ্যমে কাজ করে, অর্থাৎ, উৎস থেকে গন্তব্যের মধ্যে এমন পথ খোঁজে যেখানে প্রবাহ বাড়ানোর সুযোগ রয়েছে।
অ্যালগরিদমের ধাপসমূহ:
- প্রাথমিকভাবে: সব প্রান্তের প্রবাহ শূন্য (0) হিসেবে সেট করুন।
- মৌলিক খোঁজ: উৎস থেকে গন্তব্যের মধ্যে একটি augmenting path খুঁজুন (BFS বা DFS ব্যবহার করে)।
- আপডেট: যদি একটি augmenting path পাওয়া যায়, তবে প্রান্তের প্রবাহ আপডেট করুন এবং যতটা সম্ভব প্রবাহ বাড়ান।
- পুনরাবৃত্তি: এই ধাপগুলো চালিয়ে যান যতক্ষণ না কোনো augmenting path পাওয়া না যায়।
উদাহরণ (Python Implementation):
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(dict)
def add_edge(self, u, v, capacity):
self.graph[u][v] = capacity
self.graph[v][u] = 0 # reverse flow for residual graph
def bfs(self, source, sink, parent):
visited = set()
queue = [source]
visited.add(source)
while queue:
u = queue.pop(0)
for v in self.graph[u]:
if v not in visited and self.graph[u][v] > 0: # available capacity
queue.append(v)
visited.add(v)
parent[v] = u
if v == sink:
return True
return False
def ford_fulkerson(self, source, sink):
parent = {}
max_flow = 0
while self.bfs(source, sink, parent):
# Find the maximum flow through the path found by BFS
path_flow = float('Inf')
s = sink
while s != source:
path_flow = min(path_flow, self.graph[parent[s]][s])
s = parent[s]
# update residual capacities of the edges and reverse edges
v = sink
while v != source:
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
max_flow += path_flow
return max_flow
# উদাহরণ ব্যবহার
g = Graph()
g.add_edge('s', 'a', 10)
g.add_edge('s', 'b', 5)
g.add_edge('a', 'b', 15)
g.add_edge('a', 't', 10)
g.add_edge('b', 't', 10)
max_flow = g.ford_fulkerson('s', 't')
print("Maximum Flow:", max_flow) # আউটপুট হবে 15
সারসংক্ষেপ
- Max Flow Problem: একটি গ্রাফের উৎস থেকে গন্তব্য পর্যন্ত সর্বাধিক প্রবাহ নির্ধারণ করে।
- Ford-Fulkerson Algorithm: augmenting paths খোঁজার মাধ্যমে সর্বাধিক প্রবাহ খুঁজে বের করে।
এই অ্যালগরিদমগুলি বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়, যেমন নেটওয়ার্ক ডিজাইন, যানবাহন প্রবাহ বিশ্লেষণ, এবং সম্পদ বরাদ্দের সমস্যায়। আপনি যদি এই বিষয়ের উপর আরও বিস্তারিত আলোচনা করতে চান বা অন্য কিছু জানতে চান, তাহলে আমাকে জানাতে পারেন!
