DSA Ford-Fulkerson

Ford-Fulkerson algoritmi

Ford-Fulkerson algoritmi yo‘naltirilgan graf uchun maksimal oqim masalasini yechadi.

Oqim manba cho‘qqisidan (\(s\)) chiqadi va quyilish cho‘qqisiga (\(t\)) borib tushadi, grafdagi har bir qirra esa sig‘im bilan cheklangan oqimni o‘tkazadi.

Ford-Fulkerson algoritmi manbadan quyilishga qadar bo‘sh sig‘imga ega yo‘lni (u kengaytiruvchi yo‘l — augmented path deb ataladi) qidirib, so‘ngra shu yo‘l orqali imkon qadar ko‘p oqim yuborish orqali ishlaydi.

Ford-Fulkerson algoritmi maksimal oqimga erishilguncha ko‘proq oqim yuborish uchun yangi yo‘llarni topishda davom etadi.

Yuqoridagi simulyatsiyada Ford-Fulkerson algoritmi maksimal oqim masalasini yechadi: u \(s\) manba cho‘qqisidan \(t\) quyilish cho‘qqisiga qancha oqim yuborish mumkinligini aniqlaydi va bu maksimal oqim 8 ga teng.

Yuqoridagi simulyatsiyadagi sonlar kasr ko‘rinishida yozilgan: birinchi son — oqim, ikkinchi son esa sig‘im (shu qirradagi mumkin bo‘lgan maksimal oqim). Masalan, \(s \rightarrow v_2\) qirrasidagi 0/7 shu qirrada 0 oqim borligini va uning sig‘imi 7 ekanini bildiradi.

Quyida Ford-Fulkerson algoritmi qanday ishlashining asosiy qadamma-qadam tavsifini ko‘rishingiz mumkin, ammo uni chindan tushunish uchun keyinroq batafsilroq to‘xtalishimiz kerak bo‘ladi.

Ford-Fulkerson algoritmida qoldiq tarmoq

Aslida Ford-Fulkerson algoritmi qoldiq tarmoq (residual network) deb ataladigan tuzilmani yaratib, undan foydalanish orqali ishlaydi; u asl grafning o‘ziga xos tasviridir.

Qoldiq tarmoqda har bir qirra qoldiq sig‘imga (residual capacity) ega bo‘lib, u qirraning asl sig‘imidan shu qirradagi oqim ayirilganiga teng. Qoldiq sig‘imni ma’lum oqimga ega qirradagi qolgan bo‘sh sig‘im deb qarash mumkin.

Masalan, agar \( v_3 \rightarrow v_4 \) qirrasida oqim 2 ga, sig‘im esa 3 ga teng bo‘lsa, bu qirradagi qoldiq oqim 1 ga teng, chunki bu qirra orqali yana 1 birlik oqim yuborish uchun joy bor.

Ford-Fulkerson algoritmida teskari qirralar

Ford-Fulkerson algoritmi oqimni orqaga yuborish uchun teskari qirralar (reversed edges) deb ataladigan narsadan ham foydalanadi. Bu umumiy oqimni oshirish uchun foydali.

Masalan, yuqoridagi animatsiyadagi va quyida qo‘lda bajarib ko‘rishdagi oxirgi kengaytiruvchi yo‘l \(s \rightarrow v_2 \rightarrow v_4 \rightarrow v_3 \rightarrow t\) umumiy oqim aslida \( v_4 \rightarrow v_3 \) qirrasi bo‘ylab oqimni orqaga, ya’ni teskari yo‘nalishda yuborish orqali yana bir birlikka qanday oshirilishini ko‘rsatadi.

Misolimizda \( v_3 \rightarrow v_4 \) qirrasi bo‘ylab oqimni teskari yo‘nalishda orqaga yuborish \( v_3 \) cho‘qqisidan chiqayotgan shu 1 birlik oqim endi \( v_3 \) dan \( v_3 \rightarrow v_4 \) o‘rniga \( v_3 \rightarrow t \) qirrasi orqali chiqishini anglatadi.

Oqimni qirraga qarama-qarshi yo‘nalishda orqaga yuborish uchun tarmoqdagi har bir asl qirra uchun teskari qirra yaratiladi. Shundan so‘ng Ford-Fulkerson algoritmi oqimni teskari yo‘nalishda yuborish uchun bu teskari qirralardan foydalana oladi.

