Wikiszótár

Edmonds-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈɛdmont͡ʃɒlɡoritmuʃ]

Főnév

Edmonds-algoritmus

  1. (matematika, gráfelmélet, algoritmusok) Az Edmonds-algoritmus a minimális feszítő fenyő megtalálására szolgál (ezt néha optimális elágazásnak nevezik). A feszítő fenyő olyan irányított fa, amelyben van egy speciális, gyökérnek nevezett pont, amelyből minden pontba vezet irányított út. Ez a minimális feszítőfa probléma irányított analógja.

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).


Probléma megfogalmazása

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.

Kulcsfogalmak:

  • Alap (augmentáló) út: Olyan út, amely a párosítatlan csúcsból indul, és alternáló módon halad párosított és párosítatlan élek mentén.
  • Blossom (virág): Egy párosítatlan csúcsokat tartalmazó páratlan kör, amelyet kezelni kell az algoritmus során.


Algoritmus alapelvei

  1. Indulás:
    • Kezdjük egy üres párosítással.
    • Használjunk BFS-t vagy DFS-t az alaputak keresésére.
  2. Blossom felismerése és összehúzása:
    • Ha egy páratlan kört (blossom) találunk, azt összehúzzuk egyetlen csúccsá, így az alapút könnyebben kezelhető.
  3. Augmentáló út meghosszabbítása:
    • Az alapúttal növeljük a párosítást, ha találunk ilyet.
  4. Ismétlés:
    • Addig folytatjuk az augmentáló utak keresését és használatát, amíg nem találunk többet.


Tulajdonságok

  • Időkomplexitás: (O(V^3)), ahol (V) a csúcsok száma.
  • Párosítás maximális méretének garantálása.


Pszeudokód

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

Python implementáció

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[u] = -1
    queue = deque()

    for u in graph:
        if match[u] is None:
            dist[u] = 0
            queue.append(u)

    while queue:
        u = queue.popleft()
        for v in graph[u]:
            matched_to = match[v]
            if matched_to is None:
                return True
            if dist[matched_to] == -1:
                dist[matched_to] = dist[u] + 1
                queue.append(matched_to)
    return False

def dfs(graph, u, match, dist):
    for v in graph[u]:
        matched_to = match[v]
        if matched_to is None or (dist[matched_to] == dist[u] + 1 and dfs(graph, matched_to, match, dist)):
            match[u] = v
            match[v] = u
            return True
    dist[u] = -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[u] is None and dfs(graph, u, match, dist):
                matching_size += 1

    return matching_size, match

# Példa gráf
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

matching_size, match = edmonds_maximum_matching(graph)
print("Maximális párosítás mérete:", matching_size)
print("Párosítás:", match)

C++ implementáció

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[i] == -1) {
            dist[i] = 0;
            q.push(i);
        } else {
            dist[i] = INF;
        }
    }

    bool found_augmenting_path = false;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : graph[u]) {
            int matched_to = match[v];
            if (matched_to == -1) {
                found_augmenting_path = true;
            } else if (dist[matched_to] == INF) {
                dist[matched_to] = dist[u] + 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[u]) {
        int matched_to = match[v];
        if (matched_to == -1 || (dist[matched_to] == dist[u] + 1 && dfs(matched_to, graph, match, dist))) {
            match[u] = v;
            match[v] = u;
            return true;
        }
    }

    dist[u] = 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[i] == -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;
}

Összegzés

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.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Edmonds-algoritmus&oldid=3479859”