Ford-Fulkerson Algorithm

Ford-Fulkerson algoritmi — bu oqim tarmog'ida (flow network) yoki grafda manbadan (source) oqim qabul qiluvchiga (sink) yo'naltirilishi mumkin bo'lgan maksimal oqimni (maximum possible flow) hisoblash uchun mo'ljallangan greedy yondashuv algoritmidir.

Graf nazariyasida manba (S — Source) va iste'molchi (T — Sink) tugunlariga ega cho'qqilar hamda qirralar to'plamidan iborat tarmoq oqim tarmog'i (flow network) deb ataladi. S va T dan tashqari har bir cho'qqi orqali o'tayotgan oqim teng bo'lishi kerak, ya'ni kiruvchi oqimlar yig'indisi chiquvchi oqimlar yig'indisiga teng bo'ladi. S (manba) faqat oqim jo'nata oladi, T (iste'molchi) esa faqat oqim qabul qila oladi.

Ushbu algoritmni turli o'tkazuvchanlik sig'imiga ega quvurlar tarmog'i ichidagi suyuqlik oqimi sifatida tasavvur qilish mumkin. Har bir quvur ma'lum bir vaqt birligida o'tkaza oladigan maksimal suyuqlik sig'imiga (capacity) ega. Algoritmning vazifasi — tarmoq orqali manbadan iste'molchiga bir vaqtning o'zida eng ko'p qancha suyuqlik oqizish mumkinligini aniqlashdir.

Oqim tarmog'i grafigi (Flow network graph)

Foydalaniladigan asosiy atamalar

Augmenting Path

Kengaytiruvchi yo'l:

Bu oqim tarmog'ida manbadan (S) iste'molchiga (T) olib boruvchi va qo'shimcha oqim o'tkazish imkoniyati mavjud bo'lgan yo'ldir.

Residual Graph

Qoldiq graf:

Bu oqim tarmog'ida hali qo'shimcha oqim o'tkaza oladigan qirralar va ularning qoldiq sig'imlarini aks ettiruvchi grafdir.

Residual Capacity

Qoldiq sig'im:

Bu qirraning maksimal sig'imidan (capacity) ayni paytda oqib o'tayotgan joriy oqim (flow) ayirib tashlanganidan keyingi qolgan bo'sh sig'imdir: qoldiq_sig'im = maksimal_sig'im - joriy_oqim.

Ford-Fulkerson algoritmi qanday ishlaydi?

Algoritm quyidagi tartibda ishlaydi:

1. Barcha qirralardagi boshlang'ich oqimni 0 ga tenglashtiramiz.
2. Manba (S) va iste'molchi (T) o'rtasida kengaytiruvchi yo'l (augmenting path) mavjud ekan, ushbu yo'l bo'yicha mumkin bo'lgan oqimni umumiy oqimga qo'shamiz.
3. Qoldiq grafni (residual graph) yangilaymiz.

[!TIP] Eslatma: Agar zarur bo'lsa, teskari yo'nalishdagi yo'llarni (reverse-paths) ham hisobga olishimiz kerak. Chunki teskari yo'llarni hisobga olmasak, hech qachon global maksimal oqimni topa olmasligimiz mumkin.

Keling, ushbu tushunchalarni quyidagi misolda bosqichma-bosqich ko'rib chiqamiz.

Ford-Fulkerson algoritmi misoli

Boshlanishida barcha qirralarning oqimi 0 ga teng.

Oqim tarmog'i misoli (barcha oqimlar 0/capacity holatida)

1. Manba S dan T ga olib boruvchi ixtiyoriy yo'lni tanlaymiz. Ushbu qadamda S-A-B-T yo'lini tanladik.

   

   Yo'lni topish: S-A-B-T

   Ushbu uchta qirra orasidagi minimal sig'im 2 ga teng (B-T qirrasida sig'im 2). Shundan kelib chiqib, har bir yo'l uchun oqim/sig'im qiymatlarini yangilaymiz.

   

   Oqim qiymatlarini yangilash (2 birlik oqim yo'naltirildi)

2. Boshqa bir yo'lni tanlaymiz: S-D-C-T. Ushbu qirralar orasidagi minimal sig'im 3 ga teng (S-D qirrasida).

   

   Keyingi yo'lni topish: S-D-C-T

   Sig'imlarni mos ravishda yangilaymiz (oqimga 3 birlik qo'shiladi).

   

   Sig'imlarni yangilash

