Havel–Hakimi-algoritmus

Egyszerű, összefüggő gráf

A matematikában a gráfok rendkívül gyakran használt struktúrák. A számítástudományban nagy szerepet játszanak a gráfokkal foglalkozó algoritmusok. Számos érdekes probléma fogalmazható meg ezek segítségével.

Fokszámsorozatok realizációja

Ilyen fokszámsorozattal nem létezik egyszerű gráf

d₁ ≤ d₂ ≤ … ≤ d_n létezik ilyen egyszerű gráf?
Feltétel: ∑ d_i páros
Feltétel2: d_n-k+1+d_n-k+2+…+d_n-k*(k-1) ≤ d₁+d₂+…+d_n-k (minden k-ra)
Megjegyzés: Ez szükséges feltétel. Kicsi módosítás kell, hogy elégséges legyen.
Pl.: fokszámok: 1, 1, 1, 2, 2, 2, 7, 7, 7 (9 csúcs van)

• kettévágjuk kis- és nagyfokúakra
• az a kérdés, hogy hol vannak az élek
• ebben az esetben 3 csúcs van, ami 7 fokú, ezek a legnagyobbak, így ezen három csúcs kerül a nagyfokúak csoportjába, a többi pedig a kisfokúakhoz
• ebben az esetben 3*5 élnek át kell mennie a kisfokúakhoz
• a kisfokúak viszont 15 él helyett csak 9-et tudnak befogadni

→ nem tudunk ebből egyszerű gráfot rajzolni!

Havel–Hakimi-tétel

Létezik d₁ > 0, d₂ ≥ ... ≥ d_n fokszámú egyszerű gráf ⇐⇒ létezik d₂ − 1, ..., d_d1+1 − 1, d_d1+2, ..., d_n fokszámú egyszerű gráf.
Létezik egyszerű gráf az adott fokokkal ⇐⇒ Havel–Hakimi-algoritmus végigfut.

Havel–Hakimi-algoritmus

Ebben az esetben az algoritmus elakad

Az algoritmust 1955-ben Václav J. Havel, 1962-ben pedig Seifollah Louis Hakimi adta ki.
A Havel–Hakimi-algoritmus egy gráfelméletbeli algoritmus, mely segítséget nyújt a gráf megvalósításában. A kérdés az, hogy létezik-e adott fokszámú csúcsokkal rendelkező egyszerű gráf. Ezen algoritmus létrehoz egy különleges, átlátható megoldást abban az esetben, ha létezik ilyen egyszerű gráf, vagy azt bizonyítja, hogy az ember nem talál egy pozitív választ. Belátjuk, hogy ha az algoritmus elakad, akkor nem létezik a fokszámsorozathoz egyszerű realizáció. Ez a konstrukció egy rekurzív algoritmuson alapul.

Az előző tétel alapján az algoritmus

Ebben az esetben az algoritmus végigfut

1. fokszám szerint nemnövekvő sorba rendezzük a pontokat
2. kiválasztunk egy v_i csúcsot
3. összekötjük a (tőle különböző) d_i darab legnagyobb fokú csúccsal
4. ezt addig ismételjük, amíg minden fok 0 lesz, ekkor egy egyszerű gráfot kapunk, melynek fokszámsorozata a kiindulási sorozat.

Algoritmus alkalmazása a gyakorlatban

Rajzolunk n csúcsot. Rájuk írjuk a (még) kívánatos fokszámokat. Kiválasztjuk (az egyik) legnagyobb fokú csúcsot, összekötjük az utána következő szükséges számú, legnagyobb fokú csúcsokkal. Kijavítjuk a fokokat, vagyis amely csúcsba húztunk élet, annak fokszámát eggyel csökkentjük. Majd így folytatjuk addig, amíg minden csúcs esetében az élek száma meg nem egyezik a kívánt fokszámmal. Így megmutattuk, hogy a d₁ ≥ d₂ ≥...≥ d_n fokszámsorozattal rendelkező gráfok halmazából hogyan lehet előállítani egy tetszőlegeset.
De ezzel a módszerrel nem lehet az összes ilyen gráfot előállítani.

Források

• Véges matematika – Elekes György, Brunczel András (ELTE egyetemi jegyzet)
• V. Havel: A remark on the existence of finite graphs, 1955