10 – Grundbegriffe der Graphentheorie

 

Relationen- und Graphentheorie gehören zu den wichtigsten Hilfsmitteln der Informatik, die aus der diskreten Mathematik stammen.
Ein Graph setzt sich aus einer Menge von Knoten V (vertices) und einer Menge von Kanten E (edges) zusammen.

Jede Kante ist dabei durch zwei Knoten ("Endpunkte") definiert. Die Objekte, die in der Knoten- und Kantenmenge enthalten sind, müssen nichts mit geometrischen Objekten zu tun haben. Vielmehr ist die Graphentheorie ein Hilfsmittel zur Beschreibung beliebiger Beziehungen zwischen Objekten beliebigen Typs.
Eine Kante heißt inzident an einem Knoten v, wenn der Knoten v Endpunkt der Kante ist. Adjazente Knoten sind Knoten, die durch eine Kante verbunden sind.
Aufgaben, die mit der Graphentheorie gelöst werden können, sind z.B.:

  • Ist in einem System von vernetzten Rechnern Rechner B auch dann noch von Rechner A aus erreichbar, wenn eine der Netzwerkverbindungen gekappt wird (Erreichbarkeitsproblem)?
  • Suche in einem Straßennetz die kürzeste Verbindung von A nach B (Wegsuche).
  • Ermittle die minimale Bauzeit eines Bauprojektes (Terminplanung).

Im Einzelnen unterscheidet man sogenannte ungerichtete Graphen, d.h. Graphen, in denen die Richtung der Kanten (z.B. von Knoten a nach Knoten b oder umgekehrt) uninteressant ist, von gerichteten Graphen (Digraphen = directed graphs). Die Richtung der Kanten spielt z.B. bei der Beschreibung eines Straßennetzes, das auch Einbahnstraßen enthält, eine Rolle.

Als Beispiele gerichteter Graphen haben wir bereits Binärbäume kennengelernt.
Graphen werden anschaulich durch Linienzüge dargestellt. In vielen Anwendungen ist es notwendig, die Kanten eines Graphen zu bewerten. Beispielsweise setzt sich ein Rohrleitungsnetz im allgemeinen nicht aus lauter Rohren gleichen Durchmessers zusammen. Der Rohrdurchmesser spielt also eine wichtige Rolle als Attribut der Kanten. Viele Graphenalgorithmen verwenden solche Attribute zu Kanten. Man spricht von bewerteten Graphen:

Es können entweder, wie hier, die Kanten bewertet werden, oder die Knoten selber. Ein Graph mit bewerteten Kanten entspricht zum Beispiel einem Straßennetz, in dem auf den Straßen Mautgebühren oder einfach Benzinkosten anfallen. Ein Graph mit bewerteten Knoten entspricht zum Beispiel einem Netz öffentlicher Verkehrsmittel, bei dem an den Knoten Aufwand durch Umsteigen oder Wartezeit entsteht.