Mustaqil ish

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.