Хамгийн их урсгал - Форд-Фалкерсон ба Эдмондс-Карп¶

Эдмондс-Карпын алгоритм нь урсгалын сүлжээн дэх хамгийн их урсгалыг тооцоолох Форд-Фалкерсоны аргын хэрэгжүүлэлт юм.

Урсгалын сүлжээ¶

Эхлээд урсгалын сүлжээ, урсгал ба хамгийн их урсгал гэж юу болохыг тодорхойлъё.

Сүлжээ гэдэг нь орой $V$ ба ирмэг $E$-тэй чиглэлтэй граф $G$-г ирмэг $e \in E$ бүрд сөрөг биш бүхэл тоон утга буюу $e$-ийн багтаамж-ийг оноодог функц $c$-тэй хослуулсан зүйл юм. Хэрэв бид нэмж хоёр оройг нэгийг нь эх, нөгөөг нь цорго гэж шошголбол ийм сүлжээг урсгалын сүлжээ гэж нэрлэнэ.

Урсгалын сүлжээн дэх урсгал гэдэг нь ирмэг $e$ бүрд дахин сөрөг биш бүхэл тоон утга буюу урсгалыг оноодог функц $f$ юм. Функц дараах хоёр нөхцөлийг хангах ёстой:

Ирмэгийн урсгал багтаамжаас хэтрэх боломжгүй.

$$f(e) \le c(e)$$

Мөн эх ба цорго оройноос бусад тохиолдолд орой $u$-д орж буй урсгалын нийлбэр $u$-ээс гарч буй урсгалын нийлбэртэй тэнцүү байх ёстой.

$$\sum_{(v, u) \in E} f((v, u)) = \sum_{(u, v) \in E} f((u, v))$$

Эх орой $s$ зөвхөн гарах урсгалтай, цорго орой $t$ зөвхөн орох урсгалтай.

Дараах тэнцэтгэл биелэхийг харахад амархан:

$$\sum_{(s, u) \in E} f((s, u)) = \sum_{(u, t) \in E} f((u, t))$$

Урсгалын сүлжээний сайн аналоги нь дараах дүрслэл юм: Бид ирмэгүүдийг усны хоолой гэж илэрхийлэх ба ирмэгийн багтаамж нь хоолойгоор секундэд урсаж чадах усны хамгийн их хэмжээ, ирмэгийн урсгал нь одоогоор хоолойгоор секундэд урсаж буй усны хэмжээ юм. Энэ нь эхний урсгалын нөхцөлийг үндэслэнэ. Хоолойгоор түүний багтаамжаас илүү их ус урсаж чадахгүй. Оройнууд нь уулзвар болж ажиллах ба зарим хоолойноос ус гарч ирэх ба дараа нь эдгээр орой усыг бусад хоолой руу ямар нэг байдлаар тараана. Энэ нь мөн хоёр дахь урсгалын нөхцөлийг үндэслэнэ. Орж ирсэн бүх усыг уулзвар бүрд бусад хоолой руу тараах ёстой. Энэ нь ид шидээр алга болох буюу гарч ирэх боломжгүй. Эх $s$ нь бүх усны эх үүсвэр бөгөөс ус зөвхөн цорго $t$-д зайлж чадна.

Дараах зураг урсгалын сүлжээг харуулж байна. Ирмэг бүрийн эхний утга нь эхэндээ 0 байх урсгалыг, хоёр дахь утга нь багтаамжийг илэрхийлнэ.

Сүлжээний урсгалын утга гэдэг нь эх $s$-д үүсэх бүх урсгалын нийлбэр, эсвэл түүнтэй эквивалентээр цорго $t$-ээр зарцуулагдах бүх урсгалын нийлбэр юм. Хамгийн их урсгал гэдэг нь боломжит хамгийн их утгатай урсгал юм. Урсгалын сүлжээний энэ хамгийн их урсгалыг олох нь бидний бодохыг хүсэж буй бодлого юм.

Усны хоолойтой дүрслэлд бодлогыг дараах байдлаар томьёолж болно: бид эхээс цорго руу хоолойгоор хэр их ус түлхэж чадах вэ?

Дараах зураг урсгалын сүлжээн дэх хамгийн их урсгалыг харуулж байна.

Форд-Фалкерсоны арга¶

