Хамгийн бага огтлол - Штөр-Вагнерийн алгоритм¶
Бодлогын томьёолол¶
Бидэнд $n$ орой, $m$ ирмэгтэй чиглэлгүй жинтэй граф $G$ өгөгдсөн. Огтлол $C$ гэдэг нь оройнуудын хоосон биш жинхэнэ дэд олонлог юм (үнэн хэрэгтээ огтлол гэдэг нь оройнуудыг хоосон биш хоёр олонлогт хуваах хуваалт юм: $C$-д харьяалагдах оройнууд ба бусад бүгд). Огтлолын жин гэдэг нь огтлолыг гаталж буй ирмэгүүдийн, өөрөөр хэлбэл яг нэг үзүүрийн цэг нь $C$-д байх ирмэгүүдийн жингийн нийлбэр юм:
энд $E$ нь граф $G$-ийн бүх ирмэгийн олонлогийг тэмдэглэх ба $c(v,u)$ нь ирмэг $(v,u)$-ийн жин юм.
Даалгавар бол хамгийн бага жинтэй огтлолыг олох явдал.
Заримдаа энэ бодлогыг "глобал хамгийн бага огтлол" гэж нэрлэдэг — эх орой ба цорго орой өгөгдсөн байх ба бид цоргыг агуулсан боловч эхийг агуулаагүй хамгийн бага огтлол $C$-г олох ёстой байдаг бодлогоос ялгаатай нь. Глобал хамгийн бага огтлол нь боломжит бүх эх-цоргын хосын хамгийн бага өртөгтэй огтлолуудын дундах хамгийн багатай тэнцүү.
Хэдийгээр энэ бодлогыг хамгийн их урсгалын алгоритмаар (эх ба цоргын боломжит бүх хосын хувьд түүнийг $O(n^2)$ удаа ажиллуулснаар) бодож болох ч доор бид Мехтхильд Штөр ба Франк Вагнер нарын 1994 онд санал болгосон илүү энгийн бөгөөд хурдан алгоритмыг тайлбарлана.
Ерөнхийдөө гогцоо ба олон ирмэг зөвшөөрөгдөнө, хэдийгээр гогцоо үр дүнд ямар ч байдлаар нөлөөлөхгүй нь илэрхий бөгөөд олон ирмэгийг үргэлж тэдгээрийн нийлбэр жинтэй ганц ирмэгээр солиж болно. Тиймээс энгийн байдлын үүднээс бид оролтын граф гогцоо ба олон ирмэг агуулаагүй гэж үзнэ.
Алгоритмын тайлбар¶
Алгоритмын үндсэн санаа маш энгийн. Бид дараах процессыг давтан давтана: ямар нэг оройн хос $s$ ба $t$-ийн хоорондох хамгийн бага огтлолыг олоод, дараа нь эдгээр хоёр оройг нэг болгон нэгтгэнэ (тэдгээрийн зэргэлдээгийн жагсаалтыг холбож). Эцэст нь $n-1$ итерацын дараа граф ганц орой болж шахагдах ба процесс зогсоно. Үүний дараа хариу нь олдсон бүх $n-1$ огтлолын дундах хамгийн бага нь байна. Үнэндээ $i$ дахь үе шат бүрд орой $s_i$ ба $t_i$-ийн хооронд олдсон хамгийн бага огтлол $C_i$ нь эсвэл хайж буй глобал хамгийн бага огтлол болж таарна, эсвэл эсрэгээрээ $s_i$ ба $t_i$-г өөр өөр олонлогт оруулах нь ашиггүй тул эдгээр хоёр оройг нэг болгон нэгтгэснээр бид юуг ч муутгахгүй.
Ингэснээр бид бодлогыг дараах бодлого болгон бууруулсан: өгөгдсөн графын хувьд ямар нэг дурын оройн хос $s$ ба $t$-ийн хоорондох хамгийн бага огтлолыг ол. Энэ бодлогыг бодохын тулд мөн давталттай дараах процессыг санал болгосон. Бид эхэндээ ганц дурын орой агуулах оройнуудын олонлог $A$-г танилцуулна. Алхам бүрд бид олонлог $A$-тай хамгийн хүчтэй холбогдсон оройг, өөрөөр хэлбэл дараах хэмжигдэхүүн нь хамгийн их байх орой $v \not\in A$-г олно:
(өөрөөр хэлбэл нэг үзүүрийн цэг нь $v$-д, нөгөө нь $A$-д байх ирмэгүүдийн жингийн нийлбэр хамгийн их байна).
Дахин хэлэхэд энэ процесс бүх орой олонлог $A$ руу шилжсэн үед $n-1$ итерацын дараа дуусна (дашрамд хэлэхэд энэ процесс Примийн алгоритм-тай маш төстэй). Тэгвэл Штөр-Вагнерийн теорем-ын өгүүлж буйгаар хэрэв бид $A$-д хамгийн сүүлд нэмэгдсэн хоёр оройг $s$ ба $t$ гэж тэмдэглэвэл орой $s$ ба $t$-ийн хоорондох хамгийн бага огтлол ганц орой буюу $t$-ээс тогтоно. Энэ теоремын баталгааг дараагийн хэсэгт өгнө (ихэвчлэн тохиолддогчлон энэ нь өөрөө алгоритмыг ойлгоход ямар ч байдлаар нэмэр болохгүй).
Ингэснээр Штөр-Вагнерийн алгоритмын ерөнхий схем дараах байдалтай байна. Алгоритм $n-1$ фазаас тогтоно. Фаз бүрд олонлог $A$-г эхэндээ ямар нэг орой агуулахаар тохируулж, оройнуудын эхлэлийн жин $w(v,A)$-г тооцоолно. Дараа нь $n-1$ итерац явагдах ба тэдгээрийн тус бүрд $w(v,A)$ хамгийн их утгатай орой $u$-г сонгож олонлог $A$-д нэмнэ, үүний дараа үлдсэн оройнуудын $w$ утгыг дахин тооцоолно (үүний тулд илэрхий байдлаар бид сонгосон орой $u$-ийн зэргэлдээгийн жагсаалт дахь бүх ирмэгийг дайрч өнгөрөх ёстой). Бүх итерацыг гүйцэтгэсний дараа бид хамгийн сүүлд нэмэгдсэн хоёр оройг $s$ ба $t$-д тэмдэглэн авах ба $w(t,A \setminus t)$ утгыг $s$ ба $t$-ийн хооронд олдсон хамгийн бага огтлолын өртөг гэж авч болно. Дараа нь бид олдсон хамгийн бага огтлолыг одоогийн хариутай харьцуулж, хэрэв бага бол хариуг шинэчилж, дараагийн фаз руу шилжинэ.
Хэрэв бид ямар ч нарийн төвөгтэй өгөгдлийн бүтэц ашиглахгүй бол хамгийн чухал хэсэг нь $w$ хамгийн их утгатай оройг олох явдал юм. Хэрэв бид үүнийг $O(n)$-д хийвэл, тус бүр $n-1$ итерацтай $n-1$ фаз байгааг харгалзвал үүссэн алгоритмын complexity нь $O(n^3)$ болно.
Хэрэв бид $w$ хамгийн их утгатай оройг олохын тулд Фибоначчийн овоолго ашиглавал (энэ нь түлхүүрийн утгыг $O(1)$ хорогдуулсан хугацаанд ихэсгэх, максимумыг $O(\log n)$ хорогдуулсан хугацаанд гаргаж авах боломж олгодог) нэг фаз дахь олонлог $A$-тай холбоотой бүх үйлдлийг $O(m + n \log n)$-д гүйцэтгэнэ. Энэ тохиолдолд алгоритмын үүссэн complexity нь $O(n m + n^2 \log n)$ юм.
Штөр-Вагнерийн теоремын баталгаа¶
Энэ теоремын мэдэгдлийг эргэн сануулъя. Хэрэв бид бүх оройг олонлог $A$-д нэг нэгээр нь, тухай бүр энэ олонлогтой хамгийн хүчтэй холбогдсон оройг нэмэх байдлаар нэмбэл, сүүлээсээ хоёр дахь нэмэгдсэн оройг $s$, хамгийн сүүлийнхийг $t$ гэж тэмдэглэе. Тэгвэл хамгийн бага $s$-$t$ огтлол ганц орой буюу $t$-ээс тогтоно.
Үүнийг батлахын тулд дурын $s$-$t$ огтлол $C$-г авч үзээд, түүний жин ганц орой $t$-ээс тогтох огтлолын жингээс бага байж чадахгүйг харуулъя:
Үүний тулд бид дараах баримтыг батална. $A_v$ нь орой $v$-г нэмэхийн өмнөхөн олонлог $A$-ийн төлөв байг. $C_v$ нь огтлол $C$-ээр үүсгэгдсэн олонлог $A_v \cup \{v\}$-ийн огтлол байг (энгийнээр хэлбэл $C_v$ нь эдгээр хоёр оройн олонлогийн огтлолцолтой тэнцүү). Цаашилбал орой $v$ ба түүнээс өмнө нэмэгдсэн орой нь огтлол $C$-ийн өөр өөр хэсэгт харьяалагдаж байвал орой $v$-г (огтлол $C$-ийн хувьд) идэвхтэй гэж нэрлэнэ. Тэгвэл дурын идэвхтэй орой $v$-ийн хувьд дараах тэнцэтгэл биш биелнэ гэж бид батлан хэлнэ:
Тухайлбал $t$ нь идэвхтэй орой юм (учир нь түүний өмнө нэмэгдсэн орой нь $s$ байсан), мөн $v = t$-ийн хувьд энэ тэнцэтгэл биш теоремын мэдэгдэл болж хувирна:
Тэгэхээр бид энэ тэнцэтгэл бишийг математик индукц ашиглан батална.
Эхний идэвхтэй орой $v$-ийн хувьд тэнцэтгэл биш биелнэ (түүнээс ч илүү энэ нь тэнцэтгэл болж хувирна) — учир нь $A_v$-ийн бүх орой огтлолын нэг хэсэгт, $v$ нөгөө хэсэгт харьяалагдана.
Одоо энэ тэнцэтгэл биш ямар нэг орой $v$ хүртэлх бүх идэвхтэй оройн хувьд биелнэ гэж үзье; дараагийн идэвхтэй орой $u$-ийн хувьд үүнийг батлая. Үүний тулд зүүн талыг хувиргая:
Эхлээд дараахыг анзаар:
энэ нь олонлог $A$ нь $A_v$-тэй тэнцүү байх үед түүнд нэмэгдсэн орой яг $v$ байсан бөгөөд $u$ биш байсан, өөрөөр хэлбэл түүнд $w$-ийн хамгийн их утга байсан гэдэг баримтаас мөрдөнө.
Цаашилбал индукцийн таамаглалаар $w(v,A_v) \le w(C_v)$ тул бид дараахыг олж авна:
эндээс бид дараахыг авна:
Одоо орой $u$ ба $A_u \setminus A_v$-ийн бүх орой огтлол $C$-ийн өөр өөр хэсэгт байгааг анзаар, тиймээс $w(u,A_u \setminus A_v)$ хэмжигдэхүүн нь $w(C_u)$-д тоологдох боловч $w(C_v)$-д хараахан тоологдоогүй байсан ирмэгүүдийн жингийн нийлбэрийг тэмдэглэнэ, эндээс бид дараахыг авна:
шаардлагатай ёсоор.
Бид $w(v,A_v) \le w(C_v)$ хамаарлыг баталсан бөгөөд дээр дурдсанчлан үүнээс бүхэл теорем мөрдөнө.
Implementation¶
For the simplest and clearest implementation (with $O(n^3)$ complexity), the graph is represented as an adjacency matrix. The answer is stored in the variables best_cost and best_cut (the cost of the minimum cut and the vertices contained in it).
For every vertex, the array exist stores whether it still exists, or whether it has been merged with some other vertex. The list v[i] for every compressed vertex $i$ stores the numbers of the original vertices that were compressed into this vertex $i$.
The algorithm consists of $n-1$ phases (the loop over the variable ph). In every phase, all vertices are initially outside the set $A$, so the array in_a is filled with zeros, and the connectivities $w$ of all vertices are zero. In each of the $n-\mathrm{ph}$ iterations, the vertex sel with the largest value of $w$ is found. If this is the last iteration, the answer is updated if necessary, and the second-to-last prev and the last sel selected vertices are merged into one. If the iteration is not the last one, then sel is added to the set $A$, after which the weights of all the remaining vertices are recalculated.
Note that the algorithm "spoils" the graph g during its work, so if you still need it later, you have to save a copy of it before calling the function.
const int MAXN = 500;
int n;
long long g[MAXN][MAXN];
long long best_cost = (1LL << 62);
vector<int> best_cut;
void mincut() {
vector<int> v[MAXN];
for (int i = 0; i < n; ++i)
v[i].assign(1, i);
long long w[MAXN];
bool exist[MAXN], in_a[MAXN];
memset(exist, true, sizeof exist);
for (int ph = 0; ph < n - 1; ++ph) {
memset(in_a, false, sizeof in_a);
memset(w, 0, sizeof w);
for (int it = 0, prev; it < n - ph; ++it) {
int sel = -1;
for (int i = 0; i < n; ++i)
if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel]))
sel = i;
if (it == n - ph - 1) {
if (w[sel] < best_cost) {
best_cost = w[sel];
best_cut = v[sel];
}
v[prev].insert(v[prev].end(), v[sel].begin(), v[sel].end());
for (int i = 0; i < n; ++i)
g[prev][i] = g[i][prev] += g[sel][i];
exist[sel] = false;
} else {
in_a[sel] = true;
for (int i = 0; i < n; ++i)
w[i] += g[sel][i];
prev = sel;
}
}
}
}