Guliston davlat

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'pqon va berilgan tarmoqdagi maksimal oqimning miqdori bo'lsin.
Agar tarmoqda shunday oqim topilsaki, uning miqdor biror kesimning o'tkazish qobilyatiga teng bo'lsa, 1-teoremadan shun maksimal oqim, esa minimal kesim bo'lishi kelib chiqadi. 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.