Typisierung

  Bei vielen Anwendungen von Graphen haben nicht alle Knoten bzw. Kanten ähnliche Bedeutungen. Vielmehr kann man Teilmengen von Knoten bzw. Kanten ähnlicher Bedeutung identifizieren.

Wenn man z.B. einen Stadtplan auf einen Graphen abbilden will, liegt es nahe, Straßenabschnitte als Kanten und Kreuzungen, Einmündungen, Parkplätze, Parkhäuser und Tiefgaragen als Knoten zu modellieren. Bei den Knoten fällt auf, daß man sie grob in zwei Mengen zerlegen kann, nämlich in die aller Verzweigungspunkte (Kreuzungen und Einmündungen) und die aller Parkeinrichtungen, die ihrerseits wieder feiner zerlegt werden können (siehe Abb.).

  

Abbildung: ER-Diagramm des Typisierungsbeispiels

Die Einteilung von Knoten oder Kanten zu unterschiedlichen Mengen kann durch  Typisierung realisiert werden. Die unterschiedlichen Mengen werden dabei durch  Typen repräsentiert. Die Zugehörigkeit eines Knotens bzw. einer Kante zu einer bestimmten Menge wird dann dadurch ausgedrückt, daß dem Knoten bzw. der Kante der diese Menge repräsentierende Typ zugewiesen wird.

Falls eine Menge, die durch einen Typ A repräsentiert wird, Teilmenge der durch Typ B repräsentierten Menge ist, ist A ein  Untertyp von B (A  is-a B) und B ein  Obertyp von A. So ist Parkhaus ein Untertyp von Parkgebaeude. In der Abbildung wird die Untertyprelation dadurch ausgedrückt, daß der Untertyp innerhalb des Obertyps notiert ist. Die Untertyprelation ist reflexiv und transitiv, muß aber nicht notwendigerweise antisymmetrisch sein.

Weiterhin werden die Mengen der Knoten und Kanten, die einen gemeinsamen Obertyp haben, zu  Klassen von Typen zusammengefaßt. Eine  Klasse beinhaltet alle Kanten und Knoten des gemeinsamen Obertyps sowie aller seiner Untertypen. Dabei benutzen wir den Obertypen als Bezeichner der gesamten Klasse. Im EER-Diagramm in Abbildung ist z.B. Parkgebaeude eine  Klasse, in der alle Knoten der  Typen Tiefgarage, Parkhaus und Parkgebaeude enthalten sind.