Graph (Graphentheorie)

Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (manchmal auch Bögen). Die Kanten können gerichtet oder ungerichtet sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.

In einem U-Bahn-Netz stellt jeder Knoten eine U-Bahn-Station dar und jede Kante eine direkte Zugverbindung zwischen zwei Stationen. Die chemische Graphentheorie betrachtet Moleküle als Graphen, mit Atomen als Knoten und Molekularverbindungen als Kanten. Komplexe räumliche Gebilde wie Polyeder können als Graphen dargestellt werden (Schlegeldiagramm). Das Internet ist ein riesiger Graph aus Computern und Datenverbindungen.

Bäume wie etwa Stammbäume sind ein Sonderfall der Graphen und enthalten keine Zyklen.

Die mathematische Betrachtung von Graphen begann im 18. Jahrhundert mit dem Königsberger Brückenproblem.

1. ↑ Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 1–34 (online: 4th elektronische Ausgabe 2010 – Erstausgabe: 1996).