Hasse-Diagramm
Bei einem Hasse-Diagramm (auch Ordnungsdiagramm) handelt es sich um eine bestimmte Art der Darstellung von Ordnungsrelationen, die zumeist für Halbordnungen und gelegentlich auch für Striktordnungen verwendet wird.
Der Name Hasse-Diagramm geht auf den deutschen Mathematiker Helmut Hasse zurück.
Beschreibung
Bei einem Hasse-Diagramm handelt es sich um eine vereinfachte Form der Darstellung einer zweistelligen Relation \(R \subseteq A \times A\) auf einer Menge \(A\) als (gerichteter) Graph. Die Elemente der Menge \(A\) bilden hierbei die Knoten des Graphen.
Für Hasse-Diagramme gelten die folgenden Eigenschaften:
- Zwei Knoten \(a,b \in A\) sind genau dann durch eine Kante von \(a\) nach \(b\) verbunden, falls \(a\) in Relation mit \(b\) steht und falls kein Element \(c \in A\) existiert, für das \((a,c) \in R\) und \((c,b) \in R\) gilt. Kanten, die sich aufgrund der Transitivität ergeben, werden also nicht dargestellt; es handelt sich hierbei um die sogenannte transitive Reduktion der Relation.
- Schlingen, also reflexive Kanten der Form \((a,a)\), werden nicht dargestellt.
- Kanten sind stets nach oben orientiert. Gilt \((a,b) \in R\), so wird \(b\) oberhalb von \(a\) dargestellt. Aufgrund der daraus resultierenden Orientierung aller Kanten nach oben können sämtliche Pfeilspitzen der Kanten weggelassen werden.
Die konkrete Anordnung der Knoten, sofern sie durch die obigen Eigenschaften nicht explizit vorgegeben ist, kann beliebig gewählt werden.
Beispiel
Es sei \(\mathcal{P}(A)\) die Potenzmenge der Menge \(A = \bigl\{ a,b,c \bigr\}\). Die betrachtete Relation \(R \subseteq \mathcal{P}(A) \times \mathcal{P}(A)\) sei definiert als
Es handelt sich bei \(R\) folglich um die Teilmengenbeziehung \(\subseteq\) auf der Menge \(\mathcal{P}(A)\). Die Relation \(R\) besitzt die folgende Darstellung als gerichteter Graph. Bei den grauen Kanten handelt es sich um diejenigen Kanten, die sich aus der Reflexivität und aus der Transitivität der Relation ergeben.
Für das Hasse-Diagramm der Relation \(R\) werden alle reflexiven Kanten, alle transitiven Kanten sowie die Pfeilspitzen entfernt, sodass sich die folgende, vereinfachte Darstellung ergibt:
