Wikiszótár

Karger-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkɒrɡɛrɒlɡoritmuʃ]

Főnév

Karger-algoritmus

  1. (matematika, algoritmusok) A Karger-algoritmus egy valószínűségi algoritmus a minimális vágás (minimum cut) meghatározására egy gráfban. Az algoritmus ismételt élszűkítéssel dolgozik, míg a gráf két csúcshalmazra csökken. A két halmaz közötti élek száma adja meg a minimális vágás értékét.


Algoritmus menete

  1. Gráf beolvasása: A gráfot csúcsok és élek formájában reprezentáljuk.
  2. Véletlen élszűkítés:
    • Egy élt véletlenszerűen kiválasztunk, majd “összehúzzuk” az él által összekapcsolt két csúcsot.
    • Az összehúzott csúcs összes élét egyesítjük, miközben az önhurkokat eltávolítjuk.
  3. Ismétlés:
    • Addig ismételjük az élszűkítést, amíg a gráf két csúcsra csökken.
  4. Minimális vágás kiértékelése:
    • Az utolsó két csúcs között lévő élek száma adja a minimális vágást.
  5. Több futtatás:
    • Az algoritmus véletlenszerű természete miatt többször kell futtatni, hogy növeljük a sikeres eredmény esélyét.


Pszeudokód

function KargerMinCut(Graph G):
    while G has more than 2 vertices:
        randomly select an edge (u, v)
        merge vertices u and v into a single vertex
        remove self-loops
    return the number of edges between the remaining two vertices

Python Implementáció

import random
from copy import deepcopy

def karger_min_cut(graph):
    """
    Karger-algoritmus a minimális vágás meghatározására.
    
    Args:
        graph: A gráf szomszédsági listaként.
        
    Returns:
        A minimális vágás értéke.
    """
    # Mély másolat a gráf módosítása elkerülése érdekében
    graph = deepcopy(graph)
    
    while len(graph) > 2:
        # Véletlenszerű él kiválasztása
        u = random.choice(list(graph.keys()))
        v = random.choice(graph[u])
        
        # Csúcsok összevonása
        graph[u].extend(graph[v])
        for vertex in graph[v]:
            graph[vertex] = [u if x == v else x for x in graph[vertex]]
        
        # Önhurok eltávolítása
        graph[u] = [x for x in graph[u] if x != u]
        del graph[v]
    
    # A minimális vágás a megmaradt két csúcs közötti élek száma
    return len(next(iter(graph.values())))

# Példa gráf szomszédsági listában
graph = {
    1: [2, 3, 4],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [1, 2, 3]
}

# Több futtatás a legjobb eredményért
min_cut = float('inf')
for _ in range(100):
    result = karger_min_cut(graph)
    if result < min_cut:
        min_cut = result

print("Minimális vágás:", min_cut)

C++ Implementáció

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// Gráf szomszédsági lista reprezentáció
using Graph = unordered_map<int, vector<int>>;

int kargerMinCut(Graph graph) {
    while (graph.size() > 2) {
        // Véletlenszerű él kiválasztása
        int u = rand() % graph.size();
        auto it = graph.begin();
        advance(it, u);
        int vertex_u = it->first;

        int v_index = rand() % graph[vertex_u].size();
        int vertex_v = graph[vertex_u][v_index];

        // Csúcsok összevonása
        graph[vertex_u].insert(graph[vertex_u].end(), graph[vertex_v].begin(), graph[vertex_v].end());

        for (int neighbor : graph[vertex_v]) {
            auto& edges = graph[neighbor];
            replace(edges.begin(), edges.end(), vertex_v, vertex_u);
        }

        // Önhurok eltávolítása
        auto& edges = graph[vertex_u];
        edges.erase(remove(edges.begin(), edges.end(), vertex_u), edges.end());

        // Eltávolítjuk a vertex_v-t
        graph.erase(vertex_v);
    }

    // A megmaradt két csúcs közötti élek száma
    return graph.begin()->second.size();
}

int main() {
    srand(time(0));

    // Példa gráf szomszédsági listában
    Graph graph = {
        {1, {2, 3, 4}},
        {2, {1, 3, 4}},
        {3, {1, 2, 4}},
        {4, {1, 2, 3}}
    };

    int min_cut = INT_MAX;
    for (int i = 0; i < 100; i++) {
        Graph temp_graph = graph;
        min_cut = min(min_cut, kargerMinCut(temp_graph));
    }

    cout << "Minimális vágás: " << min_cut << endl;
    return 0;
}

Alkalmazások

  1. Hálózati optimalizáció:
    • Minimális kapcsolatvesztés meghatározása.
  2. Szociális hálózatok:
    • Közösségek szétválasztása.
  3. Vágások és particionálás:
    • Gráfpartíció optimalizálása.


Előnyök és Hátrányok

Előnyök

  • Egyszerűség: Könnyen implementálható.
  • Hatékonyság: Nagy méretű gráfok esetén is gyors.

Hátrányok

  • Valószínűségi természet: Többször kell futtatni a pontos eredmény érdekében.
  • Nem determinisztikus: A végeredmény eltérhet a futtatások között.


Összegzés

A Karger-algoritmus hatékony módszer a minimális vágás problémájának megoldására. Bár véletlenszerűségen alapul, többszörös futtatással növelhető az eredmény megbízhatósága. Pythonban és C++-ban egyaránt egyszerűen implementálható, és számos hálózati és gráfprobléma esetén hasznos.

Fordítások

Tartalom

További információk

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