Бас нэг зүйлийг тодорхойлъё. Чиглэлтэй ирмэгийн үлдэгдэл багтаамж гэдэг нь багтаамжаас урсгалыг хассан утга юм. Хэрэв ямар нэг чиглэлтэй ирмэг $(u, v)$-ийн дагуу урсгал байвал урвуу ирмэг 0 багтаамжтай байх ба бид түүний урсгалыг $f((v, u)) = -f((u, v))$ гэж тодорхойлж болохыг тэмдэглэх нь зүйтэй. Энэ нь мөн бүх урвуу ирмэгийн үлдэгдэл багтаамжийг тодорхойлно. Бид эдгээр бүх ирмэгээс үлдэгдэл сүлжээ үүсгэж болох ба энэ нь ижил орой, ирмэгтэй сүлжээ боловч бид багтаамж болгон үлдэгдэл багтаамжийг ашиглана.

Форд-Фалкерсоны арга дараах байдлаар ажиллана. Эхлээд бид ирмэг бүрийн урсгалыг тэг болгож тохируулна. Дараа нь бид $s$-ээс $t$ хүрэх нэмэгдүүлэх зам хайна. Нэмэгдүүлэх зам гэдэг нь тэр замын дагуух бүх ирмэгийн үлдэгдэл багтаамж эерэг байх үлдэгдэл граф дахь энгийн зам юм. Хэрэв ийм зам олдвол бид эдгээр ирмэгийн дагуу урсгалыг нэмэгдүүлж чадна. Бид нэмэгдүүлэх зам хайж, урсгалыг нэмэгдүүлсээр байна. Нэмэгдүүлэх зам байхаа больмогц урсгал хамгийн их болно.

Нэмэгдүүлэх замын дагуу урсгалыг нэмэгдүүлэх гэдэг нь юу гэсэн үг болохыг илүү дэлгэрэнгүй тодорхойлъё. $C$ нь зам дахь ирмэгүүдийн хамгийн бага үлдэгдэл багтаамж байг. Тэгвэл бид урсгалыг дараах байдлаар нэмэгдүүлнэ: бид зам дахь ирмэг $(u, v)$ бүрийн хувьд $f((u, v)) ~\text{+=}~ C$ ба $f((v, u)) ~\text{-=}~ C$ гэж шинэчилнэ.

Аргыг үзүүлэх жишээ энд байна. Бид дээрхтэй ижил урсгалын сүлжээг ашиглана. Эхэндээ бид 0 урсгалаас эхэлнэ.

Бид үлдэгдэл багтаамж нь 7, 5, 8 байх зам $s - A - B - t$-г олж чадна. Тэдгээрийн минимум нь 5 тул бид энэ замын дагуу урсгалыг 5-аар нэмэгдүүлж чадна. Энэ нь сүлжээнд 5 урсгал өгнө.

Бид дахин нэмэгдүүлэх зам хайх ба энэ удаад үлдэгдэл багтаамж нь 4, 3, 3, 5 байх $s - D - A - C - t$-г олно. Тиймээс бид урсгалыг 3-аар нэмэгдүүлж чадах ба сүлжээнд 8 урсгал авна.

Энэ удаад бид үлдэгдэл багтаамж нь 1, 2, 3, 3 байх зам $s - D - C - B - t$-г олох ба тиймээс урсгалыг 1-ээр нэмэгдүүлнэ.

Энэ удаад бид үлдэгдэл багтаамж нь 2, 3, 1, 2 байх нэмэгдүүлэх зам $s - A - D - C - t$-г олно. Бид урсгалыг 1-ээр нэмэгдүүлж чадна. Гэвч энэ зам маш сонирхолтой. Энэ нь урвуу ирмэг $(A, D)$-г агуулна. Анхны урсгалын сүлжээнд бидэнд $A$-ээс $D$ рүү ямар ч урсгал илгээхийг зөвшөөрөөгүй. Гэвч бид $D$-ээс $A$ рүү аль хэдийн 3 урсгалтай тул энэ нь боломжтой. Үүний зөн совин нь дараах юм: $D$-ээс $A$ рүү 3 урсгал илгээхийн оронд бид зөвхөн 2 илгээж, үүнийг $s$-ээс $A$ рүү нэмэлт 1 урсгал илгээх замаар нөхөх ба энэ нь бидэнд $D - C - t$ замын дагуу нэмэлт 1 урсгал илгээх боломж олгоно.

Одоо $s$ ба $t$-ийн хооронд нэмэгдүүлэх зам олох боломжгүй тул энэ $10$ урсгал нь боломжит хамгийн их юм. Бид хамгийн их урсгалыг оллоо.

