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

فهرست مطالب

مقدمه   
فصل 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 می‌شود...

منابع
1)    ریاضیات گسسته و تركیباتی ، مؤلف: رالف پ. گریمالدی
ترجمه: دكتر محمد علی رضوانی و دكتر بیژن شمس
انتشارات فاطمی
2)    درآمدی بر نظریه گراف، مؤلف: ربین ج. ویلسون
ترجمه: دكتر جعفر بی آزار
انتشارات دانشگاه گیلان
3)    نظریه گراف و كاربردهای آن، مؤلفین: جی.ای.باندی و یو.اس.ار.مورتی
ترجمه : حمید ضرابی زاده
موسسه فرهنگی هنری دیباگران تهران