مقاله در مورد شبکه ها و تطابق در گراف

بخشی از مقاله

شبكه ها و تطابق در گراف

فهرست مطالب
عنوان صفحه
مقدمه
فصل 1
شبكه ها
1-1 شارش ها
1-2 برش ها
1-3 قضيه شارش ماكزيمم – برش مينيمم
1-4 قضيه منجر

فصل 2
تطابق ها
2-1 انطباق ها
2-2 تطابق ها و پوشش ها در گراف هاي دو بخش
2-3 تطابق كامل
2-4 مسأله تخصیص شغل

منابع
شبكه ها
1-1 شارش ها
شبكه هاي حمل و نقل، واسطه‌هايي براي فرستادن كالاها از مراكز توليد به فروشگاهها هستند. اين شبكه ها را مي‌توان به صورت يك گراف جهت دار با يك سري ساختارهاي اضافي درنظر گرفت و آن ها را به صورت كارآيي مورد تحليل و بررسي قرار داد. اين گونه گراف هاي جهت دار، نظريه اي را به وجود آورده اند كه موضوع مورد بحث ما در اين فصل مي باشد. اين نظريه ابعاد وسيعي از كاربردها را دربرمي‌گيرد.
تعريف 1-1 فرض كنيم N=(V,E) يك گراف سودار همبند بيطوقه باشد. N را يك شبكه يا يك شبكه حمل و نقل مي‌نامند هرگاه شرايط زير برق

رار باشند:
(الف) رأس يكتايي مانند وجود دارد به طوري كه ، يعني درجة ورودي a، برابر 0 است. اين رأس a را مبدأ يا منبع مي‌نامند.
(ب) رأس يكتايي مانند به نام مقصد يا چاهك، وجود دارد به طوري كه od(z)، يعني درجة خروجي z، برابر با 0 است.
(پ) گراف N وزندار است و از اين رو، تابعي از E در N، يعني مجموعة

اعداد صحيح نامنفي، وجود دارد كه به هر كمان يك ظرفيت، كه با نشان داده مي‌شود، نسبت مي‌دهد.
براي نشان دادن يك شبكه، ابتدا گراف جهت زمينه آن (D) را رسم كرده و سپس ظرفيت هر كمان را به عنوان برچسب آن كمان قرار مي‌دهيم.
مثال 1-1 گراف شكل 1-1 يك شبكه حمل و نقل است. در اين جا رأس a مبدأ و راس z مقصد است و ظرفيتها، كنار هر كمان نشان داده شده‌اند. چون ، مقدار كالاي حمل شده از a به z نمي‌تواند از 12 بيشتر شود. با توجه به بازهم اين مقدار محدودتر مي‌شود و نمي‌تواند از 11 تجاوز كند. براي تعيين مقدار ماكسيممي كه مي‌توان از a به z حمل كرد بايد ظرفيتهاي همة كمانهاي بشكه را درنظر بگيريم.

