Graph processing masalalarini örganişni davom ettiramiz.

Minimum cut - graph'ni ikkiga şunday böliş kerakki, uning böliniş edge'lari bir-biriga eng kam (kuçsiz) boğlangan joyi bölsin. Oddiyroq aytganda, graph'ni ikkiga böliş uçun eng kam harajat / kuç talab etilsin.

Maximum flow - graph'da bir vertex'dan ikkinçi vertex'ga maksimum ötkazuvçanlik qobilyatini topiş masalasi körib çiqiladi.

Minimum cut va maximum flow haqida quyida batafsil töxtalamiz.

Minimum cut

Bizda pozitiv edge weight'larga ega directed graph mavjud. Boşlanğiç vertext - s, möljal vertex - t. Biz graph'ni minimum kuç sarflagan holda ikkiga bölişimiz kerak bölsin. Bunda s birinçi qismda, t ikkinçi qismda qoladi.

Kuç / sarf'ni aniqlaş uçun edge weight'laridan foydalanamiz, sarfni esa capacity deb ataymiz. Capacity deb, graph ikkiga bölinganda, ikki qismni boğlab turuvçi edge'lar weight'larining yiğindisi tuşuniladi.

Biz graph'ni ikkiga ajratişga urinib köramiz:

• Agar biz s ni bir tomonda qoldirib, qolgan vertex'larni ikkinçi qismga ajratsak, edge capacity s -> 0, s -> 5, s -> 10 edge weight'larining yiğindisiga teng böladi: 10 + 5 + 15 = 30
• Agar biz s, 1, 2 vertex'larni bir tomonda qoldirib, qolgan vertex'larni ikkinçi qismga ajratsak, edge capacity s -> 0, 1 -> 4, 2 -> 5 edge weight'larining yiğindisiga teng: 10 + 8 + 16 = 34. Capacity hisoblaşda içki boğlanişlar hisoblanmaydi.
• Agar biz s, 1, 2, 5 vertex'larni bir tomonda qoldirib, qolgan vertex'larni ikkinçi qismga ajratsak, edge capacity s -> 0, 1 -> 4, 5 -> t edge weight'larining yiğindisiga teng: 10+ 8 + 10 = 28

Hisoblaşlardan xulosa qiladigan bölsak, graph'ni {s, 1, 2, 5} va {0, 3, 4, t} qismlarga ajratiş uçun minimum sarf talab qilinar ekan.

Maximum flow

Graph'da bir vertex'dan ikkinçi vertex'ga maksimum ötkazuvçanlik qobilyatini topiş uçun edge'ga yana bir qiymat - flow kiritiladi. Flow - minimum qiymati 0, maksimum qiymati capacity'ga (weight'ga) teng bölgan son, bölib u edge'ning ötkazuvçanlik qobilyatini ifodalaydi. Flow'ni quvurlardan qança suv yuborişni aniqlovçi qiymat deb tasavvur qilsak, minimum = 0, suv ötmaydi, maksimum = capacity, quvurning ötkaziş qobilyatiga teng.

Şuningdek flow qiymati boşlanğiç va manzil vertex - s va t dan taşqari qolgan har bir vertex'ning muvozanatini, kiruvçi ötkazuvçanlik (inflow) va çiquvçi ötkazuvçanligini (outflow) belgilaş uçun ham kerak böladi. Bunda muvozanat bölişi uçun inflow = outflow bölişi kerak.

Graph'ga köra, max flow qiymati inflow'ga teng: 8 + 10 + 10 = 28.
Minimum cut ham 28 ga teng edi.

Biz keyingi maqolada maximum flow'ni topiş uçun Ford-Fulkerson algoritmini körib çiqamiz.

---

Maximum flow va minimum cut körinişidan bir-birining teskarisi bölsada, aslida bir biriga teng masalalar. Özingiz öylab köring, graph'ning maksimum ötkaziş qobilyati uning eng kuçsiz boğlangan joyining ötkaziş qobilyatidan katta bölolmaydi. Oddiyroq tuşuntirganda, quvurlardan suv yuborişda, quvurlarning kiçkina ulangan joyining ötkaziş qobilyatidan köp suv yubora olmaysiz. Uşbu tenglik maxflow-mincut teoremasi deb ataladi.