In der Mathematik ist ein Hasse-Diagramm (auch Ordnungs- oder einfach Liniendiagramm genannt) eine bestimmte graphische Darstellung endlicher halbgeordneter Mengen. Solche Diagramme werden nach dem Mathematiker Helmut Hasse benannt. [1] Das Hasse-Diagramm für eine Halbordnung ergibt sich als Darstellung eines gerichteten Graphen, wobei die Elemente von die Knoten bilden. Zwei Knoten und werden durch eine Kante verbunden, wenn gilt und es keinen Knoten gibt mit. Hasse diagramm erstellen es. (Hierbei ist als und zu verstehen. ) Die Einschränkung auf solche nennt man transitive Reduktion der Halbordnung. Die Richtung der Kante wird dadurch zum Ausdruck gebracht, dass sich der Knoten oberhalb von befindet. Solch eine Anordnung lässt sich erreichen, da das Hasse-Diagramm zyklenfrei ist. Schleifen bei Reflexivität werden weggelassen. Manchmal werden Hasse-Diagramme auch verwendet, um Striktordnungen (Ordnungsrelationen zweiter Art) darzustellen. Beispiele [ Bearbeiten | Quelltext bearbeiten] Teilerverband [ Bearbeiten | Quelltext bearbeiten] Die Teiler einer natürlichen Zahl lassen sich mittels eines Hasse-Diagramms darstellen, da sie bezüglich der Teilbarkeitsrelation eine halbgeordnete Menge, den Teilerverband, bilden.
Eine Ordnung < auf einer endlichen Menge A lässt sich wie jede endliche Relation graphentheoretisch visualisieren, indem wir alle Elemente von A in der Ebene geeignet platzieren und für alle a, b ∈ A mit a < b einen Pfeil von a nach b zeichnen. Dabei wirkt sich die Transitivität oft störend aus, da sie zu einer Flut von Verbindungspfeilen führt. Wir lassen deswegen unnötige Verbindungspfeile weg. Zudem vereinbaren wir eine Wachstumsrichtung (z. B. von unten nach oben oder von links nach rechts). Dadurch entstehen sog. Hasse-Diagramme. Um sie genauer zu beschreiben, definieren wir: Definition (Nachfolger und Vorgänger) Sei < eine Ordnung auf A. Weiter seien a, b ∈ A. Dann heißt b ein direkter Nachfolger von a und a ein direkter Vorgänger von b, falls a < b und kein c existiert mit a < c und c < b. Für die Inklusion auf ℘ ({ 1, 2, 3, 4}) sind { 1, 2, 3} und { 1, 3, 4} die beiden direkten Nachfolger von { 1, 3}. Die direkten Vorgänger von { 1, 3} sind { 1} und { 3}. Diagramm - Rechner. Für die übliche Ordnung auf ℤ ist a + 1 der direkte Nachfolger und a − 1 der direkte Vorgänger von a.
Wenn eine partielle Ordnung als Hasse-Diagramm gezeichnet werden kann, in dem sich keine zwei Kanten kreuzen, wird ihr überdeckender Graph als nach oben planar bezeichnet. Eine Reihe von Ergebnissen zur Aufwärtsplanarität und zur kreuzungsfreien Hasse-Diagrammkonstruktion sind bekannt: Wenn die zu zeichnende Teilordnung ein Gitter ist, kann sie genau dann ohne Kreuzungen gezeichnet werden, wenn sie eine Ordnungsdimension von höchstens zwei hat. Hasse diagramm erstellen. [5] In diesem Fall kann eine sich nicht kreuzende Zeichnung gefunden werden, indem kartesische Koordinaten für die Elemente aus ihren Positionen in den beiden linearen Ordnungen abgeleitet werden, um die Ordnungsdimension zu realisieren, und dann die Zeichnung um einen 45-Grad-Winkel gegen den Uhrzeigersinn gedreht wird. Wenn die Teilordnung höchstens ein minimales Element oder höchstens ein maximales Element hat, dann kann in linearer Zeit geprüft werden, ob sie ein nicht kreuzendes Hasse-Diagramm hat. [6] Es ist NP-vollständig zu bestimmen, ob eine Teilordnung mit mehreren Quellen und Senken als kreuzungsfreies Hasse-Diagramm gezeichnet werden kann.
Obwohl Hasse-Diagramme ursprünglich als eine Technik zum Erstellen von Zeichnungen von teilweise geordneten Mengen von Hand entwickelt wurden, wurden sie in jüngerer Zeit automatisch mit Techniken zum Zeichnen von Graphen erstellt. [1] Der Ausdruck "Hasse-Diagramm" kann sich auch auf die transitive Reduktion als einen abstrakten gerichteten azyklischen Graphen beziehen, unabhängig von einer Zeichnung dieses Graphen, aber diese Verwendung wird hier vermieden. Hasse-Diagramm – Wikipedia. [2] [3] [4] Obwohl Hasse-Diagramme sowohl einfache als auch intuitive Werkzeuge für den Umgang mit endlichen Posets sind, erweist es sich als ziemlich schwierig, "gute" Diagramme zu zeichnen. Der Grund dafür ist, dass es im Allgemeinen viele Möglichkeiten gibt, ein Hasse-Diagramm für ein bestimmtes Poset zu zeichnen. Die einfache Technik, nur mit den minimalen Elementen einer Ordnung zu beginnen und dann inkrementell größere Elemente zu zeichnen, führt oft zu ziemlich schlechten Ergebnissen: Symmetrien und innere Struktur der Ordnung gehen leicht verloren.