3. Endi teskari yo'nalishdagi B-D qirrasini ham hisobga olamiz. S-A-B-D-C-T yo'lini tanlaymiz. Ushbu yo'ldagi qirralarning eng kichik qoldiq sig'imi 1 ga teng (D-C qirrasida).

   

   Keyingi yo'lni topish: S-A-B-D-C-T

   Sig'imlarni yangilaymiz (oqimga yana 1 birlik qo'shiladi).

   

   Sig'imlarni yangilash

   To'g'ri va teskari yo'llar uchun sig'imlar alohida hisoblanadi.

4. Barcha oqimlarni qo'shamiz: 2 + 3 + 1 = 6. Bu ushbu oqim tarmog'ida manbadan iste'molchiga o'tkazilishi mumkin bo'lgan maksimal oqim (maximum flow) hisoblanadi.

[!NOTE] E'tibor bering, agar biror qirraning sig'imi to'liq to'lsa (oqim = sig'im), u holda bu yo'ldan boshqa qo'shimcha oqim o'tkazib bo'lmaydi.

Ford-Fulkerson algoritmi kodi

package main

import (
	"fmt"
	"math"
)

type Graph struct {
	graph [][]int
	ROW   int
}

func NewGraph(g [][]int) *Graph {
	r := len(g)
	cp := make([][]int, r)
	for i := range g {
		cp[i] = make([]int, len(g[i]))
		copy(cp[i], g[i])
	}
	return &Graph{graph: cp, ROW: r}
}

// Qidiruv algoritmi sifatida BFS dan foydalanish
func (g *Graph) BFS(s, t int, parent []int) bool {
	visited := make([]bool, g.ROW)
	queue := []int{s}
	visited[s] = true

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for ind, val := range g.graph[u] {
			if !visited[ind] && val > 0 {
				queue = append(queue, ind)
				visited[ind] = true
				parent[ind] = u
			}
		}
	}

	return visited[t]
}

// Ford-Fulkerson algoritmini qo'llash
func (g *Graph) FordFulkerson(source, sink int) int {
	parent := make([]int, g.ROW)
	maxFlow := 0

	for g.BFS(source, sink, parent) {
		pathFlow := math.MaxInt32
		s := sink
		for s != source {
			if g.graph[parent[s]][s] < pathFlow {
				pathFlow = g.graph[parent[s]][s]
			}
			s = parent[s]
		}

		// Yo'l oqimini qo'shish
		maxFlow += pathFlow

		// Qirralarning qoldiq (residual) sig'imlarini yangilash
		v := sink
		for v != source {
			u := parent[v]
			g.graph[u][v] -= pathFlow
			g.graph[v][u] += pathFlow
			v = parent[v]
		}
	}

	return maxFlow
}

func main() {
	graph := [][]int{
		{0, 8, 0, 0, 3, 0},
		{0, 0, 9, 0, 0, 0},
		{0, 0, 0, 0, 7, 2},
		{0, 0, 0, 0, 0, 5},
		{0, 0, 7, 4, 0, 0},
		{0, 0, 0, 0, 0, 0},
	}

	g := NewGraph(graph)
	source := 0
	sink := 5

	fmt.Printf("Max Flow: %d\n", g.FordFulkerson(source, sink))
}

Ford-Fulkerson murakkabligi

• Vaqt murakkabligi (Time Complexity): O(E * f), bu yerda E — qirralar soni, f esa tarmoqdagi maksimal oqim qiymati. Agar kengaytiruvchi yo'llarni topish uchun BFS algoritmi (Edmonds-Karp usuli) qo'llanilsa, vaqt murakkabligi O(V * E^2) ga teng bo'ladi va oqim qiymatiga bog'liq bo'lmaydi.
• Xotira murakkabligi (Space Complexity): O(V) yoki O(V^2) (grafni ifodalash uchun adjacency matrix qo'llanilganda).

Ford-Fulkerson algoritmining qo'llanilishi

• Suv taqsimlash quvurlari tarmog'i: Quvurlar tizimida suv ta'minotining maksimal o'tkazuvchanligini hisoblash.
• Bipartite matching masalasi: Ikki qismli graflarda maksimal mosliklarni topish (masalan, xodimlarga vakansiyalarni eng samarali taqsimlash).
• Talablarga mos aylanma oqimlar: Transport, logistika va yuk yetkazib berish marshrutlarida tarmoq oqimlarini optimallashtirish.