Teskari qirraning oqimi ham, sig‘imi ham yo‘q, faqat qoldiq sig‘imi bor. Teskari qirraning qoldiq sig‘imi har doim unga mos asl qirradagi oqimga teng. Misolimizda \( v_3 \rightarrow v_4 \) qirrasidagi oqim 2 ga teng, demak, unga mos teskari \( v_4 \rightarrow v_3 \) qirrasida qoldiq sig‘im 2 ga teng.

Bu shunchaki asl \( v_3 \rightarrow v_4 \) qirrasida 2 oqim bo‘lganda, xuddi shu miqdordagi oqimni shu qirra bo‘ylab, lekin teskari yo‘nalishda orqaga yuborish imkoniyati borligini bildiradi. Oqimni orqaga surish uchun teskari qirradan foydalanishni allaqachon hosil qilingan oqimning bir qismini bekor qilish deb ham qarash mumkin.

Qirralarda qoldiq sig‘imga ega qoldiq tarmoq g‘oyasi va teskari qirralar g‘oyasi Ford-Fulkerson algoritmi ishlashining markazida turadi; algoritmni ushbu sahifada quyiroqda amalga oshirganimizda bu haqda batafsilroq to‘xtalamiz.

Qo‘lda bajarib ko‘rish

Boshida grafda oqim yo‘q.

Maksimal oqimni topish uchun Ford-Fulkerson algoritmi oqimni oshirishi kerak, lekin avval oqimni qayerda oshirish mumkinligini aniqlashi lozim: u kengaytiruvchi yo‘lni topishi kerak.

Aslida Ford-Fulkerson algoritmida bunday kengaytiruvchi yo‘l qanday topilishi belgilanmagan (shuning uchun u ko‘pincha algoritm emas, balki metod sifatida tavsiflanadi), ammo bu darslikda Ford-Fulkerson algoritmi uchun kengaytiruvchi yo‘llarni topishda chuqurlik bo‘yicha qidiruv (DFS)dan foydalanamiz.

Ford-Fulkerson DFS yordamida topadigan birinchi kengaytiruvchi yo‘l — \(s \rightarrow v_1 \rightarrow v_3 \rightarrow v_4 \rightarrow t\).

Tor joyni hisoblash orqali Ford-Fulkerson kengaytiruvchi yo‘l orqali yuborish mumkin bo‘lgan eng katta oqim 3 ekanini aniqlaydi, shuning uchun bu yo‘ldagi barcha qirralarda oqim 3 ga oshiriladi.

Ford-Fulkerson algoritmining keyingi iteratsiyasi quyidagi qadamlarni yana bajarishdan iborat:

2. Yangi kengaytiruvchi yo‘lni toping
3. Shu yo‘ldagi oqimni qanchaga oshirish mumkinligini aniqlang
4. Shu yo‘ldagi qirralar bo‘ylab oqimni mos ravishda oshiring

Keyingi topilgan kengaytiruvchi yo‘l — \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow v_3 \rightarrow t\); u oqim orqaga yuboriladigan \(v_4 \rightarrow v_3\) teskari qirrasini o‘z ichiga oladi.

Ford-Fulkerson algoritmidagi teskari qirralar tushunchasi juda qo‘l keladi, chunki u algoritmning yo‘l topuvchi qismiga teskari qirralar ham kirishi mumkin bo‘lgan kengaytiruvchi yo‘lni topish imkonini beradi.

Ushbu muayyan holatda bu 2 oqimni \(v_3 \rightarrow v_4\) qirrasi bo‘ylab orqaga yuborib, uning o‘rniga \(v_3 \rightarrow t\) ga yo‘naltirish mumkinligini anglatadi.

Bu yo‘lda oqimni faqat 2 ga oshirish mumkin, chunki \( v_3 \rightarrow t \) qirrasining sig‘imi shunga teng.

Keyingi topilgan kengaytiruvchi yo‘l — \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\).

Bu yo‘lda oqimni 2 ga oshirish mumkin. Tor joy (cheklovchi qirra) — \( v_1 \rightarrow v_4 \), chunki bu qirrada yana atigi ikki birlik oqim yuborish uchun joy bor.

Keyingi va oxirgi kengaytiruvchi yo‘l — \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\).

