Havel–Hakimi-algoritmus
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 

d1 ≤ d2 ≤ … ≤ dn létezik ilyen egyszerű gráf?
Feltétel: ∑ di páros
Feltétel2: dn-k+1+dn-k+2+…+dn-k*(k-1) ≤ d1+d2+…+dn-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 d1 > 0, d2 ≥ ... ≥ dn fokszámú egyszerű gráf ⇐⇒ létezik d2 − 1, ..., dd1+1 − 1, dd1+2, ..., dn fokszámú egyszerű gráf.
Létezik egyszerű gráf az adott fokokkal ⇐⇒ Havel–Hakimi-algoritmus végigfut.

Havel–Hakimi-algoritmus 

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 

 fokszám szerint nemnövekvő sorba rendezzük a pontokat
 kiválasztunk egy vi csúcsot
 összekötjük a (tőle különböző) di darab legnagyobb fokú csúccsal
 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 d1 ≥ d2 ≥...≥ dn 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

Gráfelmélet
Algoritmusok
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 d1 ≤ d2 ≤ … ≤ dn létezik ilyen egyszerű gráf ? Feltétel : ∑ di páros Feltétel2 : dn-k+1+dn-k+2+…+dn-k*( k-1 ) ≤ d1+d2+…+dn-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 : ( 9 csúcs van ) kettévágjuk kis- és nagyfokúakra az a kérdés , hogy hol vannak az élek ebben az esetbencsúcs van , amifokú , 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 esetben5 élnek át kell mennie a kisfokúakhoz a kisfokúak viszontél helyett csaket tudnak befogadni → nem tudunk ebből egyszerű gráfot rajzolni ! Havel–Hakimi-tétel Létezik d1 > d2 ≥\... ≥ dn fokszámú egyszerű gráf ⇐⇒ létezik d2 −\... , dd1+1 − dd1+2,\... , dn fokszámú egyszerű gráf . Létezik egyszerű gráf az adott fokokkal ⇐⇒ Havel–Hakimi-algoritmus végigfut . Havel–Hakimi-algoritmus Az algoritmustben Václav J. Havel, 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 fokszám szerint nemnövekvő sorba rendezzük a pontokat kiválasztunk egy vi csúcsot összekötjük a ( tőle különböző ) di darab legnagyobb fokú csúccsal ezt addig ismételjük , amíg minden foklesz , 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 d1 ≥ d2 ≥...≥ dn 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 , Gráfelmélet Algoritmusok