بررسی شبکه ها و تطابق در گراف

فهرست مطالب

مقدمه   
فصل ۱   
شبکه ها   
۱-۱ شارش ها   
۱-۲ برش ها   
۱-۳ قضیه شارش ماکزیمم – برش مینیمم   
۱-۴ قضیه منجر      
فصل ۲   
تطابق ها   
۲-۱ انطباق ها   
۲-۲ تطابق ها و پوشش ها در گراف های دو بخش   
۲-۳ تطابق کامل   
۲-۴ مسأله تخصبص شغل       
منابع   

شبکه ها
۱-۱    شارش ها
شبکه های حمل و نقل، واسطه‌هایی برای فرستادن کالاها از مراکز تولید به فروشگاهها هستند. این شبکه ها را می‌توان به صورت یک گراف جهت دار با یک سری ساختارهای اضافی درنظر گرفت و آن ها را به صورت کارآیی مورد تحلیل و بررسی قرار داد. این گونه گراف های جهت دار، نظریه ای را به وجود آورده اند که موضوع مورد بحث ما در این فصل می باشد. این نظریه ابعاد وسیعی از کاربردها را دربرمی‌گیرد.
تعریف ۱-۱ فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:
(الف) رأس یکتایی مانند   وجود دارد به طوری که  ، یعنی درجه ورودی a، برابر ۰ است. این رأس a را مبدأ یا منبع می‌نامند.
(ب) رأس یکتایی مانند   به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجه خروجی z، برابر با ۰ است.
(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعه اعداد صحیح نامنفی، وجود دارد که به هر کمان   یک ظرفیت، که با   نشان داده می‌شود، نسبت می‌دهد.
برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.
مثال ۱-۱ گراف شکل ۱-۱ یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون  ، مقدار کالای حمل شده از a به z نمی‌تواند از ۱۲ بیشتر شود. با توجه به   بازهم این مقدار محدودتر می‌شود و نمی‌تواند از ۱۱ تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد  باید ظرفیتهای همه کمانهای بشکه را درنظر بگیریم.
تعریف ۱-۲ فرض کنیم   یک شبکه حمل و نقل باشد تابع f از E در N، یعنی مجموعه اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه
الف) به ازای هر کمان   و
ب) به ازای هر  ، غیر از مبدأ a یا مقصد  z ،   (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم 
مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف را قید ظرفیت می‌نامند.
شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همه رأسها به استثنای مبدأ و مقصد بر قرار  است.
مثال ۱-۲ در شبکه های شکل ۱-۲، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در   صدق می کند. در شکل ۱-۲ (الف)، شارش، وارد رأس   می شود،۵ است، ولی شارشی که از آن رأس خارج می شود ۴=۲+۲ است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل ۱-۲ (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.
توجه داشته باشید که هر شبکه، حداقل دارای یک شارش است، زیرا تابع fای که در آن به ازای هر   داشته باشیم:   در هر دو شرط تعریف
۱-۲ صدق می کند. این تابع، شارش صفر نامیده می شود.
تعریف ۱-۳ فرض کنیم f شارشی برای شبکه حمل و نقل N=(V,E) باشد.
الف) کمانی مانند e متعلق به این شبکه را اشباع شده می نامند هر گروه f(e)=c(e) اگر f(e)<c(e) این کمان را اشباع نشده می نامند.
ب) اگر a مبدأ N باشد،   را مقدار شارش می نامند.
مثال ۱-۳ در شبکه شکل ۱-۲ (ب) فقط کمان   اشباع شده است. هر یک از کمان‌های دیگر اشباع نشده است. مقدار شارش این شبکه
است. ولی آیا شارش دیگری مانند   وجود دارد که به  ؟
می‌گوئیم شارش fدر N، یک شارش ماکزیمم  است، هر گاه هیچ شارش دیگری مانند   در N با شرط   وجود نداشته باشد.
هدف ما در ادامه، تعیین یک شارش ماکزیمم است. برای انجام این کار، ملاحظه می‌کنیم که در شکل ۱-۲ (ب) داریم.
 
