Mustaqil ish fan : Diskret tuzilmalar Mavzu: Grafda turg`unlik to`plami. Grafning ichki va tashqi turg`unliklari soni Topshirdi : 730-21 guruh talabasi Hafizov Shukrullo

2-teorema. Istalgan tarmoqda manbadan o'pqonga maksimal oqimning miqdori mnbani o'pqondan ajratuvchi minimal kesimning o'tkazish qobilyatiga teng.
Isboti. tarmoq orgraf,  manba,  o'pqonvaberilgantarmoqdagimaksimaloqimningmiqdoribo'lsin.
Agartarmoqdashunday oqimtopilsaki, uning miqdorbiror kesimningo'tkazishqobilyatigatengbo'lsa, 1-teoremadanshun maksimaloqim,  esaminimalkesimbo'lishikelibchiqadi. Demak, teorema isbotiga ega bo'lish uchun  tenglik o'rinli bo'ladigan  kesimni qurish mumkinligini ko'rsatish yetarli.
Bunday kesimni qurish maqsadida tarkibida, albatta,  uch bor bo'lgan, lekin  uchni saqlamaydigan  to'plamni aniqlash zarur.Bu  to'plam  uchdan chiquvchi zanjir bilan tutashtirish mumkinbo'lgan uchlar to'plamidan iborat bo'ladi.V to'plamning qolgan uchlari  to'plamni tashkil etadi.
 maksimal oqim bo'lsin, deb faraz qilmiz.
Shu oqimga mos  to'plamning elementlarini ketma-ket ravishda quyidagi qoida bo'yicha aniqlaymiz:
- ;
- agar bo'lsa u holda  ;
- agar bo'lsa u holda  .
Agar  to'plamni aniqlash jarayonida  uchni  to'plamga kiritish imkoniyati topilmasa, ya'ni  bo'lsa, u holda izlanayotgan  kesimni qurish mumkin bo'ladi.
Teskarisini faraz qilamiz, ya'ni  bo'lsin. U holda  to'plamning aniqlanish qoidasiga asoslanib, shunday zanjirni qurish mumkinki, uning barcha to'g'ri yoylari oqimga to'yinmagan, teskari yoylarida esa oqim musbat bo;ladi.  zanjirning barcha to'g'ri yoylari to'plamini  , teskari yoylari to'plamini esa  deb belgilaymiz.
Quyidagi miqdorni qaraymiz: 
 Tushunarliki,  bo'ladi. Agar  yo'lning barcha to'g'ri yoylarida oqim  miqdorga oshirilib, uning barcha teskari yoylarida esa  miqdorga kamaytirilsa, u holda tarmoqdagi oqim miqdori  ga ortadi. Bu esa  oqimning maksimal oqimi ekanligiga ziddir.Olingan qarama-qarshilik  ekanligini ko'rsatadi.
Endi yuqorida bayon qilingan qoidani ketma-ket qo'llab, hosil qilingan  to'plam uchun  deb olsak, G orgrafning to'plamga tegishli uchlarining biridan chiqib  to'plamga tegishli uchlarning biriga kiruvchi barcha yoylar to'plami  kesimni tashkil etadi.
 to'plamning aniqlanishiga asosan, barcha ( yoylar oqimiga to'yingan  = ,  to'plamga tegishli uchlardan chiqib,  to'plamga tegishli uchlarga kiruvchi barcha  yoylarda esa oqim nolga teng bo'ladi. Shuning uchun, 1-teoremaning isbotida hosil qilingan

Formulaga ko'ra,

munosabatni olamiz. Demak, qurilgan  kesim uchun  tenglik bajariladi.Bu yerdan yuqoridagi eslatilgan mulohazalarga ko'ra, teorema isbotiga ega bo'lamiz.