Wikiszótár

Bron-Kerbosch algoritmus

Magyar

Kiejtés

  • IPA: [ ˈbroŋkɛrboʃxɒlɡoritmuʃ]

Főnév

Bron-Kerbosch algoritmus

  1. (matematika) A Bron-Kerbosch algoritmus egy hatékony rekurzív algoritmus, amely a gráf összes maximális klikkjét (teljes részgráfját) megtalálja. A maximális klikk egy olyan csúcshalmaz, amelyben minden csúcs összeköttetésben van egymással, és a halmaz bővítése már nem eredményez klikket.


Algoritmus Menete

Az algoritmus a következő három halmazzal dolgozik: 1. R – Az aktuális klikk (kezdetben üres). 2. P – Azok a csúcsok, amelyek még hozzáadhatók ( R )-hez. 3. X – Azok a csúcsok, amelyek korábban voltak ( R )-ben, de már nem lehetnek részei az aktuális klikknek.

Pszeudokód

function BronKerbosch(R, P, X):
    if P és X üres:
        output R  # R egy maximális klikk
    for minden v ∈ P:
        BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P := P \ {v}
        X := X ∪ {v}

Optimalizáció Pivotálással

A pivotálás csökkenti az algoritmus által bejárt csúcsok számát azáltal, hogy a választott pivotcsúcs szomszédait előnyben részesíti.

Optimalizált Pszeudokód

function BronKerboschPivot(R, P, X):
    if P és X üres:
        output R  # R egy maximális klikk
    pivot = egy elem P ∪ X-ből
    for minden v ∈ P \ N(pivot):
        BronKerboschPivot(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P := P \ {v}
        X := X ∪ {v}

Python Implementáció

def bron_kerbosch(R, P, X, graph, results):
    """
    Bron-Kerbosch algoritmus maximális klikkek keresésére.

    Args:
        R: Az aktuális klikk.
        P: Azok a csúcsok, amelyek még hozzáadhatók a klikkhez.
        X: Azok a csúcsok, amelyek nem bővíthetik a klikket.
        graph: A gráf szomszédsági listája.
        results: Az összes maximális klikket tartalmazó lista.
    """
    if not P and not X:
        results.append(R)
        return
    for v in list(P):
        bron_kerbosch(R.union({v}), 
                      P.intersection(graph[v]), 
                      X.intersection(graph[v]), 
                      graph, 
                      results)
        P.remove(v)
        X.add(v)

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

results = []
bron_kerbosch(set(), set(graph.keys()), set(), graph, results)
print("Maximális klikkek:", results)

C++ Implementáció

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>

using namespace std;

typedef unordered_map<int, set<int>> Graph;

void bronKerbosch(set<int> R, set<int> P, set<int> X, const Graph& graph, vector<set<int>>& results) {
    if (P.empty() && X.empty()) {
        results.push_back(R);
        return;
    }
    auto it = P.begin();
    while (it != P.end()) {
        int v = *it;
        set<int> newR = R;
        newR.insert(v);

        set<int> newP, newX;
        set_intersection(P.begin(), P.end(), graph.at(v).begin(), graph.at(v).end(),
                         inserter(newP, newP.begin()));
        set_intersection(X.begin(), X.end(), graph.at(v).begin(), graph.at(v).end(),
                         inserter(newX, newX.begin()));

        bronKerbosch(newR, newP, newX, graph, results);

        P.erase(v);
        X.insert(v);
        it = P.begin();
    }
}

int main() {
    Graph graph = {
        {1, {2, 3}},
        {2, {1, 3, 4}},
        {3, {1, 2, 4}},
        {4, {2, 3}}
    };

    vector<set<int>> results;
    bronKerbosch({}, {1, 2, 3, 4}, {}, graph, results);

    cout << "Maximális klikkek:" << endl;
    for (const auto& clique : results) {
        for (int node : clique) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

Optimalizált Pivotálás Pythonban

def bron_kerbosch_with_pivot(R, P, X, graph, results):
    if not P and not X:
        results.append(R)
        return
    # Pivot választása
    pivot = next(iter(P.union(X)))
    for v in P - graph[pivot]:
        bron_kerbosch_with_pivot(R.union({v}), 
                                 P.intersection(graph[v]), 
                                 X.intersection(graph[v]), 
                                 graph, 
                                 results)
        P.remove(v)
        X.add(v)

# Ugyanaz a gráf, mint korábban
results = []
bron_kerbosch_with_pivot(set(), set(graph.keys()), set(), graph, results)
print("Maximális klikkek pivotálással:", results)

Alkalmazások

  1. Szociális hálózatok:
    • Erős közösségek azonosítása (klikkek).
  2. Bioinformatika:
    • Fehérje-fehérje interakciós hálózatok elemzése.
  3. Térképezés és klaszterezés:
    • Adatok klaszterezése gráfok segítségével.
  4. Adatbázisok:
    • Adattáblák közötti maximális kapcsolatok keresése.


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

Előnyök

  • Egyszerű implementáció: Könnyen érthető rekurzív felépítés.
  • Hatékonyság: Pivotálással jelentősen gyorsítható.

Hátrányok

  • Kombinatorikus robbanás: Nagy méretű és sűrű gráfokon lassú lehet.
  • Memóriaigény: A csúcsok halmazainak kezelése memóriaigényes lehet.


Összegzés

A Bron-Kerbosch algoritmus hatékony módszer a maximális klikkek meghatározására, különösen ritka gráfok esetében. Az algoritmus pivotálással tovább optimalizálható. Pythonban és C++-ban egyaránt könnyen implementálható, és számos területen alkalmazható, például szociális hálózatok és bioinformatikai hálózatok elemzésére.

Fordítások

Tartalom

További információk

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