Graphen

Bäume und Hierachien In der Informatik bezeichnet der Begriff „Baum“ eine Datenstruktur und abstrakten Datentypen, mit dem sich hierarchische Strukturen abbilden lassen. Damit stellt der Baum eine spezielle Struktur derjenigen Strukturen dar, die Gegenstand der so genannten Graphentheorie sind. Wie alle Strukturen, die in der Graphentheorie behandelt werden, also beispielsweise den schon behandelten Beispielgraphen aus Kapitel „Allgemeiner Graph als Adjazenzliste“, besteht ein Baum aus Knoten und Kanten. Eine Hierarchie ist wiederum ein spezieller Baum, der durch Über-/Unterordnungsverhältnisse gekennzeichnet ist. Im Falle einer Mitarbeiterhierarchie, wie wir sie in Unternehmen vorfinden, kann man auch sagen, dass Macht von oben nach unten vererbt…

Adjazenzlisten-Modell In der Graphentheorie sind Adjazenzlisten, auch Nachbarschaftslisten genannt, eine Möglichkeit, Graphen zu repräsentieren. Dabei wird für jeden Knoten eine Liste, die Adjazenzliste, aller seiner Nachbarn (in ungerichteten Graphen) beziehungsweise Nachfolger (in gerichteten Graphen) angegeben. Betrachten wir den folgenden Graphen: Der Beispielgraph ist gerichtet, wie an den Pfeilen, welche die Kanten zieren, leicht zu erkennen ist. Nicht alle Knoten sind verbunden. An den Kanten sind Gewichte notiert. Grundsätzlich könnten auch mehrere Gewichte mit unterschiedlicher Semantik angegeben sein. Uns reicht hier ein Gewicht. – Wir werden dieses daher auch direkt in der Adjazenzliste notieren und keine diesbezügliche Normalisierung vornehmen. >In SQL…

Graphen Zu Beginn dieses Abschnitts möchte ich Sie mit einigen wichtigen Begriffen vertraut machen, die in Zusammenhang mit Graphen benötigt werden, um über diese Datenstruktur unmissverständlich sprechen zu können. Die Graphentheorie ist ein Teilgebiet der Mathematik, welches sich mit abstrakten Strukturen befasst, die als Graphen bezeichnet werden. Dabei handelt es sich nicht um Präsentationsgrafiken, wie sie beispielsweise mithilfe von Tabellenkalkulationen erstellt werden. In erster Annäherung ist ein Graph ein Diagramm aus Knoten (Nodes) und Kanten (Edges), die diese verbinden. Die Kanten können gerichtet oder ungerichtet sein. Den Kanten können Werte zugeordnet sein, wie Entfernungen zwischen zwei Orten oder die Kosten…