Bu yo‘lda oqimni faqat 1 ga oshirish mumkin, chunki \( v_4 \rightarrow t \) qirrasi bu yo‘ldagi tor joy bo‘lib, unda yana atigi bir birlik oqim uchun joy bor (\(capacity-flow=1\)).

Bu bosqichda yangi kengaytiruvchi yo‘lni topib bo‘lmaydi (\(s\) dan \(t\) ga ko‘proq oqim yuborish mumkin bo‘lgan yo‘lni topishning iloji yo‘q), demak maksimal oqim topildi va Ford-Fulkerson algoritmi o‘z ishini tugatdi.

Maksimal oqim 8 ga teng. Yuqoridagi rasmda ko‘rib turganingizdek, \(s\) manba cho‘qqisidan chiqayotgan oqim (8) \(t\) quyilish cho‘qqisiga kirayotgan oqimga teng.

Shuningdek, \(s\) yoki \(t\) dan boshqa istalgan cho‘qqini olsangiz, cho‘qqiga kirayotgan oqim miqdori undan chiqayotgan oqimga teng ekanini ko‘rasiz. Buni biz oqimning saqlanishi (conservation of flow) deb ataymiz va bu barcha shunday oqim tarmoqlari (har bir qirrasi oqim va sig‘imga ega yo‘naltirilgan graflar) uchun bajarilishi shart.

Ford-Fulkerson algoritmini amalga oshirish

Ford-Fulkerson algoritmini amalga oshirish uchun Graph sinfini yaratamiz. Graph grafni uning cho‘qqilari va qirralari bilan birga ifodalaydi:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

3-qator: Barcha qirralar va qirra sig‘imlarini saqlash uchun adj_matrixni yaratamiz. Boshlang‘ich qiymatlar 0ga tenglanadi.

4-qator: size — grafdagi cho‘qqilar soni.

5-qator: vertex_data barcha cho‘qqilarning nomlarini saqlaydi.

7–8-qatorlar: add_edge metodi u cho‘qqisidan v cho‘qqisiga c sig‘imli qirra qo‘shish uchun ishlatiladi.

10–12-qatorlar: add_vertex_data metodi grafga cho‘qqi nomini qo‘shish uchun ishlatiladi. Cho‘qqining indeksi vertex argumenti orqali beriladi, data esa cho‘qqining nomi.

Graph sinfida chuqurlik bo‘yicha qidiruv (Depth-First-Search) yordamida kengaytiruvchi yo‘llarni topadigan dfs metodi ham bor:

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

        visited[s] = True
        path.append(s)

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

15–18-qatorlar: visited massivi kengaytiruvchi yo‘lni qidirish davomida bir xil cho‘qqilarga qayta tashrif buyurmaslikka yordam beradi. Kengaytiruvchi yo‘lga tegishli cho‘qqilar path massivida saqlanadi.

20–21-qatorlar: Joriy cho‘qqi tashrif buyurilgan deb belgilanadi, so‘ngra yo‘lga qo‘shiladi.

23–24-qatorlar: Agar joriy cho‘qqi quyilish tuguni bo‘lsa, demak manba cho‘qqisidan quyilish cho‘qqisigacha kengaytiruvchi yo‘l topildi va bu yo‘lni qaytarish mumkin.

26–30-qatorlar: Qo‘shnilik matritsasida joriy s cho‘qqisidan boshlanadigan barcha qirralar sikl orqali aylanib chiqiladi; ind qo‘shni tugunni, val esa shu cho‘qqiga boradigan qirradagi qoldiq sig‘imni ifodalaydi. Agar qo‘shni cho‘qqiga tashrif buyurilmagan bo‘lsa va unga boradigan qirrada qoldiq sig‘im bo‘lsa, shu tugunga o‘ting va yo‘lni o‘sha cho‘qqidan qidirishda davom eting.

32-qator: Agar yo‘l topilmasa, None qaytariladi.

fordFulkerson metodi Graph sinfiga qo‘shadigan oxirgi metodimiz:

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

Dastlab max_flow qiymati 0ga teng va while sikli oqimni oshirish mumkin bo‘lgan kengaytiruvchi yo‘l mavjud ekan, max_flowni oshirishda davom etadi.

37-qator: Kengaytiruvchi yo‘l topiladi.

39–42-qatorlar: Shu yo‘l orqali qancha oqim yuborish mumkinligini aniqlash uchun kengaytiruvchi yo‘ldagi har bir qirra tekshiriladi.

