Az Edmonds-algoritmus (más néven Edmonds-féle maximális párosítás algoritmus) egy hatékony módszer, amely általános gráfokban meghatározza a maximális párosítást. Az algoritmus működik irányítatlan gráfokon, és különösen hasznos, ha az élek tartalmazhatnak páratlan köröket (ún. “blossom” - virág alakzatokat).
Egy irányítatlan gráfban a párosítás olyan élek halmaza, amelyek között nincs közös csúcs. A maximális párosítás a legtöbb élt tartalmazó ilyen halmaz.
EdmondsMaximumMatching(G):
P = üres párosítás
amíg található alapút:
ha találunk augmentáló utat:
növeljük meg a párosítást
ha találunk blossomt:
húzzuk össze és folytassuk az algoritmust
visszatér P
Ez a kód egy általános megközelítést alkalmaz Edmonds-algoritmushoz, de egyszerűsített formában mutatja be az augmentációs lépéseket.
from collections import deque
def find_augmenting_path(graph, match, dist):
for u in graph:
dist = -1
queue = deque()
for u in graph:
if match is None:
dist = 0
queue.append(u)
while queue:
u = queue.popleft()
for v in graph:
matched_to = match
if matched_to is None:
return True
if dist == -1:
dist = dist + 1
queue.append(matched_to)
return False
def dfs(graph, u, match, dist):
for v in graph:
matched_to = match
if matched_to is None or (dist == dist + 1 and dfs(graph, matched_to, match, dist)):
match = v
match = u
return True
dist = -1
return False
def edmonds_maximum_matching(graph):
match = {u: None for u in graph}
dist = {}
matching_size = 0
while find_augmenting_path(graph, match, dist):
for u in graph:
if match is None and dfs(graph, u, match, dist):
matching_size += 1
return matching_size, match
# Példa gráf
graph = {
0: ,
1: ,
2: ,
3:
}
matching_size, match = edmonds_maximum_matching(graph)
print("Maximális párosítás mérete:", matching_size)
print("Párosítás:", match)
Az alábbi kód egy egyszerűbb formában valósítja meg az Edmonds-algoritmust.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 1e9;
bool bfs(const vector<vector<int>>& graph, vector<int>& match, vector<int>& dist) {
queue<int> q;
int n = graph.size();
for (int i = 0; i < n; i++) {
if (match == -1) {
dist = 0;
q.push(i);
} else {
dist = INF;
}
}
bool found_augmenting_path = false;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph) {
int matched_to = match;
if (matched_to == -1) {
found_augmenting_path = true;
} else if (dist == INF) {
dist = dist + 1;
q.push(matched_to);
}
}
}
return found_augmenting_path;
}
bool dfs(int u, const vector<vector<int>>& graph, vector<int>& match, vector<int>& dist) {
for (int v : graph) {
int matched_to = match;
if (matched_to == -1 || (dist == dist + 1 && dfs(matched_to, graph, match, dist))) {
match = v;
match = u;
return true;
}
}
dist = INF;
return false;
}
int edmonds_maximum_matching(const vector<vector<int>>& graph) {
int n = graph.size();
vector<int> match(n, -1), dist(n);
int matching_size = 0;
while (bfs(graph, match, dist)) {
for (int i = 0; i < n; i++) {
if (match == -1 && dfs(i, graph, match, dist)) {
matching_size++;
}
}
}
return matching_size;
}
int main() {
vector<vector<int>> graph = {
{1, 2}, {0, 3}, {0, 3}, {1, 2}
};
cout << "Maximális párosítás mérete: " << edmonds_maximum_matching(graph) << endl;
return 0;
}
Az Edmonds-algoritmus hatékonyan kezeli a párosítási problémát általános gráfokon, beleértve a páratlan köröket is. Bár az algoritmus bonyolultabb, mint más egyszerűbb módszerek (pl. Greedy algoritmus), garantáltan megtalálja a maximális párosítást, így fontos eszköz a hálózatkutatásban és kombinatorikai optimalizálási feladatokban.