Es ist ein nützliches Werkzeug, das den zugehörigen Teilauftrag vollständig beschreibt. Daher wird es auch Ordnungsdiagramm genannt. Es ist sehr einfach, einen gerichteten Graphen einer Beziehung auf einer Menge A in ein äquivalentes Hasse-Diagramm umzuwandeln. Daher müssen beim Zeichnen eines Hasse-Diagramms die folgenden Punkte beachtet werden.
- Die Eckpunkte im Hasse-Diagramm werden durch Punkte und nicht durch Kreise bezeichnet.
- Da eine Teilordnung reflexiv ist, muss jeder Scheitelpunkt von A auf sich selbst bezogen sein, sodass die Kanten von einem Scheitelpunkt zu sich selbst im Hasse-Diagramm gelöscht werden.
- Da eine Teilordnung transitiv ist, gilt immer dann, wenn aRb, bRc, aRc. Eliminieren Sie alle Kanten, die durch die transitive Eigenschaft im Hasse-Diagramm impliziert werden, d. h. löschen Sie die Kante von a bis c, behalten Sie aber die beiden anderen Kanten bei.
- Wenn ein Scheitelpunkt „a“ durch eine Kante mit dem Scheitelpunkt „b“ verbunden ist, d. h. aRb, dann erscheint der Scheitelpunkt „b“ über dem Scheitelpunkt „a“. Daher kann der Pfeil an den Kanten im Hasse-Diagramm weggelassen werden.
Das Hasse-Diagramm ist viel einfacher als der gerichtete Graph der Teilordnung.
Beispiel: Betrachten Sie die Menge A = {4, 5, 6, 7}. Sei R die Beziehung ≦ auf A. Zeichnen Sie den gerichteten Graphen und das Hasse-Diagramm von R.
Lösung: Die Beziehung ≦ auf der Menge A ist gegeben durch
R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
Der gerichtete Graph der Beziehung R ist wie in Abb. dargestellt:
Um das Hasse-Diagramm der Teilordnung zu zeichnen, wenden Sie die folgenden Punkte an:
- Löschen Sie alle durch die reflexive Eigenschaft implizierten Kanten, d. h.
(4, 4), (5, 5), (6, 6), (7, 7) - Löschen Sie alle durch die transitive Eigenschaft implizierten Kanten, d. h.
(4, 7), (5, 7), (4, 6) - Ersetzen Sie die Kreise, die die Eckpunkte darstellen, durch Punkte.
- Lassen Sie die Pfeile weg.
Das Hasse-Diagramm ist in Abb. dargestellt:
Obere Grenze: Betrachten Sie B als Teilmenge einer teilweise geordneten Menge A. Ein Element x ∈ A heißt Obergrenze von B, wenn y ≦ x für jedes y ∈ B.
Untergrenze: Betrachten Sie B als Teilmenge einer teilweise geordneten Menge A. Ein Element z ∈ A heißt Untergrenze von B, wenn z ≦ x für jedes x ∈ B.
Beispiel: Betrachten Sie die in Abb. gezeigte Ordnung des Posets A = {a, b, c, d, e, f, g}. Sei auch B = {c, d, e}. Bestimmen Sie die Ober- und Untergrenze von B.
xd xd Bedeutung
Lösung: Die Obergrenze von B ist e, f und g, da jedes Element von B „≤“ e, f und g ist.
Die unteren Grenzen von B sind a und b, da a und b „≤“ alle Elemente von B sind.
Kleinste Obergrenze (SUPREMUM):
Sei A eine Teilmenge einer teilweise geordneten Menge S. Ein Element M in S heißt Obergrenze von A, wenn M auf jedes Element von A folgt, d. h. wenn für jedes x in A x gilt<=m< p>
Wenn eine Obergrenze von A jeder anderen Obergrenze von A vorausgeht, wird sie als Supremum von A bezeichnet und mit Sup (A) bezeichnet.
Größte Untergrenze (INFIMUM):
Ein Element m in einem Poset S heißt Untergrenze einer Teilmenge A von S, wenn m vor jedem Element von A steht, d. h. wenn für jedes y in A m gilt<=y < p>
Wenn eine Untergrenze von A auf jede andere Untergrenze von A folgt, wird sie als Infimum von A bezeichnet und mit Inf (A) bezeichnet.
Beispiel: Bestimmen Sie die kleinste Obergrenze und die größte Untergrenze von B = {a, b, c} (falls vorhanden) des Posets, dessen Hasse-Diagramm in Abb. dargestellt ist:
Lösung: Die kleinste Obergrenze ist c.
Die größte Untergrenze ist k.