Hasse-Diagramm

Das Hasse-Diagramm ist ein spezieller Graph zur anschaulichen Darstellung von Partialordnungen. Sein Zweck ist es, einfach zu zeigen, welche Elemente direkt zueinander in Relation stehen in der Ordnung.

Definition

Das Hasse-Diagramm eines teilweise geordneten Satzes (A, ≤) ist ein Graph, in dem:

• Die Elemente der Menge als Knoten erscheinen.
• Wenn a ≤ b, dann ist im Graphen der Knoten a unter b platziert.
• Wir zeichnen eine Kante nur, wenn a ≤ b wahr ist, aber es gibt kein intermediäres c-Element, für das a ≤ c und c ≤ b gilt (d.h., es gibt eine direkte Verbindung zwischen a und b).
• Die Kanten werden nach oben von niedrigeren zu höheren Elementen gezeichnet.

Wie man ein Hasse-Diagramm konstruiert

• Platziere die minimalen Elemente (diejenigen ohne kleinere Elemente) unten.
• Platziere die maximalen Elemente (diejenigen ohne größere Elemente) oben.
• Zeichne gerichtete Kanten (meist nach oben) nur für Überdeckungsrelationen (direkte Nachfolger).
• Ordne die Knoten so an, dass die Ordnung visuell klar ist, ohne kreuzende Kanten, wenn möglich.

Beispiel

Sei A = {1,2,3,6}, mit der Teilbarkeitsrelation (|).

Die Partialordnung: 1 | 2, 1 | 3, 2 | 6, 3 | 6.

Das Hasse-Diagramm: 1 unten, darüber 2 und 3 (parallel), und 6 oben verbunden mit beiden 2 und 3.

Eigenschaften

• Das Hasse-Diagramm ist immer ein gerichteter azyklischer Graph (DAG).
• Reflexive Kanten (a → a) werden nicht dargestellt.
• Transitive Verbindungen (wenn a ≤ b und b ≤ c, dann a ≤ c) werden nicht separat gezeichnet, da Kanten nur direkte Verbindungen zeigen.
• Das Hasse-Diagramm macht die Hierarchie der Partialordnung leicht sichtbar.

Zusammenfassung

Mit dem Hasse-Diagramm können wir eine Partialordnung einfach und übersichtlich darstellen. Es zeigt nur direkte Verbindungen, indem es reflexive und transitive Kanten weglässt. Dadurch wird die Hierarchie der Elemente des Satzes leicht sichtbar.

Übungsaufgabe