دليل على Lemma للتدفق في الرسم البياني المتبقي

Question

في CLRS 3'rd Edition هناك LEMMA 26.2 التي تنص على ما يلي:

دع $ g= (v، e) $ تكون شبكة التدفق، دع $ f $ كن تدفقا في $ g، $ ودع $ P $ يكون مسار زيادة في $ g_ {f} $ . تحديد وظيفة $ f_ {p} \ colon v \ times v \ rawrow \ mathbb {r} $ بواسطة $$ f_ {p} (u، v)=start \ {{\ {\} {ll} c_ {f} (p) & \ text {if} (u، v) \ text {on} p \\ 0 & \ text {other} \ end {array} \ or. $$ ثم، $ f_ {p} $ هو تدفق في $ g_ {f} $ مع القيمة $ \ left | f_ {p} \ right |= c_ {f} (p)> 0 $

كيف تذهب حول إثبات هذا؟

كما أفهمنا نحتاج إلى التحقق من الحفاظ على التدفق وقيد القدرات. نحن نعلم أن $ c_f (p) $ هو الحد الأدنى للقدرات المتبقية على المسار $ P $ أي أصغر من القدرات، وبالتالي قيود القدرات راضية. ولكن ماذا عن قيود الحفاظ على التدفق وإثبات أن قيمة التدفق في الواقع $ c_f (p)> 0 $ ؟

Answer 1

لاحظ أنه إذا كان $ v ليس رأسا من $ p $ ، ثم $ f_p (u، v)= 0 $ . عندما $ v $ موجود في $ P $ وليس مصدرا ولا مصدرا، ثم هناك اثنين فقط الرؤوس $ v_1 $ و $ v_2 $ بحيث الحواف $ (v_1، v)، (v، v_2) $ موجودة في $ P $ . لذلك، في التدفق الزائد عند $ v $ $$ \ sum_u f_p (u، v) $ فقط لديك شروط غير صفرية $ f_p (v_1، v)= c_f (p) $ و $ f_p (v_2، v)= - f_p (v، v_2)= - c_f (p) $ .

لذلك، التدفق الزائد هو صفر.

لمعرفة ذلك $ c_f (p)> 0 $ فقط أذكر أنه يعرف على أنه الحد الأدنى من القدرات المتبقية من حواف $ P $ . هناك العديد من الحواف كثيرة في $ P $ وتحديد مسار زيادة القدرات المتبقية حوافها إيجابية. لذلك، أنت تأخذ الحد الأدنى من العديد من الأرقام الإيجابية. التي تؤدي إلى رقم إيجابي.