تعريف 1-2 فرض كنيم يك شبكة حمل و نقل باشد تابع f از E در N، يعني مجموعة اعداد صحيح نامنفي، را يك شارش براي N مي نامند هرگاه
الف) به ازاي هر كمان و
ب) به ازاي هر ، غير از مبدأ a يا مقصد z ، (اگر كماني مانند (v,w) وجود نداشته باشد، قرار مي دهيم
مقدار تابع f براي كمان e، f(e) را مي توان به نرخ انتقال داده در طول e، تحت شارش f تشبيه كرد. شرط اول اين تعريف مشخص مي‌كند كه مقدار كالاي حمل شده در طول هر كمان نمي تواند از ظرفيت آن كمان تجاوز كند، كران بالايي شرط الف را قيد ظرفيت مي‌نامند.
شرط دوم، شرط بقا ناميده مي شود و ايجاب مي كند كه، مقدار كالايي كه وارد رأس مانند v مي شود با مقدار كالايي كه از اين رأس خارج مي شود برابر باشد. اين امر در مورد همة رأسها به استثناي مبدأ و مقصد بر قرار است.
مثال 1-2 در شبكه هاي شكل 1-2، نشان x,y روي كماني مانند e به اين ترتيب تعيين شده است كه y , x=c(e) مقداري است كه شارشي مانند f به اين كمان نسبت داده است. نشان هر كمان مانند e در صدق مي كند. در شكل 1-2 (الف)، شارش، وارد رأس مي شود،5 است، ولي شارشي كه از آن رأس خارج مي شود 4=2+2 است. بنابراين، در اين حالت تابع f نمي تواند يك شارش باشد. تابع f براي شكل 1-2 (ب) در هر دو شرط صدق مي

كند و بنابراين، شارشي براي شبكهء مفروض است.
توجه داشته باشيد كه هر شبكه، حداقل داراي يك شارش است، زيرا تابع fاي كه در آن به ازاي هر داشته باشيم: در هر دو شرط تعريف
1-2 صدق مي كند. اين تابع، شارش صفر ناميده مي شود.
تعريف 1-3 فرض كنيم f شارشي براي شبكة حمل و نقل N=(V,E) باشد.
الف) كماني مانند e متعلق به اين شبكه را اشباع شده مي نامند هر گروه f(e)=c(e) اگر f(e)<c(e) اين كمان را اشباع نشده مي نامند.
ب) اگر a مبدأ N باشد، را مقدار شارش مي نامند.
مثال 1-3 در شبكه شكل 1-2 (ب) فقط كمان اشباع شده است. ه

ر يك از كمان‌هاي ديگر اشباع نشده است. مقدار شارش اين شبكه

است. ولي آيا شارش ديگري مانند وجود دارد كه به ؟
مي‌گوئيم شارش fدر N، يك شارش ماكزيمم است، هر گاه هيچ شارش ديگري مانند در N با شرط وجود نداشته باشد.
هدف ما در ادامه، تعيين يك شارش ماكزيمم است. براي انجام اين كار، ملاحظه مي‌كنيم كه در شكل 1-2 (ب) داريم.

