Wikiszótár

Havel-Hakimi-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈhɒvɛlhɒkimiɒlɡoritmuʃ]

Főnév

Havel-Hakimi-algoritmus

  1. (matematika)

Havel-Hakimi-algoritmus

A Havel-Hakimi-algoritmus egy gráfelméleti algoritmus, amely egy adott fokszámsorozatról eldönti, hogy létezik-e olyan egyszerű gráf, amelynek csúcsfokai megegyeznek ezzel a sorozattal. Az algoritmust Vaclav Havel (1955) és Simon Hakimi (1962) dolgozta ki.


Fő ötlet

Egy fokszámsorozat akkor valósítható meg egy egyszerű gráfban, ha az algoritmus ismételt csökkentésekkel és rendezésekkel ki tudja szűrni az érvényes csúcsösszekötéseket.


Algoritmus működése

Bemenet:

  • Egy nem negatív egész számokat tartalmazó sorozat ((d_1, d_2, , d_n)).

Kimenet:

  • Igaz: Ha létezik egy egyszerű gráf, amely megfelel a sorozatnak.
  • Hamis: Ha nem létezik ilyen gráf.

Feltételek:

  1. Egy egyszerű gráf:
    • Nem tartalmaz hurokéleket.
    • Nem tartalmaz párhuzamos éleket.


Lépések

  1. Sorozat rendezése:
    • Rendezzük a fokszámsorozatot csökkenő sorrendbe.
  2. Érvénytelen fokszám kiszűrése:
    • Ha bármelyik fokszám negatív, a sorozat nem megvalósítható ((Hamis)).
  3. Nullák ellenőrzése:
    • Ha minden fokszám (0), akkor a sorozat érvényes ((Igaz)).
  4. Csúcsok csökkentése:
    • Vegyük a legnagyobb fokszámot ((d_1)), majd távolítsuk el azt a sorozatból.
    • Csökkentsük az első (d_1) elem értékét (1)-gyel (kivéve, ha ez negatív értéket eredményez).
  5. Ismétlés:
    • Térj vissza az első lépéshez.


Pszeudokód

HavelHakimi(sequence):
    amíg sequence nem üres:
        rendezd sequence-et csökkenő sorrendbe
        ha a sequence első eleme negatív:
            térj vissza Hamis
        ha minden elem 0:
            térj vissza Igaz
        vegyük ki az első elemet (max_degree)
        ha max_degree > len(sequence):
            térj vissza Hamis
        csökkentsük a sequence első max_degree elemét 1-gyel
    térj vissza Igaz

Példa

Bemenet:

([4, 3, 3, 2, 2])

  1. Rendezés: ([4, 3, 3, 2, 2])
  2. Első elem kivétele ((d_1 = 4)): ([3, 3, 2, 2])
  3. Első négy elem csökkentése: ([2, 2, 1, 1])
  4. Ismétlés:
    • Rendezés: ([2, 2, 1, 1])
    • Első elem kivétele ((d_1 = 2)): ([2, 1, 1])
    • Csökkentés: ([1, 0, 0])
  5. Ismétlés:
    • Rendezés: ([1, 0, 0])
    • Első elem kivétele ((d_1 = 1)): ([0, 0])
    • Csökkentés: ([0, 0])
  6. Minden elem (0): (Igaz).

Kimenet:

  • A sorozat megvalósítható.


Python implementáció

def havel_hakimi(sequence):
    while sequence:
        # Rendezés csökkenő sorrendbe
        sequence.sort(reverse=True)
        
        # Negatív értékek ellenőrzése
        if sequence[0] < 0:
            return False
        
        # Nullák ellenőrzése
        if all(degree == 0 for degree in sequence):
            return True
        
        # Legnagyobb fokszám eltávolítása
        max_degree = sequence.pop(0)
        
        # Ellenőrizzük, hogy van-e elég csúcs csökkenteni
        if max_degree > len(sequence):
            return False
        
        # Csökkentsük az első max_degree csúcsot
        for i in range(max_degree):
            sequence[i] -= 1
    
    return True

# Példa használat
sequence = [4, 3, 3, 2, 2]
print("Megvalósítható:", havel_hakimi(sequence))

Kimenet: 

Megvalósítható: True

C++ implementáció

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool havel_hakimi(vector<int> sequence) {
    while (!sequence.empty()) {
        // Rendezés csökkenő sorrendbe
        sort(sequence.rbegin(), sequence.rend());
        
        // Negatív értékek ellenőrzése
        if (sequence[0] < 0) {
            return false;
        }
        
        // Nullák ellenőrzése
        if (all_of(sequence.begin(), sequence.end(), [](int degree) { return degree == 0; })) {
            return true;
        }
        
        // Legnagyobb fokszám eltávolítása
        int max_degree = sequence[0];
        sequence.erase(sequence.begin());
        
        // Ellenőrizzük, hogy van-e elég csúcs csökkenteni
        if (max_degree > sequence.size()) {
            return false;
        }
        
        // Csökkentsük az első max_degree csúcsot
        for (int i = 0; i < max_degree; ++i) {
            sequence[i] -= 1;
        }
    }
    
    return true;
}

int main() {
    vector<int> sequence = {4, 3, 3, 2, 2};
    cout << "Megvalósítható: " << (havel_hakimi(sequence) ? "True" : "False") << endl;
    return 0;
}

Kimenet: 

Megvalósítható: True

Előnyök

  1. Egyszerűség:
    • Az algoritmus intuitív és könnyen implementálható.
  2. Hatékonyság:
    • Az algoritmus időkomplexitása (O(n^2)), ami kis méretű gráfok esetén megfelelő.
  3. Gráfelméleti alapok:
    • Alkalmas gráfok fokszámsorozatainak vizsgálatára.


Hátrányok

  1. Nagyobb méretű adatok esetén:
    • Az (O(n^2)) időkomplexitás miatt lassú lehet nagy méretű sorozatoknál.
  2. Specifikus alkalmazás:
    • Csak fokszámsorozatok realizálhatóságának vizsgálatára alkalmas, nem adja meg a gráf konkrét szerkezetét.


Összegzés

A Havel-Hakimi-algoritmus egy hatékony eszköz annak eldöntésére, hogy egy fokszámsorozat megvalósítható-e egyszerű gráfként. Alkalmazásai közé tartozik a gráfok modellezése, hálózatelemzés és a gráfelméleti problémák vizsgálata. Egyszerűsége és intuitivitása miatt széles körben tanítják az algoritmusok és gráfelmélet kurzusokon.

További információk

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