Havel–Hakimi-algoritmus

Ezt a szócikket némileg át kellene dolgozni a wiki jelölőnyelv szabályainak figyelembevételével, hogy megfeleljen a Wikipédia alapvető stilisztikai és formai követelményeinek.

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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.

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!

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.

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.

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.

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.

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