44–46-qatorlar: Oqim oshirilishi natijasida har bir to‘g‘ri qirraning qoldiq sig‘imi (sig‘im minus oqim) kamaytiriladi.

47-qator: Bu Ford-Fulkerson algoritmi asl to‘g‘ri qirralar bo‘ylab oqimni orqaga yuborish (bekor qilish) uchun foydalanadigan teskari qirrani ifodalaydi. Shuni tushunish muhimki, bu teskari qirralar asl grafda yo‘q — ular algoritm ishlashi uchun Ford-Fulkerson tomonidan kiritilgan soxta (fiktiv) qirralardir.

49-qator: Har safar kengaytiruvchi yo‘l bo‘ylab oqim oshirilganda, max_flow ham xuddi shu qiymatga oshiriladi.

51–52-qatorlar: Bu faqat algoritm keyingi iteratsiyani boshlashidan oldin kengaytiruvchi yo‘lni chop etish uchun.

Graph sinfini aniqlagach, muayyan grafni initsializatsiya qilish uchun cho‘qqilar va qirralarni aniqlash kerak. Ford-Fulkerson algoritmi misolining to‘liq kodi quyidagicha:

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def dfs(self, s, t, visited=None, path=None):
        if visited is None:
            visited = [False] * self.size
        if path is None:
            path = []

        visited[s] = True
        path.append(s)

        if s == t:
            return path

        for ind, val in enumerate(self.adj_matrix[s]):
            if not visited[ind] and val > 0:
                result_path = self.dfs(ind, t, visited, path.copy())
                if result_path:
                    return result_path

        return None

    def fordFulkerson(self, source, sink):
        max_flow = 0

        path = self.dfs(source, sink)
        while path:
            path_flow = float("Inf")
            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                path_flow = min(path_flow, self.adj_matrix[u][v])

            for i in range(len(path) - 1):
                u, v = path[i], path[i + 1]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow

            max_flow += path_flow

            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

            path = self.dfs(source, sink)

        return max_flow

g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5

print("The maximum possible flow is %d " % g.fordFulkerson(source, sink))

Ford-Fulkerson algoritmining vaqt murakkabligi

Ford-Fulkerson algoritmining vaqt murakkabligi cho‘qqilar soni \(V\) ga, qirralar soni \(E\) ga, shuningdek, grafdagi maksimal oqim \(f\) ga ham bog‘liq ravishda o‘zgaradi.

Vaqt murakkabligining grafdagi maksimal oqim \(f\) ga bog‘liq ravishda o‘zgarishining sababi shundaki, o‘tkazuvchanligi yuqori grafda oqimni oshiruvchi kengaytiruvchi yo‘llar ko‘proq bo‘ladi, bu esa shu kengaytiruvchi yo‘llarni topuvchi DFS metodi ko‘proq marta ishlashi kerakligini anglatadi.

Chuqurlik bo‘yicha qidiruvning (DFS) vaqt murakkabligi \(O(V+E)\).

DFS har bir yangi kengaytiruvchi yo‘l uchun bir marta ishlaydi. Agar har bir kengaytiruvchi graf oqimni 1 birlikka oshiradi deb faraz qilsak, DFS \(f\) marta, ya’ni maksimal oqim qiymaticha marta ishlashi kerak.

Bu DFS’dan foydalanadigan Ford-Fulkerson algoritmining vaqt murakkabligi quyidagiga teng ekanini anglatadi

\[ O( (V+E) \cdot f ) \]

Zich graflar (dense graphs) uchun, ya’ni \( E > V \) bo‘lganda, DFS’ning vaqt murakkabligini \(O(E)\) ga soddalashtirish mumkin, demak, Ford-Fulkerson algoritmining vaqt murakkabligini ham quyidagiga soddalashtirish mumkin

\[ O( E \cdot f ) \]

Zich grafning aniq ta’rifi yo‘q, lekin bu qirralari ko‘p bo‘lgan graf.

Biz tavsiflaydigan, maksimal oqimni topuvchi keyingi algoritm — Edmonds-Karp algoritmi.

Edmonds-Karp algoritmi Ford-Fulkerson algoritmiga juda o‘xshaydi, ammo kengaytiruvchi yo‘llarni topish uchun DFS o‘rniga BFS’dan foydalanadi, bu esa maksimal oqimni topish uchun kamroq iteratsiya talab qilinishiga olib keladi.