درنتيجه، شارش كل خارج شده از مبدأ a شارش كل وارد شده به مقصد z برابر است.
نكته اخير در مثال 1-3 شرط معقولي به نظر مي‌رسد، ولي آيا در حالت كلي چنين وضعيتي روي مي دهد؟ براي اثبات آن در مورد هر شبكه دلخواه به نوع خاصي از مجموعه هاي برشي كه در قسمت بعد مي‌آيد، نياز داريم.
1-2 برش ها
تعريف 1-4 اگر يك شبكهء حمل و نقل و C يك مجموعة برشي براي گراف بيسوي وابسته به N به صورت كه در آن باشد، C را يك برش يا يك برش a-z مي نامند هرگاه حذف كمانهاي C از شبكة مفروض به جدايي a و z منتهي شود.
ظرفيت هر برش، كه با capC نشان داده مي شود، با
(1-1)
يعني مجموع ظرفيتهاي همة كمانهاي (y,w) كه در آن و ، تعريف مي‌شود.
مثال 1-4 هر يك از خمهاي خط چين در شكل 1-3 برشي براي شبكة مفروض است. برش از كمانهاي بيسوي تشكيل شده است. اين برش رأسهاي شبكة مفروض را بر دو مجموعة و متمم آن، يعني ، افرازي مي‌كند و در اين مثال . ] در برش ، اگر يالهاي سودار (از P به )، يعني يالهاي ، را درنظر بگيريم مي بينيم كه حذف اين يالها به زيرگرافي با دو مؤلفه منتهي نمي شود. ولي، اين سريال مينيمال اند، به اين معني كه حذف آنها امكان پيدايش هر مسير سودار از a به z را از بين مي برد[
برش افراز و را براي رأسها القا مي‌كند و داراي ظرفيت است.
قضيه 1-1 فرض كنيم f شارشي در شبكة N=(V,E) باشد. اگر برشي در N باشد، آنگاه Val(f) نمي تواند از تجاوز كند.
اثبات فرض كنيم رأس a مبدأ N و رأس Z مقصد آن باشد. چون ، پس به ازاي هر ، . درنتيجه،

با توجه به شرط (ب) در تعريف شارش، به ازاي هر و ، داريم

اگر برابريهاي بالا را به هم بيفزاييم خواهيم داشت:



چون مجموعه هاي و
روي كل مجموعه متشكل از همة جفتهاي مرتب متعلق به P×P محاسبه شده اند، با يكديگر برابرند. درنتيجه،
(1-2)
به ازاي هر ، داريم و از اين رو، و
(1-3) .
با توجه به قضية 1-1 مي‌بينيم كه در شبكه اي مانند N، مقدار هر

شارش كوچكتر از يا برابر با ظرفيت هر برش موجود در آن شبكه است. بنابراين مقدار شارش ماكزيمم نمي تواند از مينيمم ظرفيتهاي برشهاي شبكه تجاوز كند. در مورد شبكة شكل 2-3 مي توان نشان داد كه برش متشكل از يالهاي و داراي ظرفيت مينيمم 11 است. درنتيجه شارش ماكزيمم f براي اين شبكه در صدق مي كند.
تعريف 1-5 برش C در N، يك برش مينيمم است، اگر هيچ برش ديگري مانند در N با شرط وجود نداشته باشد.
اگر يك شارش ماكزيمم و يك برش مينيمم به عنوان حالت خاصي از قضيه 1-1 داريم: (1-4)
نتيجه 1-1 فرض كنيد f يك شارش و C يك برش باشد، به طوري كه در اين صورت f يك شارش ماكزيمم و C يك برش مينيمم است.
اثبات فرض كنيد يك شارش ماكزيمم و يك برش مينيمم باشد. در اين صورت بنا بر رابطة 1-4 داريم:

و چون طبق فرض، ، نتيجه مي‌گيريم كه و درنتيبجه f يك شارش ماكزيمم و C يك برش مينيمم است .
در بخش آينده، عكس نتيجه 1-1 را اثبات خواهيم كرد، يعني اين كه در رابطة 1-4 همواره تساوي برقرار است.
ولي، قبل از پرداختن به اين مطلب، با توجه به برهان قضيه 1-1 ملاحظه ميكنيم كه مقدار هر شارش با

كه در آن برشي دلخواه در N است، بيان مي شود. بنابراين، به محض آنكه شارشي در شبكه اي ساخته شد، به ازاي هر برش در اين شبكه، مقدار شارش برابر است با مجموع شارشهاي موجود در كمان هاي سودار از رأسهاي P به رأسهاي منهاي مجموع ش

ارشهاي موجود در كمان هاي سودار از رأسهاي به رأسهاي P.
اين نكته ما را به نتيجة زير هدايت مي كند.
نتيجة 1-2 اگر f شارشي در شبكة حمل و نقل N=(V,E) باشد، انگاه مقدار شارش خارج شده از مبدأ a برابر است با مقدار شارش وارد شده در مقصد z.
اثبات قرار مي دهيم . با توجه به نكته قبلي داريم:

چون و ، مي‌بينيم كه
به همين ترتيب، به‌ازاي و داريم
درنتيجه،

و اين اثبات تمام است.

1-3 قضيه شارش ماكزيمم – برش مينيمم
در اين بخش الگوريتمي براي تعيين يك شارش ماكزيمم در شبكه ها ارائه مي‌نمائيم. يكي از اساسي‌ترين ملزومات چنين الگوريتمي اين است كه در صورت ديدن يك شارش، بتواند تشخيص دهد آيا اين شارش ماكزيمم هست يا خير. بنابراين در شروع كار، نگاهي به اين مسأله مي‌اندازيم.
فرض كنيد f يك شارش در شبكه N باشد. به هر مسير S در N، يك عدد صحيح نامنفي l(S) به صورت روبرو نسب مي‌دهيم:
كه در آن:

به راحتي مي توان ديد كه l(S)، بيشترين ميزان ممكن براي افزايش شارش در طول S (تحت f) است، بدون اينكه به شرط الف در تعريف 1-2 آسيبي وارد شود. اگر ، مسير S را f- اشباع شده و اگر ، S را f– اشباع نشده مي‌ناميم (حالت اخير معادل با اين است كه هر كمان رو به جلو از S، f – اشباع نشده و هر كمان معكوس از S، f- مثبت باشد). به طور ساده مي‌توان گفت كه يك مسير f- اشباع نشده، مسيري است كه از تمام ظرفيتش استفاده نشده است. مسير -f افزايشي يك مسير -f اشباع نشده از مبدأ a به مقصد z مي باشد. به طور مثال اگر f شارش مشخص شده در شبكه شكل 1-4 (الف) باشد، در اين صورت يك مسير -f افزايشي خواهد بود. و كمان‌هاي روبه جلوي S هستند و داريم .
وجود يك مسير -f افزايشي S در شبكه حائز اهميت است، زيرا نشان مي دهد كه f شارش ماكزيمم نيست.
در حقيقت با فرستادن يك شارش اضافي l(S)، در طول S، مي توان به شارش جديد ، به صورت زير رسيد:

و در اين حال داريم: را شارش اصلاح شده بر پاية S مي ‌خوانيم.
در شكل 1-4 (ب) شارش اصلاح شده شبكه 1-4 (الف) بر پايه مسير -f افزايشي نشان داده شده است.
شكل 1-4 (الف) مسير -f افزايشي S (ب) شارش اصلاح شده بر پايه f
در شكل (الف)

در شكل (ب)

نقش مسيرهاي افزايشي درنظريه شاره‌ها همانند مسيرهاي افزوده درنظريه تطابق هاست. قضيه زيرمؤيد اين مطلب است (آن را با قضية 2-1 مقايسه نمائيد.)

قضيه 1-2 شارش f در N ماكزيمم است، اگر و تنها اگر N داراي هيچ مسير
-f افزايشي نباشد.
اثبات اگر N شامل يك مسير -f افزايشي S باشد، در اين صورت f نمي تواند يك شارش ماكزيمم باشد. زيرا ، شارش اصلاح شده بر پايه S، داراي مقدار بزرگتري است.
برعكس، فرض كنيد كه N شامل هيچ مسير -f افزايشي نباشد. مي‌خواهيم نشان دهيم كه f يك شارش ماكزيمم است. فرض كنيد P مجموعه تمام رأس هايي باشد كه a توسط مسيرهاي -f اشباع نشده در N به آن ها متصل است. به وضوح داريم . از طرفي چون N داراي هيچ مسير -f افزايشي نيست، پس . بنابراين يك برش در N است. در ادامه نشان خواهيم داد كه هر كمان ، -f اشباع شده و هر كمان ، -f صفر است.
فرض كنيد t كماني با دم و سر باشد. از آن جايي كه پس (a,u)- مسير -f اشباع نشده مانند Q وجود دارد. اگر t، -f اشباع نشده باشد، در اين صورت Q را مي توان

با افزودن كمان t به مسير Q، به يك (a,v) – مسير -f اشباع نشده گسترش داد. ولي با توجه به اينكه ، چنين ميسري وجود ندارد و بنابراين t بايد -f اشباع شده باشد. با استدلال مشابهي مي‌توان نتيجه گرفت كه اگر ، آنگاه t بايد -f صفر باشد.
با به كارگيري قضيه 1-1 نتيجه مي شود:

و اكنون با توجه به نتيجه 1-1 روشن مي گردد كه f، يك شارش ماكزيمم (و C يك برش مينيمم است.) 
طي اثبات فوق، وجود يك شارش ماكزيمم و يك برش مينيمم C كه در آن ها شرط برقرار است، به اثبات رسيد. بنابراين قضيه زير كه متعلق به فورد، فالكرسن (1956) است، نيز مستقيماً به اثبات مي‌رسد:
قضيه 1-3 قضيه شارش ماكزيمم – برش مينيمم. در هر شبكة حمل و نقل ، شارش ماكزيمم كه مي‌توان در N به دست آورد برابر است با مينيمم ظرفيتهاي برشهاي اين شبكه.
اثبات بنابرقضيه 1-1 اگر برشي با ظرفيت مينيمم در N باشد، مقدار هر شارشي در N مانند f در نابرابري صدق مي‌كند. براي تحقيق در وجود شارشي مانند f كه به ازاي آن داشته باشيم ، الگوريتم زير، كه روش نشانگذاري نام دارد، مراحل لازم را در اختيار مي گذارد. 
روش نشانگذاري
مرحله 1: در شبكه مفروض N، شارش آغازي f در N را به ازاي هر كمان e متعلق به E با تعريف مي‌كنيم. اين تابع در شرايط شارش صدق مي‌كند.
مرحلة 2: مبدأ a را با نشانگذاري مي كنيم. (تين نشانگذاري نشان مي دهد كه در مبدأ a، هر اندازه ماده براي تحقق شارش ماكزيمم لازم باشد موجود است.)
مرحلة 3: به ازاي هر رأس مانند x كه مجاور از a است، x را به صورت زير نشانگذاري مي‌كنيم:
الف) اگر ، تعريف مي‌كنيم و رأس x را با نشانگذاري مي‌كنيم.
ب) اگر ، راس x را بدون نشان رها مي‌كنيم. ] نشان بر اين امر دلالت دارد كه شارش فعلي از a به x را مي توان به مقدار افزايش داد و اين واحد اضافي از مبدأ a تأمين مي شود.[
مرحلة 4: تا زماني كه رأس نشانداري مانند و يالي مانند (x,y) كه در آن y بي‌نشان است، وجود دارد و رأس y را به صورت زير نشانگذاري مي‌كنيم.
الف)اگر ،تعريف‌ميكنيم و رأس y را با نشانگذاري مي‌كنيم.
ب) اگر ، رأس y را بدون نشان رها مي‌كنيم.
]نشان بر اين امر دلالت دارد كه شارش فعلي وارد شده و در رأس y را

