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.2§.Tarmoqlar. Ford algoritmi.
Tarmoq tushunchasi.Graflar nazariyasida hozirgacha ba'zi iboralar bo'yicha umumiy kelishuv qaror topmaganligini qayd qilgan edik. Bu fikr graflar nazariyasining tarmoq va tarmoqqa oid tushunchalarri bilan ish ko'rganda yaqqol nomoyon bo'ladi. Ba'zan, (tarmoq) iborasining o'rniga (to'r) iborasini ham qo'llaydilar.
Berilgan  to'plam va har bir  elementi M dan olingan  majmuani tarmoq, deb ataymiz va  bilan belgilaymiz, bu yerda  M to'plamning obyektlari tarmoq uchlari deb,  majmuadagi obyektlar esa tarmoq qutblari, deb ataladi.
Yuqorida eslatilgan kitobda ta'kidlanishicha:  Adabiyotda tarmoq tushunchasiga yaqin tushunchalar ham uchraydi, masalan,  Blok-sxema tushunchasiga,  gippergraf tushunhasi. Blok-sxema tushunchasi tarmoq tushunchasidan oldin paydo bo'lgan, gippergraf tushunchasi esa keyinroq .
Gippergraf tushunchasi – bu graf tushunchasining shunday umumlashmasiki, bunda qirralar nafaqat ikki elementli bo'lishi, ular uchlar to'plamining istlgan qism to'plamlari bo'lishi ham mumkin.
Graf tushunchasining turli umumlashmalarini ma'qullagan hamda bunday umumlashmalar turli masalalarni hal etishda zarur qurol sifatida ishlatilishini ta'kidlagan holda (10) kitobdagi tarmoq tushunchasining bir-biriga ekvivalent bo'lgan quyidagi ikki ta'rifni keltiramiz:

1. 
   Har bir a yoyiga  manfiymas haqiqiy son mos qo'yilgan N orgraf tarmoq, deb ataladi;
   
2. 
   Tarmoq deb shunday  juftlikka aytiladi, bunda D=(U,V) – orgraf,  esa D orgrafning yoylari to'plamini manfiymas haqiqiy sonlar to'plamiga akslantiruvchi funksiya.
   

Tarmoqdagi oqimlar.Graflar (orgraflar) bilan bog'liq ko'plab tushunchalarni osonlik bilan tarmoqlar uchun ko'chirish mumkin.
 tarmoq berilgan bo'lsin, bu yerda,  – bog'lamli graf (yoki orgraf, yo bo'lmasa, aralash graf), b esa G grafning yoylarini manfiymas  haqiqiy sonlar to'plamiga akslantiruvchi funksiya. G grafda sirtmoq va karrali qirra yoki yoylar bo'lmasin deb faraz qilamiz. Ikkita  uchlarni tutashtiruvchi orientirlanmagan yoyni (qirrani) ikkita orientirlangan yoylarga almashtirish mumkin, deb hisoblaymiz. Shuning uchun bundan buyon G grafni orgraf, deb hisoblash mumkin.
Ta'kidlaymizki, (tarmoq) tushunchasi har bir yoyga bir nechta sonlarni mos qo'yish imkoniyatini beradi, graf (orgraf)da esa yoy faqatgina mos uchlarning tutashtirilgan yoki tutashtirilmaganligini aniqlaydi, xolos. Har bir ( , ) yoyga manfiymas  sonni qo'yib, bu sonni yoyning o'tkazish qobilyati, deb ataymiz. Tarmoqning har bir  uchi uchun quyidagi tushunchalarni kiritamiz:  uchning chiqish yarimdarajasi  - bu uchdan chiquvchi barcha yoylar o'tkazish qobilyatlari yig'indisi,  uchning kirish yarimdarajasi  – bu  uchga kiruvchi barcha yoylar o'tkazish qobilyatlari yig'indisi.
 ko'rishishlar haqidagi lemma bu yer quyidagicha ifodalanadi:
tarmoqning barcha uchlari chiqish yarimdarajalari yig'indisi ularning kirish yarimdarajalari yig'indisiga tengdir.
Grafning uchlari orasida kirish yarimdarajalari nolga teng bo'lganlari guruhini ajratamiz.Bu guruhga tegishli uchlarning har biri manba, deb ataladi.Shunga o'xshash, orgrafning chiqish yarimdarajalari nolga teng bo'lgan uchlari guruhini ham ajratish mumkin.Bu guruhga tegishli ar bir uch o'pqon, deb ataladi.
Faraz qilaylik, G orgraf faqat bitta  manbaga va faqat bitta  o'pqonga ega bo'lsin. Bir necha manba yoki o'pqonga ega bo'lgan tarmoqning orgrafiga yangi elementlar qo'shib olish yo'li bilan yuqoridagi xususiy holga osonlik bilan keltiriladi.
G orgrafning har bir ( , ) yoyiga manfiymas  sonlar mos qo'yilgan bo'lib, biron  uchun quyidagi shartlar bajarilsin:
1)

2. 
   G orgrafda mavjud barcha ( , ) yoylar uchun 
   

Bu shartlar bajarilganda  to'plamga T tarmoqdagi  manbadan  o'pqonga yo'nalgan oqim deb, p miqdorga esa, bu X oqimning miqdori, deb ataladi. 1) va 2) shartlarni qanoatlantiruvchi har bir  songa
( , ) yoy bo'ylab oqim yoki yoy oqimi deyiladi.
Yuqoridagi 1) shartga ko'ra, manba va o'pqondan farqli istalgan uchga kiruvchi oqim shu uchdan chiquvchi oqimga tengdir, 2) shartga ko'ra esa, istalgan yoy bo'ylab oqim miqdori shu yoyning o'tkazish qobilyatidan oshmaydi. 1) shartdan ko'rinib turibdiki, manbaga insident yoylar bo'yicha oqimlar yig'indisi o'pqonga insident yoylar bo'yicha oqimlar yig'indisiga tengdir:

