ডিমান্ডসহ ফ্লো#

একটি সাধারণ ফ্লো নেটওয়ার্কে একটি এজের ফ্লো শুধুমাত্র উপর থেকে ক্যাপাসিটি $c(e)$ দ্বারা এবং নিচ থেকে ০ দ্বারা সীমাবদ্ধ। এই আর্টিকেলে আমরা এমন ফ্লো নেটওয়ার্ক আলোচনা করব, যেখানে আমরা অতিরিক্তভাবে প্রতিটি এজের ফ্লোর একটি নির্দিষ্ট পরিমাণ থাকা প্রয়োজন, অর্থাৎ আমরা ফ্লোকে নিচ থেকে একটি ডিমান্ড ফাংশন $d(e)$ দ্বারা সীমাবদ্ধ করি:

তাই প্রতিটি এজের একটি ন্যূনতম ফ্লো মান আছে, যা আমাদের এজ বরাবর পাঠাতে হবে।

এটি সাধারণ ফ্লো সমস্যার একটি সাধারণীকরণ, কারণ সমস্ত এজ $e$-এর জন্য $d(e) = 0$ সেট করলে একটি সাধারণ ফ্লো নেটওয়ার্ক পাওয়া যায়। লক্ষ্য করুন যে, সাধারণ ফ্লো নেটওয়ার্কে একটি বৈধ ফ্লো খুঁজে পাওয়া অত্যন্ত সহজ, শুধু $f(e) = 0$ সেট করলেই একটি বৈধ ফ্লো হয়। তবে প্রতিটি এজের ফ্লো যদি একটি ডিমান্ড পূরণ করতে হয়, তাহলে হঠাৎ করেই একটি বৈধ ফ্লো খুঁজে পাওয়া বেশ জটিল হয়ে পড়ে।

আমরা দুটি সমস্যা বিবেচনা করব:

১. সমস্ত শর্ত পূরণকারী একটি ইচ্ছামতো ফ্লো খুঁজে বের করা ২. সমস্ত শর্ত পূরণকারী একটি ন্যূনতম ফ্লো খুঁজে বের করা

একটি ইচ্ছামতো ফ্লো খুঁজে বের করা#

আমরা নেটওয়ার্কে নিম্নলিখিত পরিবর্তন করি। একটি নতুন সোর্স $s'$ এবং একটি নতুন সিংক $t'$, সোর্স $s'$ থেকে প্রতিটি অন্য ভার্টেক্সে একটি নতুন এজ, প্রতিটি ভার্টেক্স থেকে সিংক $t'$-এ একটি নতুন এজ, এবং $t$ থেকে $s$-তে একটি এজ যোগ করি। এছাড়াও আমরা নতুন ক্যাপাসিটি ফাংশন $c'$ নিম্নরূপ সংজ্ঞায়িত করি:

