Hasse-diagram

A Hasse-diagram a részbenrendezések (partial order) szemléletes ábrázolására szolgáló speciális gráf. Célja, hogy egyszerűen megmutassa, mely elemek állnak közvetlen kapcsolatban egymással a rendezésben.

Definíció

Egy részbenrendezett halmaz (A, ≤) Hasse-diagramja egy olyan gráf, amelyben:

• A halmaz elemei csúcsokként jelennek meg.
• Ha a ≤ b, akkor a gráfban a csúcs a b alatt helyezkedik el.
• Élt csak akkor rajzolunk, ha a ≤ b igaz, de nincs olyan köztes c elem, amelyre a ≤ c és c ≤ b is fennáll (azaz közvetlen kapcsolat van a és b között).
• Az éleket felfelé húzzuk az alsóbb elemtől a feljebbiek felé.

Hogyan készítsünk Hasse-diagramot

• A minimális elemeket (amelyeknek nincs kisebb elemük) helyezzük az aljára.
• A maximális elemeket (amelyeknek nincs nagyobb elemük) helyezzük a tetejére.
• Irányított éleket (általában felfelé) csak a fedőkapcsolatoknál húzzunk (közvetlen utódlók).
• Rendezzük el a csúcsokat úgy, hogy a sorrend vizuálisan is átlátható legyen, lehetőleg kereszteződések nélkül.

Példa

Legyen A = {1,2,3,6}, a reláció pedig az oszthatóság (|).

A részleges rend: 1 | 2, 1 | 3, 2 | 6, 3 | 6.

A Hasse-diagram: 1 legalul, fölötte 2 és 3 (párhuzamosan), és legfelül 6, amely mindkettőhöz kapcsolódik.

Tulajdonságok

• A Hasse-diagram mindig irányított aciklikus gráf (DAG).
• A reflexív éleket (a → a) nem ábrázoljuk.
• A tranzitív kapcsolatokat (ha a ≤ b és b ≤ c, akkor a ≤ c) sem rajzoljuk be külön, mert az élek csak közvetlen kapcsolatot mutatnak.
• A Hasse-diagram átláthatóvá teszi a részbenrendezés hierarchiáját.

Összefoglalás

A Hasse-diagram segítségével egy részbenrendezést ábrázolhatunk egyszerű és áttekinthető módon. Csak a közvetlen kapcsolatokat mutatja meg, elhagyva a reflexív és tranzitív éleket. Ezáltal könnyen látható a halmaz elemeinek hierarchiája.

Gyakorló feladat