Алгоритми Кун — ҷуфткунии максималӣ дар графи дудола
Алгоритми Кун — ҷуфткунии максималӣ дар графи дудола
Дода шудааст графи дудолаи бо доляҳо:
- чап: ,
- рост: ,
Алгоритми Кун — ҷуфткунии максималӣ дар графи дудола
Дода шудааст графи дудолаи бо доляҳо:
Лозим аст ёфтани паросочетании калонтарин — маҷмӯи максималии қирраҳо, ки қуллаҳои умумӣ надоранд.
Алгоритми Кун — татбиқи мустақими теоремаи Берже:
Паросочетание максималӣ ⇔ дар граф занҷирҳои афзоянда нестанд.
Алгоритм чунин кор мекунад:
Занҷири афзоянда — роҳе, ки:
Пас аз ивазкунии навбатии қирраҳо дар тӯли занҷир андозаи паросочетание ба 1 зиёд мешавад.
Барои қуллаи аз доляи чап:
Яъне:
→ -ро бо мепайвандем
Барои ҳамаи :
Ҳар DFS —
То маротиба оғоз мекунем:
Дар бадтарин ҳолат:
Муҳим:
int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<char> used;
bool try_kuhn(int v) {
if (used[v]) return false;
used[v] = true;
for (int to : g[v]) {
if (mt[to] == -1 || try_kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
int main() {
// чтение графа
mt.assign(k, -1);
for (int v = 0; v < n; v++) {
used.assign(n, false);
try_kuhn(v);
}
// вывод паросочетания
for (int i = 0; i < k; i++) {
if (mt[i] != -1) {
cout << mt[i] + 1 << " " << i + 1 << "\n";
}
}
}