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.

Egyszerű, összefüggő gráf

Fokszámsorozatok realizációjaSzerkesztés

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

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ételSzerkesztés

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-algoritmusSzerkesztés

 
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 algoritmusSzerkesztés

 
Ebben az esetben az algoritmus végigfut
  1. fokszám szerint nemnövekvő sorba rendezzük a pontokat
  2. kiválasztunk egy vi csúcsot
  3. összekötjük a (tőle különböző) di 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 gyakorlatbanSzerkesztés

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ásokSzerkesztés

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