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

Ford algoritmi.  tarmoqni qaraymiz, bu yerda,  – orgraf, b esa G orgrafning yoylarini manfiyma  ) haqiqiy sonlar to'plamiga akslantiruvchi funksiya.
G orgraf faqat bitta manbaga va faqat bitta o'pqonga ega bo'lin, deb faraz qilamiz. Maksimal oqim va minimal kesim haqidagi Ford-Falkerson teoremasining yuqoria keltirilgan isboti tarmoqdagi maksimal oqimni topish algoritmnituzish nuqtayi nazaridan konstruktivdir.
T tarmoqning uchlariga, ya'ni V to'plamelementlariga 0,1,2,,,,,,m raqamlarni mos qo'yib, tarmoqning manbayi 0 uch, o'pqoni esa m uch bo'lsin, deb hisoblaymiz.Bu tarmoqda Ford tomonidan taklif etilgan maksimal oqimni topish algoritmi bilan tanishamiz.Ford algoritmining jadvallar bilan ish ko'riladigan jarayon dastlabki, umumiy (takrorlanuvchi) va yakuniy qadamlardan ibort bo'lib, u quyida keltirilgan'
Dastlabki qadam.O'lchamlari  bo'lgan jadvalniquyidagicha tuzamiz. Agar  yoyning o'tkazish qobilyati  noldan kattava unga simmetrik  yoyning o'tkazish qobilyati  nolga teng bo'lsa, u holda jadvalning katagiga  sonni, uning asosiy dioganaliga nisbatan simmetrik  katagiga esa, nolni yozamiz. Agar  bo'lsa, u holda jadvalning  va kataklari bo'sh qoldiriladi.
Umumiy qadam.Tarmoqning manbayidan o'pqoniga o'tkazish xususiyati noldan katta bo'lgan yo'l izlaymiz.Buning uchun jadvalning tarmoqdagi 0 uchga mos keluvchi ustuniga (*) belgisini qo'yamiz.Jadvalning o uchga mos satridan  elementlarni topib, bu elementlar joylashgan ustunlarni o raqami bilan belgilaymiz.
Natijada tarmoqning musbat o'tkazish xususiyatiga ega bo'lgan barcha  yoylari aniqlanadi.Bu yoylar manbadan o'pqonga boruvchi yo'lning dastlabki yoylaridir.
Belgiga ega ustunlar raqamlari bilan bir xil raqamli satrlarning har birini ketma-ket tekshirib chiqamiz. Tekshirish jarayonida har bir shunday satrda, masalan, jadvalning uchga mos satrida belgiga sga bo'lmagan ustunlardan  elementlarni izlaymiz va shunday element topilsa bu element joylashgan ustunni tekshirayotgan satr raqami (ya'ni ) bilan belgilaymiz.
Shu tarzda davom ettirilsa, natijada manbadan o'pqonga boruvchi musbat o'tkazish xususiyatli izlangan yo'lning navbatdagi yoylari bo'lib xizmat qilishi mumkin bo'lgan yoylar topilgan bo'ladi.Jadvaldgi belgiga esa ustunlar raqamlariga mos raqamli tarmoqning uchlariga to'g'ri keluvchi satrlarni tekshirish jarayonini quyidagi mumkin bo'lgan hollardan biri amalga oshguncha davom ettiramiz:
Jadvalning o'pqonga mos ustuni belgilanadi;
Jadvalning yangi ustunlarini(shu jumladan, o'pqonga mos ustunini ham) belgilash imkoniyati yo'q.
Agar a) hol ro'y bersa, u holda tarmoqda manbadan o'pqonga boruvchi musbat o'tkazish xususiyatiga ega bo'lgan biron  yo'l bor. Bu yo'l quidagicha aniqlanadi.
Jadvalning o'pqonga mos m ustunining belgisi k bo'lsin deb faraz qilaylik.
Demak,  yo'lda m uchdan oldingi uch k uchdir. Jadvalning k uchga mos satri va m uchga mos ustuni kesishgan (k,m) katagidagi  elementiga  belgisi  shu katakka asosiy dioganalga nisbatan simmetrik hisoblangan (m,k) katakdagi  elementga esa  belgisi  qo'yamiz.
Endi jadvalning k uchga mosustuni belgisi r raqami bo'lsin, deb faraz qilamiz. Jadvaldagi  elementdan jadvalning k uchga mos ustuni bo'ylab harakatlnib, uning r uchga mos satriga o'tamiz va elementga  belgi, asosiy dioganalga nisbatan simmetrik  elementga esa  belgi qo'yamiz.  va belgilar qo'yish jarayonini manbaga mos 0 satrga kelib undagi mos elementga  belgi, simmetrik elementga esa  belgi qo'yguncha davom ettiramiz.Umumiy qadamning 2-bandiga o'tamiz.
Agar b) hol bajarilsa, bu holda manbadan o'pqonga boruvchi musbat o'tkazish xususiyatiga ega bo'lgan boshqa yo'l yo'q.Shuning uchun umumiy qadamni bajarish jarayoni tugaydi.
Jadvalning belgilangan ustunlariga mos orgrafning uchlari minimal o'tkazish qobilyatiga ega bo'lgan  kesim uchun  to'plamni tashkil etadi, orgrafning qolgan uchlari esa  to'plamga tegishlidir. uchdan chiquvchi va  uchga kiruvchi barcha  yoylar to'plami berilgan tarmoq uchun minimalkesimdir. Yakuniy qadamga o'tamiz.
2. topilgan yo'l o'tkazish xususiyatining  qiymatini topamiz. Tabiiyki, son  yo'lni tashkil etuvchi yoylar o'tkazish xususiyatlarining eng kichigiga teng bo'ladi, ya'ni
 .
Umumiy qadamning 3-bandiga o'tamiz.
3. Topilgan  yo'lga tegishli yoylarning va ularga simmetrik yoylarning qolgan o'tkazish xususiyatlarini aniqlaymiz. Buning uchun jadvalning  belgisi bo'lgan  elementlaridan  sonni ayirib,  belgili  elementlariga esa  sonni qo'shib, natijalarni jadvalga mos o'rinlariga yozamiz.Jadvalning  yoki  belgisi bo'lmagan elementlari o'zgarmaydi.Jadvaldagi barcha belgilarni olib tashlaymiz. Natijada o'tkazish xususiyatlari o'zgargan tarmoqqa mos va dastlabki jadvalga o'xshash bo'lgan yangi jadvalni hosil qilamiz. Umumiy qadamning 1-bandiga o'tamiz.
Yakuniy qadam.Dastlabki jadvalning elementlaridan oxirgi qadamda hosil bo'lgan jadvalning mos elementlarini ayiramiz.Natijada musbat elementlari  yoyning mos  oqim miqdorlariga teng bo'lgan, elementlariesa asosiy dioganaliga nisbatan simmetrik joylashgan oxirgi jadvalni hosil qilamiz. Tarmoqdagi maksimal oqim miqdori  oxirgi jadvalning manbaga mos satri yoki o'pqonga mos ustuni elementlari yig'indisiga, ya'ni

Bumaksimaloqimqiymatiniumumiyqadamnibajarishjarayonlaridaaniqlanganbarcha sonlarni qo'shib ham hosil qilish mumkin.