مي توان به مقدار ، كه از رأس x مي گيريم، افزايش داد.[
مرحلة 5: به همين ترتيب، تا زماني كه رأس نشانداري مانند و كماني مانند (y,x)، كه در آن y بي نشان است، وجود دارد رأس y مقابل را به صورت زير نشانگذاري مي كنيم:
الف) اگر ، راس y را با ، كه در آن نشانگذاري مي‌كنيم.
ب) اگر ، رأس y را بدون نشان رها مي كنيم.
J نشان به ما مي گويد كه با كاهش شارش از y به x، شارش كل خارج شده از y به رأسهاي نشاندار را مي توان به اندازة كاهش داد. در اين صورت اين واحد را مي توان براي افزايش شارش كل خارج شده از y با رأسهاي بي نشان به كار گرفت.[
چون رأسي مانند y ممكن است مجاور به يا مجاور از بيش از يك رأس نشاندار باشد، نتايج اين روش الزاماً يكتا نيست. علاوه بر اين، اگر x نشانگذاري شده باشد، شبكة مورد بحث ممكن است شامل هر دو كمان (x,y) و (y,x) باشد و بنابراين، ممكن است دو نشان براي y حاصل شود. ولي اين روش براي آن طراحي شده است كه يك شارش ماكزيمم به دست دهد و اين امكان هست كه بيش از يك چنين شارشي موجود باشد. به هر حال هر بار كه بتوان رأسي را به بيش از يك طريق نشانگذاري كرد، بايد يكي را به دلخواه انتخاب كنيم.
ضمن اينكه روش نشانگذاري را در بارة رأسهاي شبكة مفروض به كار مي‌بريم، مراحل 4 و 5 تا حد امكان در مورد مجموعة جاري (و در حال تغيير) رأسهاي نشانگذاري شده تكرار مي شوند. با هر تكرار دو حالت ممكن است روي رهد.
حالت 1: اگر مقصد z با نشانگذاري شود، شارش موجود در كمان (x,z) را مي توان مطابق نشانگذاري، از f(x,z) به افزايش داد.
رأس x را مي توان با يا ، كه در آن ، نشانگذاري كرد. در ارتباط با نشان ، مي توانيم براي افزايش شارش موجود در كمان (x,z) به مقدار ، رأس v را به عنوان مبدأ تلقي كنيم. در اين حالت نيز شارش حاضر در كمان (v,x) را از f(v,x) به (و نه به ) افزايش مي‌دهيم.
اگر x داراي نشان باشد، در اين صورت، براي تأمين شارش اضافي واحدي از x به z شارش موجود در يال (x,v) را از f(x,v)به تغيير مي دهيم.
به تدريج اين فرايند به مبدأ a بازمي‌گردد، شارش موجود در هر كمان متعلق به مسيري كه از a به z مي رود، به اندازة واحد افزايش يا كاهش مي‌يابد ]كاهش مربوط به وقتي است كه رأسي (از اين مسير) نشان منفي داشته باشد[. پس از اتمام كار، همة نشانهاي رأسها، به استثناي كه مربوط به مبدأ است، حذف مي‌شوند. اين فرايند تكرار مي شود تا ببينيم آيا امكان دارد كه بازهم

شارش را افزايش دهيم يا نه.
حالت 2: اگر روش نشانگذاري را تا حد امكان اجرا كنيم و مقصد z بي نشان باقي بماند، شارش ماكزيمم حاصل شده است. فرض كنيم P مجموعة رأسهايي از V باشد كه نشانگذاري شده اند و . چون رأسهاي نشانگذاري نشده اند، شارشهاي موجود در كمان هاي (x,y)، كه در آن و ،

در صدق مي كنند.
همچنين، به ازاي هر كمان (w,v)، و ، داريم . درنتيجه، شارشي براي شبكة مفروض وجود دارد به طوري كه مقدار شارش برابر است با ظرفيت برش . با توجه به قضية 1-1 نتيجه مي‌گيريم كه اين شارش يك شارش ماكزيمم است.
قبل از ارائه مثالي در بارة روش نشانگذاري، يك نتيجه ديگر و چند تفسير وابسته به آن را بيان مي كنيم.
نتيجه 1-3 فرض كنيم N=(V,E) يك شبكة حمل و نقل باشد كه در آن، به ازاي هر ، c(e) يك عدد صحيح مثبت است. آنگاه شارش ماكزيممي مانند f براي N وجود دارد به طوري كه، به ازاي هر كمان e، f(e) يك عدد صحيح نامنفي است.
در تعريف شبكه حمل و نقل و شارش (در يك شبكة حمل و نقل) مي توانيم اين امكان را مد نظر قرار دهيم كه توابع ظرفيت و شارش توابعي حقيقي و نامنفي باشند. اگر در يك شبكة حمل و نقل ظرفيتها اعدادي گويا باشند، در اين صورت رو نشانگذاري پايان پذير است و به شارش ماكزيمم دست خواهيم يافت. ولي، اگر بعضي از ظرفيتها اعداد گنگ باشند، اين امكان وجود دارد كه اين روش پاياني نداشته باشد، به اين ترتيب كه براي هر تكرار، هاي كوچكتري پديد آيد. علاوه بر اين، ال. آرفورد جونيور و دي. آر. فاكرسون نشان دادند كه اين روش مي تواند به يك شارش منتهي شود، ولي اين شارش لزوماً يك شارش ماكزيمم نيست. وقتي ظرفيتهاي گنگ پيش مي آيند مي توان اصلاحية ارائه شده به وسيلة جي. ادموندز. آر.ام.كارپ را به كار برد و در اين صورت اين روش (پس از تعدادي متناهي مرحله) پايان مي‌پذيرد و به يك شارش ماكزيمم دست مي‌يابيم.
مثال 1-5 با استفاده از روش نشانگذاري، شارش ماكسيممي براي شبكة حمل و نقل شكل 1-5 (الف) بيابيد. در اين شبكه، هر كمان با جفت مرتبي مركب از x و y نشانگذاري شده است، كه در آن x ظرفيت كمان است و شارش آغازي براي شبكه را نشان مي دهد. شكل 1-5 (ب) نخستين كاربرد روش نشانگذاري را در بارة اين شبكه نشان مي دهد. در اينجا نشانگذاري مقصد z بر اساس انتخاب صورت گرفته است. را به جاي به عنوان نشان انتخاب كرده ايم اگر از z به h به e به s به a بازگرديم و شارش موجود در هر ريال را به اندازة افزايش دهيم، شارش جديد در شكل
1-5 (ب) را به دست مي‌آوريم. شكلهاي 1-5 (پ)، (ت)، (ث) و (ج) كاربردهاي دوم، سوم، چهارم، و پنجم روش نشانگذاري را در بارة شبكة مفروض نشان مي‌دهند. ملاحظه مي‌كنيم كه چگونه رأس در شكل هاي 1-5 (ت) و (ج) نشان منفي دارد. همچنين، شكل 1-5 (ج) موقعيت ديگري نشانگذاري منفي را، اين بار براي رأس d، به دست مي دهد. اگر براي آخرين بار روش نشانگذاري را به كار ببريم، شبكة حمل و نقل مفروض مطابق شكل 1-6 نشانگذاري مي شود. در اينجا مقصد z بي نشان است و حالت دوم در روش نشانگذاري مطرح مي شود. اگرقرار دهيم و ، مي‌بينيم كه شارش وارد شده به z

است. كمانهايي از N كه با خم خط چين قطع شده اند كمانهاي متعلق به مجموعه برشي (بيسوي) وابسته به برش هستند. اين برش از همة كمانهاي به صورت ، كه در آن و ، تشكيل ش

ده است.

1-4 قضيه هاي منجر
در اين بخش، با استفاده از قضية شارش ماكزيمم – برش مينيمم، تعدادي قضيه به دست خواهيم آورد كه متعلق به منجر (1927) مي‌باشند. ابتدا تعاريف مورد نياز را مي‌آورديم:
تعريف 1-6 اگر G=(V,E) يك گراف جهتدار و v و w روش متمايزي از G باشند:

(الف) مسيرهايي ‌ازvبهwرا كه‌‌كمان‌مشترك‌ندارند را ‌مسيرهايي‌جهت‌دار ‌كمان–مجزا مي‌نامند.
(ب) مسـيرهايي از v بـه w را كـه راس مـشترك نـدارنـد را
مسيرهاي جهت دار رأس – مجزا مي‌نامند.
قضيه 1-4 فرض كنيد N يك شبكه با منبع a و چاهك z باشد كه، ظرفيت هاي كمان آن، واحد است. در اين صورت:
(الف) مقدار شارش ماكزيمم در N برابر است با بيشترين تعداد (a,z) – مسيرهاي جهت دار كمان – مجزا در N و
(ب) ظرفيت برش مينيمم در N برابر است با كمترين تعداد كمان هايي كه حذف آنها باعث از بين رفتن (a,z) – مسيرهاي جهت در N مي‌شود.
اثبات فرض كنيد يك شارش ماكزيمم در N و گراف جهت داري باشد كه از حذف تمام كمان هاي صفر از D (گراف جهت دار زمينة N) به دست آمده است. چون ظرفيت هر كمان N واحد است، به ازاي هر شرط برقرار است. درنتيجه داريم:
(1)
(2) به ازاي هر
( = درجه ورودي رأس V و = درجة خروجي رأس )
بنابراين به تعداد ، (a,z) – مسير جهت دار كمان – مجزا در و در نتيجه در D وجود دارد. درنتيجه اگر بيشترين تعداد (a,z) – مسيرهاي جهت دار كمان مجزا در N را m فرض كنيم داريم:
(1-5)
اينك فرض كنيد كه ، ، ...، يك سيستم دلخواه از m، (a,z) – مسير جهت دار كمان – مجزا در N باشد، تابع f را روي E به صورت زير تعريف مي‌كنيم:

به وضوح f يك شارش با مقدار m در N است. از طرفي چون يك شارش ماكزيمم است، داريم:
(1-6)
از روابط 1-5 و 1-6 نتيجه مي‌شود كه:

حال فرض كنيد كه ، يك برش مينيمم در N باشد. در اين صورت در ، هيچ رأسي از قابل دستيابي از رأس هاي P نيست. به ويژه z قابل دستيابي از a نمي باشد. بنابراين يك مجموعه از كمان هايي است كه حذف آن ها باعث از بين رفتن تمام مسيرهاي جهت دار مي‌شود. اگر كمترين تعداد كمان هايي را كه با حذف آن ها، تمام مسيرهاي جهت دار در N نابود مي شوند، n درنظر بگيريم، داريم:
(1-7)
حال فرض كنيد كه مجموعه اي از n كمان باشد كه حذف آن ها باعث از بين رفتن تمام مسيرهاي جهت دار مي شود و مجموعه تمام رأسهايي كه در ، قابل دستيابي از a هستند را با P نمايش مي دهيم. از آن جايي كه و ، درنتيجه يك برش در N است. علاوه بر اين طبق تعريف ، شامل هيچ كماني از نيست و درنتيجه . با توجه به اين كه يك برش مينيمم است، نتيجه مي گيريم كه:
(1-8)
با تركيب روابط 1-7 و 1-8 داريم
.
قضيه 1-5 فرض كنيد y و x دو رأس از گراف جهت دار D باشند. در اين صورت بيشترين تعداد (x,y) مسيرهاي جهت دار كمان – مجزا در D برابر است با كمترين تعداد كمان هايي كه حذف آن ها باعث از بين رفتن تمام
(x,y) – مسيرهاي جهت دار D مي شود.
اثبات با اختصاص يافتن ظرفيت واحد به هر يك از كمان هاي D، به يك شبكة N با منبع و چاهك مي‌رسيم. با توجه به قضيه 1-4 و قضيه شارش ماكزيمم – برش مينيمم (قضيه 1-3) نتيحه روشن است.
با يك ترفند ساده، بلافاصله به يك نسخه غيرحهت دار از قضية 1-5 دست مي يابيم.
قضيه 1-6 فرض كنيد y و x دو رأس از گراف G باشند. در اين صورت بيشترين تعداد (x,y) مسيرهاي يال – مجزا در G برابر است، با كمترين تعداد يالهايي كه حذف آن ها باعث از بين رفتن تمام

(x,y) - مسيرهاي G مي شود.
اثبات قضيه 1-5 را روي ، گراف جهت دار وابسته به G به كار بسته و به نتيجة مورد نظر مي‌رسيم (گراف جهت دار وابستة G كه آن را با D(G) نمايش مي‌دهيم، گراف جهت داري است كه از جايگزين نمودن هر يال e از G با دو كمان غير هم جهت از بين دو سر e به دست مي آيد .
نتيجة 1-4 گراف G، k – همبند يالي است اگر و تنها اگر هر دو رأس متمايز G با حداقل k مسير يال – مجزا به يكديگر وصل شده باشند.
اثبات ابتدا به يادآوري تعريف k – همبند يالي مي پردازيم.
يك برش يالي G، زير مجموعه اي از E به شكل مي باشد كه در آن، يك زيرمجموعه P غير ت

هي از مي باشد يك روش يالي با k عنصر را يك
-k برش يالي مي‌ناميم. اگر G غير بديهي و يك برش يالي از G باشد. آنگاه ناهمبند خواهد بود. بنابراين همبندي يالي G، را به عنوان كوچكترين K اي تعريف مي‌نماييم كه به ازاي آن، G داراي يك -k برش يالي باشد. اگر G بديهي باشد برابر صفر تعريف مي شود. بنابراين ، اگر G بديهي يا ناهمبند باشد و همچنين ، اگر G گراف همبند با يك برشي باشد. اگر ، G را -k همبند يالي مي ناميم. بنابراين تمام گراف‌ها همبند غير بديهي همبند يالي هستند.
حال با تعريف -k همبند يالي و با استفاده از قضيه 1-6، اين مطلب حاصل مي شود .
اكنون نسخه رأسي قضاياي فوق را بررسي مي‌كنيم.
قضيه 1-7 فرض كنيد z و a دو رأس از گراف جهت دار D باشند به طوريكه a مستقيماً به z وصل نشده باشد در اين صورت بيشترين تعداد - مسيرهايي جهت دار مجزاي داخلي در D برابر است با كمترين تعداد رأس هايي كه حذف آنها باعث از بين رفتن تمام (a,z)- مسيرهاي جهت دار در D مي‌شود.
اثبات گراف جديد را از روي D به صورت زير مي‌سازيم:
الف) هر رأس را به دو رأس جديد و مي‌شكنيم و آن ها را كمان به يكديگر وصل مي‌كنيم.
ب) هر كمان D با سر را با كمان جديدي كه سر آن است و هر كمان D با دم را با كمان جديدي كه دو آن است. جايگزين مي‌كنيم. اين عمل در شكل 1-7 نشان داده شده است.