• $c'((s', v)) = \sum_{u \in V} d((u, v))$ প্রতিটি এজ $(s', v)$-এর জন্য।
• $c'((v, t')) = \sum_{w \in V} d((v, w))$ প্রতিটি এজ $(v, t')$-এর জন্য।
• $c'((u, v)) = c((u, v)) - d((u, v))$ পুরনো নেটওয়ার্কের প্রতিটি এজ $(u, v)$-এর জন্য।
• $c'((t, s)) = \infty$

নতুন নেটওয়ার্কে স্যাচুরেটিং ফ্লো থাকলে (একটি ফ্লো যেখানে $s'$ থেকে বের হওয়া প্রতিটি এজ সম্পূর্ণ পূর্ণ, যা $t'$-এ আসা প্রতিটি এজ সম্পূর্ণ পূর্ণ হওয়ার সমতুল্য), তাহলে ডিমান্ডসহ নেটওয়ার্কের একটি বৈধ ফ্লো আছে, এবং প্রকৃত ফ্লো নতুন নেটওয়ার্ক থেকে সহজেই পুনর্গঠন করা যায়। অন্যথায় সমস্ত শর্ত পূরণকারী কোনো ফ্লো বিদ্যমান নেই। যেহেতু স্যাচুরেটিং ফ্লো অবশ্যই ম্যাক্সিমাম ফ্লো হতে হবে, এটি যেকোনো ম্যাক্সিমাম ফ্লো অ্যালগরিদম দিয়ে পাওয়া যায়, যেমন এডমন্ডস-কার্প অ্যালগরিদম বা পুশ-রিলেবেল অ্যালগরিদম।

এই রূপান্তরগুলোর সঠিকতা বোঝা আরও কঠিন। আমরা এটি নিম্নলিখিতভাবে ভাবতে পারি: $d(e) > 0$ সহ প্রতিটি এজ $e = (u, v)$ মূলত দুটি এজ দিয়ে প্রতিস্থাপিত হয়: একটি $d(i)$ ক্যাপাসিটির, এবং অন্যটি $c(i) - d(i)$ ক্যাপাসিটির। আমরা প্রথম এজটি স্যাচুরেট করতে চাই (অর্থাৎ এই এজ বরাবর ফ্লো তার ক্যাপাসিটির সমান হতে হবে)। দ্বিতীয় এজটি কম গুরুত্বপূর্ণ - এটি বরাবর ফ্লো যেকোনো কিছু হতে পারে, যদি এটি তার ক্যাপাসিটি অতিক্রম না করে। যে প্রতিটি এজ স্যাচুরেট করতে হবে সেগুলো বিবেচনা করি, এবং আমরা নিম্নলিখিত অপারেশন করি: নতুন সোর্স $s'$ থেকে এর শেষ $v$-তে এজ আঁকি, এর শুরু $u$ থেকে নতুন সিংক $t'$-এ এজ আঁকি, এজটি নিজে সরিয়ে দিই, এবং পুরনো সিংক $t$ থেকে পুরনো সোর্স $s$-তে অসীম ক্যাপাসিটির এজ আঁকি। এই কাজগুলো দিয়ে আমরা এই সত্যটি সিমুলেট করি যে এজটি স্যাচুরেটেড - $v$ থেকে অতিরিক্ত $d(e)$ ফ্লো বের হবে (আমরা একটি নতুন সোর্স দিয়ে সিমুলেট করি যা $v$-তে সঠিক পরিমাণ ফ্লো সরবরাহ করে), এবং $u$-ও $d(e)$ অতিরিক্ত ফ্লো পুশ করবে (কিন্তু পুরনো এজ বরাবর না গিয়ে, এই ফ্লো সরাসরি নতুন সিংক $t'$-এ যাবে)। $d(e)$ মানের একটি ফ্লো, যা মূলত $s - \dots - u - v - \dots t$ পাথ বরাবর প্রবাহিত হতো, এখন $s' - v - \dots - t - s - \dots - u - t'$ নতুন পাথ নিতে পারে। নতুন নেটওয়ার্কের সংজ্ঞায় একমাত্র যে জিনিসটি সরলীকৃত হয়েছে তা হল, প্রক্রিয়াটি একই ভার্টেক্স জোড়ার মধ্যে একাধিক এজ তৈরি করলে, সেগুলো যোগকৃত ক্যাপাসিটি সহ একটি একক এজে একত্রিত হয়।

ন্যূনতম ফ্লো#

লক্ষ্য করুন যে $(t, s)$ এজ বরাবর (পুরনো সিংক থেকে পুরনো সোর্সে) $\infty$ ক্যাপাসিটিসহ সংশ্লিষ্ট পুরনো নেটওয়ার্কের সম্পূর্ণ ফ্লো প্রবাহিত হয়। অর্থাৎ এই এজের ক্যাপাসিটি পুরনো নেটওয়ার্কের ফ্লো মানকে প্রভাবিত করে। এই এজকে যথেষ্ট বড় ক্যাপাসিটি (অর্থাৎ $\infty$) দিলে, পুরনো নেটওয়ার্কের ফ্লো সীমাহীন। এই এজকে ছোট ক্যাপাসিটি দিয়ে সীমাবদ্ধ করলে, ফ্লো মান কমবে। তবে এই এজকে খুব ছোট মান দিয়ে সীমাবদ্ধ করলে, নেটওয়ার্কের স্যাচুরেটেড সমাধান থাকবে না, অর্থাৎ মূল নেটওয়ার্কের সংশ্লিষ্ট সমাধান এজের ডিমান্ড পূরণ করবে না। স্পষ্টতই এখানে আমরা বাইনারি সার্চ ব্যবহার করে সবচেয়ে কম মান খুঁজে বের করতে পারি যেখানে সমস্ত শর্ত এখনও পূরণ হয়। এটি মূল নেটওয়ার্কের ন্যূনতম ফ্লো দেয়।