درنتیجه، شارش کل خارج شده از مبدأ a شارش کل وارد شده به مقصد z برابر  است.
نکته اخیر در مثال ۱-۳ شرط معقولی به نظر می‌رسد، ولی آیا در حالت کلی چنین وضعیتی روی می دهد؟ برای اثبات آن در مورد هر شبکه دلخواه به نوع خاصی از مجموعه های برشی که در قسمت بعد می‌آید، نیاز داریم.
۱-۲    برش ها
تعریف ۱-۴ اگر   یک شبکهء حمل و نقل و C یک مجموعه برشی برای گراف بیسوی وابسته به N به صورت   که در آن   باشد، C را یک برش یا یک برش a-z می نامند هرگاه حذف کمانهای C از شبکه مفروض به جدایی a و z منتهی شود.
ظرفیت هر برش، که با capC نشان داده می شود، با
(۱-۱)                             
یعنی مجموع ظرفیتهای همه کمانهای (y,w) که در آن   و  ، تعریف می‌شود.
مثال ۱-۴ هر یک از خمهای خط چین در شکل ۱-۳ برشی برای شبکه مفروض است. برش   از کمانهای بیسوی   تشکیل شده است. این برش رأسهای شبکه مفروض را بر دو مجموعه   و متمم آن، یعنی  ، افرازی می‌کند و در این مثال  . ] در برش  ، اگر یالهای سودار (از P به  )، یعنی یالهای  ، را درنظر بگیریم می بینیم که حذف این یالها به زیرگرافی با دو مؤلفه منتهی نمی شود. ولی، این سریال مینیمال اند، به این معنی که حذف آنها امکان پیدایش هر مسیر سودار  از a به z را از بین می برد[
برش   افراز   و   را برای رأسها القا می‌کند و دارای ظرفیت   است.
قضیه ۱-۱ فرض کنیم f شارشی در شبکه N=(V,E) باشد. اگر   برشی در N باشد، آنگاه Val(f)  نمی تواند از   تجاوز کند.
اثبات فرض کنیم رأس a مبدأ N و رأس Z مقصد آن باشد. چون  ، پس به ازای هر  ،  . درنتیجه، 
با توجه به شرط (ب) در تعریف شارش، به ازای هر   و  ، داریم
اگر برابریهای بالا را به هم بیفزاییم خواهیم داشت:
چون مجموعه های   و 
روی کل مجموعه متشکل از همه جفتهای مرتب متعلق به P×P محاسبه شده اند، با یکدیگر برابرند. درنتیجه،
(۱-۲)              
 به ازای هر  ، داریم   و از این رو،   و
(۱-۳)             .?
با توجه به قضیه ۱-۱ می‌بینیم که در شبکه ای مانند N، مقدار هر شارش کوچکتر از یا برابر با ظرفیت هر برش موجود در آن شبکه است. بنابراین مقدار شارش ماکزیمم نمی تواند از مینیمم ظرفیتهای برشهای شبکه تجاوز کند. در مورد شبکه شکل ۲-۳ می توان نشان داد که برش متشکل از یالهای   و   دارای ظرفیت مینیمم ۱۱ است. درنتیجه شارش ماکزیمم f برای این شبکه در   صدق می کند.
تعریف ۱-۵ برش C در N، یک برش مینیمم است، اگر هیچ برش دیگری مانند   در N با شرط   وجود نداشته باشد.
اگر   یک شارش ماکزیمم و   یک برش مینیمم به عنوان حالت خاصی از قضیه ۱-۱ داریم:   (1-4)            
نتیجه ۱-۱ فرض کنید f یک شارش و C یک برش باشد، به طوری که   در این صورت f یک شارش ماکزیمم و C یک برش مینیمم است.
اثبات فرض کنید   یک شارش ماکزیمم و   یک برش مینیمم باشد. در این صورت بنا بر رابطه ۱-۴ داریم:
و چون طبق فرض،  ، نتیجه می‌گیریم که   و   درنتیبجه f یک شارش ماکزیمم و C یک برش مینیمم است .?
در بخش آینده، عکس نتیجه ۱-۱ را اثبات خواهیم کرد، یعنی این که در رابطه ۱-۴ همواره تساوی برقرار است.
ولی، قبل از پرداختن به این مطلب، با توجه به برهان قضیه ۱-۱ ملاحظه میکنیم که مقدار هر شارش با
که در آن   برشی دلخواه در N است، بیان می شود. بنابراین، به محض آنکه شارشی در شبکه ای ساخته شد، به ازای هر برش   در این شبکه، مقدار شارش برابر است با مجموع شارشهای موجود در کمان های سودار از رأسهای P به رأسهای   منهای مجموع شارشهای موجود در کمان های سودار از رأسهای   به رأسهای P.
این نکته ما را به نتیجه زیر هدایت می کند.
نتیجه ۱-۲ اگر f شارشی در شبکه حمل و نقل N=(V,E) باشد، انگاه مقدار شارش خارج شده از مبدأ a برابر است با مقدار شارش وارد شده در مقصد z.
اثبات قرار می دهیم  . با توجه به نکته قبلی داریم:
چون   و  ، می‌بینیم که  
به همین ترتیب، به‌ازای   و   داریم 
درنتیجه
و این اثبات تمام است.?
۱-۳ قضیه شارش ماکزیمم – برش مینیمم
در این بخش الگوریتمی برای تعیین یک شارش ماکزیمم در شبکه ها ارائه می‌نمائیم. یکی از اساسی‌ترین ملزومات چنین الگوریتمی این است که در صورت دیدن یک شارش، بتواند تشخیص دهد آیا این شارش ماکزیمم هست یا خیر. بنابراین در شروع کار، نگاهی به این مسأله می‌اندازیم.
فرض کنید f یک شارش در شبکه N باشد. به هر مسیر S در N، یک عدد صحیح نامنفی l(S) به صورت روبرو نسب می‌دهیم:
که در آن:
به راحتی می توان دید که l(S)، بیشترین میزان ممکن برای افزایش شارش در طول S (تحت f) است، بدون اینکه به شرط الف در تعریف ۱-۲ آسیبی وارد شود. اگر  ، مسیر S را f- اشباع شده و اگر  ، S را f– اشباع نشده می‌نامیم (حالت اخیر معادل با این است که هر کمان رو به جلو از S، f – اشباع نشده و هر کمان معکوس از S، f- مثبت باشد). به طور ساده می‌توان گفت که یک مسیر f- اشباع نشده، مسیری است که از تمام ظرفیتش استفاده نشده است. مسیر -f افزایشی یک مسیر -f اشباع نشده از مبدأ a به مقصد z می باشد. به طور مثال اگر f شارش مشخص شده در شبکه شکل ۱-۴ (الف) باشد، در این صورت   یک مسیر -f افزایشی خواهد بود.   و   کمان‌های روبه جلوی S هستند و داریم  .
وجود یک مسیر -f افزایشی S در شبکه حائز اهمیت است، زیرا نشان می دهد که f شارش ماکزیمم نیست.
در حقیقت با فرستادن یک شارش اضافی l(S)، در طول S، می توان به شارش جدید  ، به صورت زیر رسید:
 
و در این حال داریم:   را شارش اصلاح شده بر پایه S می ‌خوانیم.
در شکل ۱-۴ (ب) شارش اصلاح شده شبکه ۱-۴ (الف) بر پایه مسیر -f افزایشی   نشان داده شده است.
شکل ۱-۴ (الف) مسیر -f افزایشی S (ب) شارش اصلاح شده بر پایه f
در شکل (الف)       
در شکل (ب) 
نقش مسیرهای افزایشی درنظریه شاره‌ها همانند مسیرهای افزوده درنظریه تطابق هاست. قضیه زیرمؤید این مطلب است (آن را با قضیه ۲-۱ مقایسه نمائید.)
قضیه ۱-۲ شارش 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 صفر باشد.
با به کارگیری قضیه ۱-۱ نتیجه می شود:
 
و اکنون با توجه به نتیجه ۱-۱ روشن می گردد که f، یک شارش ماکزیمم (و C یک برش مینیمم است.) ?
طی اثبات فوق، وجود یک شارش ماکزیمم و یک برش مینیمم C که در آن ها شرط   برقرار است، به اثبات رسید. بنابراین قضیه زیر که متعلق به فورد، فالکرسن (۱۹۵۶) است، نیز مستقیماً به اثبات می‌رسد:
قضیه ۱-۳ قضیه شارش ماکزیمم – برش مینیمم. در هر شبکه حمل و نقل   ، شارش ماکزیمم که می‌توان در N به دست آورد برابر است با مینیمم ظرفیتهای برشهای این شبکه.
اثبات بنابرقضیه ۱-۱ اگر   برشی با ظرفیت مینیمم در N باشد، مقدار هر شارشی در N مانند f در نابرابری   صدق می‌کند. برای تحقیق در وجود شارشی مانند f که به ازای آن داشته باشیم  ، الگوریتم زیر، که روش نشانگذاری نام دارد، مراحل لازم را در اختیار می گذارد. ?
روش نشانگذاری
مرحله ۱: در شبکه مفروض N، شارش آغازی f در N را به ازای هر کمان e متعلق به E با   تعریف می‌کنیم. این تابع در شرایط شارش صدق می‌کند.
مرحله ۲: مبدأ a را با   نشانگذاری می کنیم. (تین نشانگذاری نشان می دهد که در مبدأ a، هر اندازه ماده برای تحقق شارش ماکزیمم لازم باشد موجود است.)
مرحله ۳: به ازای هر رأس مانند x که مجاور از a است، x را به صورت زیر نشانگذاری می‌کنیم:
الف) اگر  ، تعریف می‌کنیم   و رأس x را با   نشانگذاری می‌کنیم.
ب) اگر  ، راس x را بدون نشان رها می‌کنیم. ] نشان   بر این امر دلالت دارد که شارش فعلی از a به x را می توان به مقدار   افزایش داد و این   واحد اضافی از مبدأ a تأمین می شود.[
مرحله ۴: تا زمانی که رأس نشانداری مانند   و یالی مانند (x,y) که در آن y بی‌نشان است، وجود دارد و رأس y  را به صورت زیر نشانگذاری می‌کنیم.
الف)اگر ،تعریف‌میکنیم   و رأس y را با   نشانگذاری می‌کنیم.
ب) اگر  ، رأس y را بدون نشان رها می‌کنیم.
]نشان   بر این امر دلالت دارد که شارش فعلی وارد شده و در رأس y را می توان به مقدار  ، که از رأس x می گیریم، افزایش داد.[
مرحله ۵: به همین ترتیب، تا زمانی که رأس نشانداری مانند   و کمانی مانند (y,x)، که در آن y بی نشان است، وجود دارد  رأس y مقابل  را به صورت زیر نشانگذاری می کنیم:
الف) اگر  ، راس y را با  ، که در آن   نشانگذاری می‌کنیم.
ب) اگر  ، رأس y را بدون نشان رها می کنیم.
J نشان   به ما می گوید که با کاهش شارش از y به x، شارش کل خارج شده از y به رأسهای نشاندار را می توان به اندازه   کاهش داد. در این صورت این   واحد را می توان برای افزایش شارش کل خارج شده از y با رأسهای بی نشان به کار گرفت.[
چون رأسی مانند y ممکن است مجاور به یا مجاور از بیش از یک رأس نشاندار باشد، نتایج این روش الزاماً یکتا نیست. علاوه بر این، اگر x نشانگذاری شده باشد، شبکه مورد بحث ممکن است شامل هر دو کمان (x,y) و (y,x) باشد و بنابراین، ممکن است دو نشان برای y حاصل شود. ولی این روش برای آن طراحی شده است که یک شارش ماکزیمم به دست دهد و این امکان هست که بیش از یک چنین شارشی موجود باشد. به هر حال هر بار که بتوان رأسی را به بیش از یک طریق نشانگذاری کرد، باید یکی را به دلخواه انتخاب کنیم.
ضمن اینکه روش نشانگذاری را در باره رأسهای شبکه مفروض به کار می‌بریم، مراحل ۴ و ۵ تا حد امکان در مورد مجموعه جاری (و در حال تغییر) رأسهای نشانگذاری شده تکرار می شوند. با هر تکرار دو حالت ممکن است روی رهد.
حالت ۱: اگر مقصد 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 می رود، به اندازه   واحد افزایش یا کاهش می‌یابد ]کاهش مربوط به وقتی است که رأسی (از این مسیر) نشان منفی داشته باشد[. پس از اتمام کار، همه نشانهای رأسها، به استثنای   که مربوط به مبدأ است، حذف می‌شوند. این فرایند تکرار می شود تا ببینیم آیا امکان دارد که بازهم شارش را افزایش دهیم یا نه.
حالت ۲: اگر روش نشانگذاری را تا حد امکان اجرا کنیم و مقصد z بی نشان باقی بماند، شارش ماکزیمم حاصل شده است. فرض کنیم P مجموعه رأسهایی از V باشد که نشانگذاری شده اند و  . چون رأسهای   نشانگذاری نشده اند، شارشهای موجود در کمان های (x,y)، که در آن   و  ، در   صدق می کنند.
همچنین، به ازای هر کمان (w,v)،   و  ، داریم  . درنتیجه، شارشی برای شبکه مفروض وجود دارد به طوری که مقدار شارش برابر  است با ظرفیت برش  . با توجه به قضیه ۱-۱ نتیجه می‌گیریم که این شارش یک شارش ماکزیمم است.
قبل از ارائه مثالی در باره روش نشانگذاری، یک نتیجه دیگر و چند تفسیر وابسته به آن را بیان می کنیم.
نتیجه ۱-۳ فرض کنیم N=(V,E) یک شبکه حمل و نقل باشد که در آن، به ازای هر  ، c(e) یک عدد صحیح مثبت است. آنگاه شارش ماکزیممی مانند f برای N وجود دارد به طوری که، به ازای هر کمان e، f(e) یک عدد صحیح نامنفی است.
در تعریف شبکه حمل و نقل و شارش (در یک شبکه حمل و نقل) می توانیم این امکان را مد نظر قرار دهیم که توابع ظرفیت و شارش توابعی حقیقی و نامنفی باشند. اگر در یک شبکه حمل و نقل ظرفیتها اعدادی گویا باشند، در این صورت رو نشانگذاری پایان پذیر است و به شارش ماکزیمم دست خواهیم یافت. ولی، اگر بعضی از ظرفیتها اعداد گنگ باشند، این امکان وجود دارد که این روش پایانی نداشته باشد، به این ترتیب که برای هر تکرار،  های کوچکتری پدید آید. علاوه بر این، ال. آرفورد جونیور و دی. آر. فاکرسون نشان دادند که این روش می تواند به یک شارش منتهی شود، ولی این شارش لزوماً یک شارش ماکزیمم نیست. وقتی ظرفیتهای گنگ پیش می آیند می توان اصلاحیه ارائه شده به وسیله جی. ادموندز. آر.ام.کارپ را به کار برد و در این صورت این روش (پس از تعدادی متناهی مرحله) پایان می‌پذیرد و به یک شارش ماکزیمم دست می‌یابیم.
مثال ۱-۵ با استفاده از روش نشانگذاری، شارش ماکسیممی برای شبکه حمل و نقل شکل ۱-۵ (الف) بیابید. در این شبکه، هر کمان با جفت مرتبی مرکب از x و y نشانگذاری شده است، که در آن x ظرفیت کمان است و   شارش آغازی برای شبکه را نشان می دهد. شکل ۱-۵ (ب) نخستین کاربرد روش نشانگذاری را در باره این شبکه نشان می دهد. در اینجا نشانگذاری مقصد z بر اساس انتخاب صورت گرفته است.   را به جای   به عنوان نشان انتخاب کرده ایم اگر از z به h به e به s به a بازگردیم و شارش موجود در هر ریال را به اندازه   افزایش دهیم، شارش جدید در شکل
۱-۵ (ب) را به دست می‌آوریم. شکلهای ۱-۵ (پ)، (ت)، (ث) و (ج) کاربردهای دوم، سوم، چهارم، و پنجم روش نشانگذاری را در باره شبکه مفروض نشان می‌دهند. ملاحظه می‌کنیم که چگونه رأس در شکل های ۱-۵ (ت) و (ج) نشان منفی دارد. همچنین، شکل ۱-۵ (ج) موقعیت دیگری نشانگذاری منفی را، این بار برای رأس d، به دست می دهد. اگر برای آخرین بار روش نشانگذاری را به کار ببریم، شبکه حمل و نقل مفروض مطابق شکل ۱-۶ نشانگذاری می شود. در اینجا مقصد z بی نشان است و حالت دوم در روش نشانگذاری مطرح می شود. اگرقرار دهیم  و ، می‌بینیم که شارش وارد شده به z
است. کمانهایی از N که با خم خط چین قطع شده اند کمانهای متعلق به مجموعه برشی (بیسوی) وابسته به برش   هستند. این برش از همه کمانهای به صورت  ، که در آن   و  ، تشکیل شده است.
۱-۴ قضیه های منجر
در این بخش، با استفاده از قضیه شارش ماکزیمم – برش مینیمم، تعدادی قضیه به دست خواهیم آورد که متعلق به منجر (۱۹۲۷) می‌باشند. ابتدا تعاریف مورد نیاز را می‌آوردیم:
تعریف ۱-۶ اگر G=(V,E) یک گراف جهتدار و v و w روش متمایزی از G باشند:
(الف) مسیرهایی ‌ازvبهwرا که‌‌کمان‌مشترک‌ندارند را ‌مسیرهایی‌جهت‌دار ‌کمان–مجزا می‌نامند.
(ب) مسـیرهایی از v بـه w را کـه راس مـشترک نـدارنـد را
مسیرهای جهت دار رأس – مجزا می‌نامند.
قضیه ۱-۴ فرض کنید N یک شبکه با منبع a و چاهک z باشد که، ظرفیت های کمان آن، واحد است. در این صورت:
(الف) مقدار شارش ماکزیمم در N برابر است با بیشترین تعداد (a,z) – مسیرهای جهت دار کمان – مجزا در N و
(ب) ظرفیت برش مینیمم در N برابر است با کمترین تعداد کمان هایی که حذف آنها باعث از بین رفتن (a,z) – مسیرهای جهت در N می‌شود.
اثبات فرض کنید   یک شارش ماکزیمم در N و   گراف جهت داری باشد که از حذف تمام کمان های   صفر از D (گراف جهت دار زمینه N) به دست آمده است. چون ظرفیت هر کمان N واحد است، به ازای هر   شرط   برقرار است. درنتیجه داریم:
(۱)  
(۲) به ازای هر 
( = درجه ورودی رأس V و   = درجه خروجی رأس  )
بنابراین به تعداد  ، (a,z) – مسیر جهت دار کمان – مجزا در   و در نتیجه در D وجود دارد. درنتیجه اگر بیشترین تعداد (a,z) – مسیرهای جهت دار کمان مجزا در N را m فرض کنیم داریم:
(۱-۵)                 
اینک فرض کنید که  ،  ، …،  یک سیستم دلخواه از m، (a,z) – مسیر جهت دار کمان – مجزا در N باشد، تابع f را روی E به صورت زیر تعریف می‌کنیم:
به وضوح f یک شارش با مقدار m در N است. از طرفی چون   یک شارش ماکزیمم است، داریم:
(۱-۶)                     
از روابط ۱-۵ و ۱-۶ نتیجه می‌شود که:                    
حال فرض کنید که  ، یک برش مینیمم در N باشد. در این صورت در  ، هیچ رأسی از   قابل دستیابی از رأس های P نیست. به ویژه z قابل دستیابی از a نمی باشد. بنابراین   یک مجموعه از کمان هایی است که حذف آن ها باعث از بین رفتن تمام   مسیرهای جهت دار می‌شود. اگر کمترین تعداد کمان هایی را که با حذف آن ها، تمام   مسیرهای جهت دار در N نابود می شوند، n درنظر بگیریم، داریم:
(۱-۷)                 
حال فرض کنید که   مجموعه ای از n کمان باشد که حذف آن ها باعث از بین رفتن تمام   مسیرهای جهت دار  می شود و مجموعه تمام رأسهایی که در  ، قابل دستیابی از a هستند را با P نمایش می دهیم. از آن جایی که   و  ، درنتیجه   یک برش در N است. علاوه بر این طبق تعریف  ،   شامل هیچ کمانی از   نیست و درنتیجه  . با توجه به این که   یک برش مینیمم است، نتیجه می گیریم که:
(۱-۸)                  
با ترکیب روابط ۱-۷ و ۱-۸ داریم
                 .?
قضیه ۱-۵ فرض کنید y و x دو رأس از گراف جهت دار D باشند. در این صورت بیشترین تعداد (x,y) مسیرهای جهت دار کمان – مجزا در D برابر  است با کمترین تعداد کمان هایی که حذف آن ها باعث از بین رفتن تمام
(x,y) – مسیرهای جهت دار D می شود.
اثبات با اختصاص یافتن ظرفیت واحد به هر یک از کمان های D، به یک شبکه N با منبع   و چاهک   می‌رسیم. با توجه به قضیه ۱-۴ و قضیه شارش ماکزیمم – برش مینیمم (قضیه ۱-۳) نتیحه روشن است.?
با یک ترفند ساده، بلافاصله به یک نسخه غیرحهت دار از قضیه ۱-۵ دست می یابیم.
قضیه ۱-۶ فرض کنید y و x دو رأس از گراف G باشند. در این صورت بیشترین تعداد (x,y) مسیرهای یال – مجزا در G برابر  است، با کمترین تعداد یالهایی که حذف آن ها باعث از بین رفتن تمام (x,y) – مسیرهای G می شود.
اثبات قضیه ۱-۵ را روی  ، گراف جهت دار وابسته به G به کار بسته و به نتیجه مورد نظر می‌رسیم (گراف جهت دار وابسته G که آن را با D(G) نمایش می‌دهیم، گراف جهت داری است که از جایگزین نمودن هر یال e از G با دو کمان غیر هم جهت از بین دو سر e به دست می آید .?
نتیجه ۱-۴ گراف G، k – همبند یالی است اگر و تنها اگر هر دو رأس متمایز G با حداقل k مسیر یال – مجزا به یکدیگر وصل شده باشند.
اثبات ابتدا به یادآوری تعریف k – همبند یالی می پردازیم.
یک برش یالی G، زیر مجموعه ای از E به شکل   می باشد که در آن، یک زیرمجموعه P غیر تهی از   می باشد یک روش یالی با k عنصر را یک
-k برش یالی می‌نامیم. اگر G غیر بدیهی و   یک برش یالی از G باشد. آنگاه   ناهمبند خواهد بود. بنابراین همبندی یالی G،   را به عنوان کوچکترین K ای تعریف می‌نماییم که به ازای آن، G دارای یک -k برش یالی باشد. اگر G بدیهی باشد   برابر صفر تعریف می شود. بنابراین  ، اگر G بدیهی یا ناهمبند باشد و همچنین  ، اگر G گراف همبند با یک برشی باشد. اگر  ، G را -k همبند یالی می نامیم. بنابراین تمام گراف‌ها همبند غیر بدیهی همبند یالی هستند.
حال با تعریف -k همبند یالی و با استفاده از قضیه ۱-۶، این مطلب حاصل می شود .?
اکنون نسخه رأسی قضایای فوق را بررسی می‌کنیم.
قضیه ۱-۷ فرض کنید z و a دو رأس از گراف جهت دار D باشند به طوریکه a مستقیماً به z وصل نشده باشد در این صورت بیشترین تعداد  – مسیرهایی جهت دار مجزای داخلی در D برابر است با کمترین تعداد رأس هایی که حذف آنها باعث از بین رفتن تمام (a,z)- مسیرهای جهت دار در D می‌شود…

منابع
۱)    ریاضیات گسسته و ترکیباتی ، مؤلف: رالف پ. گریمالدی
ترجمه: دکتر محمد علی رضوانی و دکتر بیژن شمس
انتشارات فاطمی
۲)    درآمدی بر نظریه گراف، مؤلف: ربین ج. ویلسون
ترجمه: دکتر جعفر بی آزار
انتشارات دانشگاه گیلان
۳)    نظریه گراف و کاربردهای آن، مؤلفین: جی.ای.باندی و یو.اس.ار.مورتی
ترجمه : حمید ضرابی زاده
موسسه فرهنگی هنری دیباگران تهران