Форд-Фалкерсоны арга нэмэгдүүлэх замыг олох аргыг заадаггүйг тэмдэглэх нь зүйтэй. Боломжит хандлагууд бол хоёулаа $O(E)$-д ажилладаг DFS эсвэл BFS ашиглах явдал юм. Хэрэв сүлжээний бүх багтаамж бүхэл тоо бол нэмэгдүүлэх зам бүрийн хувьд сүлжээний урсгал дор хаяж 1-ээр нэмэгдэнэ (дэлгэрэнгүйг Бүхэл урсгалын теорем-оос үз). Тиймээс Форд-Фалкерсоны complexity нь $O(E F)$ бөгөөд энд $F$ нь сүлжээний хамгийн их урсгал юм. Рационал багтаамжийн тохиолдолд алгоритм мөн дуусах боловч complexity хязгаарлагдмал биш. Иррационал багтаамжийн тохиолдолд алгоритм хэзээ ч дуусахгүй байж болох ба хамгийн их урсгал руу нийлэхгүй ч байж болно.

Эдмондс-Карпын алгоритм¶

Эдмондс-Карпын алгоритм бол нэмэгдүүлэх зам олоход BFS ашигладаг Форд-Фалкерсоны аргын хэрэгжүүлэлт юм. Алгоритмыг анх Ефим Диниц 1970 онд нийтэлсэн бөгөөд дараа нь Жак Эдмондс ба Ричард Карп нар 1972 онд бие даан нийтэлсэн.

Complexity-г хамгийн их урсгалаас хамааралгүйгээр өгч болно. Алгоритм иррационал багтаамжийн хувьд ч $O(V E^2)$ хугацаанд ажиллана. Зөн совин нь бид нэмэгдүүлэх зам олох бүрд ирмэгүүдийн нэг нь ханах ба хэрэв тэр ирмэг дараа нь нэмэгдүүлэх замд дахин гарч ирвэл түүнээс $s$ хүрэх зай илүү урт байна гэсэн явдал юм. Энгийн замуудын урт $V$-ээр хязгаарлагдана.

Implementation¶

The matrix capacity stores the capacity for every pair of vertices. adj is the adjacency list of the undirected graph, since we also have to use the reversed of directed edges when we are looking for augmenting paths.

The function maxflow will return the value of the maximal flow. During the algorithm, the matrix capacity will actually store the residual capacity of the network. The value of the flow in each edge will actually not be stored, but it is easy to extend the implementation - by using an additional matrix - to also store the flow and return it.

int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;

int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(n);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}

Бүхэл урсгалын теорем¶

Теорем нь сүлжээн дэх багтаамж бүр бүхэл тоо бол хамгийн их урсгалын хэмжээ бүхэл тоо байх ба ирмэг бүрийн урсгал нь мөн бүхэл тоо байх хамгийн их урсгал оршин байна гэж өгүүлдэг. Тухайлбал Форд-Фалкерсоны арга ийм урсгалыг олдог.

Хамгийн их урсгал - хамгийн бага огтлолын теорем¶

$s$-$t$-огтлол гэдэг нь урсгалын сүлжээний оройнуудыг нэг олонлог нь эх $s$-г, нөгөө нь цорго $t$-г агуулахаар хоёр олонлогт хуваах хуваалт юм. $s$-$t$-огтлолын багтаамжийг эхийн талаас цоргын тал руу чиглэсэн ирмэгүүдийн багтаамжийн нийлбэр гэж тодорхойлно.

Бид $s$-ээс $t$ рүү дурын $s$-$t$-огтлолын багтаамжаас илүү их урсгал илгээж чадахгүй нь илэрхий. Тиймээс хамгийн их урсгал нь хамгийн бага огтлолын багтаамжаар хязгаарлагдана.

Хамгийн их урсгал - хамгийн бага огтлолын теорем бүр цааш явна. Энэ нь хамгийн их урсгалын багтаамж хамгийн бага огтлолын багтаамжтай тэнцүү байх ёстой гэж өгүүлнэ.

Дараах зурагт бидний өмнө ашигласан урсгалын сүлжээний хамгийн бага огтлолыг харж болно. Энэ нь $\{s, A, D\}$ ба $\{B, C, t\}$ огтлолын багтаамж $5 + 3 + 2 = 10$ болохыг харуулах ба энэ нь бидний олсон хамгийн их урсгалтай тэнцүү. Бусад огтлол илүү их багтаамжтай байна, жишээ нь $\{s, A\}$ ба $\{B, C, D, t\}$-ийн хоорондох багтаамж $4 + 3 + 5 = 12$ юм.

Форд-Фалкерсоны арга ашиглан хамгийн их урсгалын тооцооллыг гүйцэтгэсний дараа хамгийн бага огтлолыг олж болно. Боломжит нэг хамгийн бага огтлол нь дараах юм: үлдэгдэл графт $s$-ээс хүрч болох (эерэг үлдэгдэл багтаамжтай ирмэг ашиглан) бүх оройн олонлог, мөн бусад бүх оройн олонлог. Энэ хуваалтыг $s$-ээс эхлэх DFS ашиглан амархан олж болно.