1-misol. 1-shakldamanbasi vao'pqoni bo'lgan tarmoqtasvirlanganbo'lib, uningyoylariyonigamoso'tkazishqobilyatlariyozilgan, bunda
 ,


Bu tarmoq chun
ekanligi shakldan ko'rinib turibdi.
Tarmoqning har bir uchi uchun chiqish yarimdarajalari va kirish yarimdarajalarini aniqlaymiz: 

BerilganTtarmoqorqali manbadan o'pqonda 4 kattalikka ega bo'lgan X oqimni quyidagi sonlar to'plami ilan ifodalash mumkin: . QaralayotganXoqimningmiqdori .
Tarmoq bo'ylab o'tkazish mumkin bo'lgan oqimlar orasida miqdori eng katta (maksimal) oqimni topish amaliyot nuqtayi nazaridan katta ahamiyatga egadir. Bunday oqimlar maksimal oqimlar , deb ataladi. 1-misolda keltirilgan oqim maksimal oqim emas, chunki berilgan tarmoq uchun miqdori 5 bo'lgan oqim bor. Albatta, umumiy holda tarmoqda bir necha turli maksimal oqimlar bo'lishi mumkin.
Maksimal oqimni o'rganishda quyidagi tushunchalarni kiritish maqsadga muvofiqdir.To'yingan yoy- bu yoy bo'ylab oqim miqdori uning o'tkazish qobiliyatidan kichik.
2-misol.Birinchi misolda qaralgan tarmoq uchun aniqlangan X oqimda  bo'lgani uchun  to'yinmagan,  esa to'yingan yoylardir.
Tarmoqdagi oqimlarni o'rganishda, zanjir tushunchasi muhim rol o'ynaydi.Bu yerda zanjir deganda tarmoqdagi yo'nalishi e'tiborga olinmasdan bir-biriga ulangan yoylar ketma-ketligini tushunamiz. Biron zanjirga tegishli yoyning yo'nalishi zanjirdagi uchlar ketma-ketligini o'tish yo'nalishiga mos tushsa, bu yoyni to'g'ri yoy deb, aks holda esa, uni teskari yoy deb ataymiz.
Tarmoqdagi oqimlarni tadqiq qilganda kesim tushunchasi ham muhim hisoblanadi. T tarmoqning G orgrafi uchlari to'plami V ni o'zaro kesishmaydigan hamda har biri bo'sh bo'lmagan ikkita  qism to'plamlarga ajratamiz, ya'ni  .
Boshlang'ich uchi  to'plamga, oxirgi uchi esa  to'plamga tegishli bo'lgan barcha yoylar to'plamini kesim deb ataymiz.Kesimni ( bilan belgilaymiz.
Agar  kesim bo'lib,  manba R to'plamga,  o'pqon esa  to'plamga tegishli bo'lsa, u holda  ga  manbani  o'pqondan ajratuvchi (yoki ayiruvchi kesim, deb ataladi.
Har bir kesimga qiymati kesimni tashkil etuvchi barcha yoylar o'tkazish qobiliyatlari yig'indisiga teng bo'lga vakesimning o'tkazish qobiliyati (yoki miqdori)deb ataluvchi  son mos qo'yilishi mumkin:

Barcha mumkin bo'lgan kesimlar ichida o'tkazish qobiliyati eng kichik bo'lganini minimal kesim, deb ataymiz.
Tarmoqda bir necha turli maksimal oqimlar bo'lishi mumkin ekanligini yuqorida ta'kidlagan edik. Xuddi shunga o'xshash, tarmoqda bir necha turli minimal kesimlar bo'lishi ham mumkin.
Ravshanki, agar tarmoq boshlang'ich uchi  manbada va oxirgi uchi  o'pqonda bo'lgan zanjirdangina iborat bo'lsa, bu tarmoq bo'ylab o'tkazish mumkin bo'lgan maksimal oqim qiymati shu zanjirni tashkil etuvchi yoylarning o'tkazish qobiliyatlarining minimal qiymati bilan chegaralangan bo'ladi. Shu tufayli, bu yerda, minimal o'tkazish qobiliyatiga ega bo'lgan yoy tarmoqning (zanjirning)  deb atalishi joyizdir.
Tarmoqdagi  manbani  o'pqondan ajratuvchi  kesim iborasi istalgan tarmoqda  iborasining o'xshashi sifatida qaralishi mumkin.
Faraz qilaylik, –T tarmoqdagi qandaydir oqim bo'lsin. Bu tarmoqdagi  uchdan  uchga yo'nalgan biron  yo'l bo'ylab oqim shu yo'l yoylaridagi oqimlarning eng kichik qiymati sifatida aniqlanadi:

Tabiyki, tarmoqdagi X oqimning miqdori  uchun

Tengliko'rinlidir, buyerda, M-G-orgrafdagi uchdan uchga yo'nalgan barcha yo'llar to'plamidan iborat.
Kesimningta'rifidanko'rinibturibdiki,  uchdan uchga olib boruvchi ixtiyoriy  yo'l shu  va uchlarni ajratuvchi har qanday  kesimning hech bo'lmaganda bitta yoyini o'zida saqlaydi.Shuninguchun, agarixtiyoriy kesimningbarchayoylarinitarmoqdanolibtashlasak, uholdaG-orgrafda uchdan  uchga boradigan bironta ham yo'l ( va , demak, oqim ham ) mavjud bo'lmaydi.
Demak, yuqorida aytilganlarni hisobga olib tarmoqdagi oqim miqdori  bilan ixtiyoriy  kesimning o'tkazish qobiliyati  uzviy bog'langan, degan xulosaga kelish mumkin. Bu bog'lanish quyidagi teoremada o'zining aniq ifodasini topgan.
1-teorema. tarmoqdagi ixtiyoriy X oqim miqdori  shu tarmoqdagi  manba o'pqonni ajratvchi har qanday  kesimning o'tkazish qobilyatidan oshmaydi, ya'ni  .
Isboti. tarmoqdagi X oqim ta'rifidan bevosita quyidagi tengliklar kelib chiqadi:


Bu tengliklarning mos tomonlaridagi ifodalarni qo'shib va o'xshash hadlarni ixchamlab,

Tenglikni olamiz. 2) shartni va

ekanligini hisobga olsak, oxirgi tenglikdan


munosabat kelib chiqadi.