Graph (Graphentheorie)

Ein Graph ist in der Graphentheorie ein Gebilde aus Knoten (auch Ecken oder Punkte), die durch Kanten verbunden sein können. Obwohl Graphen vielfach durch eine Zeichnung dargestellt werden, sind sie „nur“ mathematische Strukturen. Dies bedeutet vor allem, dass verschiedene Bilder denselben Graphen darstellen können.

Definition

Ein Graph G ist ein geordnetes Paar zweier Mengen:

G = (V, E)

Dabei bezeichnet V die Menge der im Graph enthaltenen Knoten und E die Menge der Kanten des Graphen. Die Bezeichnungen der Mengen entstammen dem Englischen: V für vertex (engl. für Knoten) und E für edge (engl. für Kante).

Kategorisierung von Graphen

Man unterscheidet in der Graphentheorie vor allem zwischen ungerichteten und gerichteten Graphen sowie Graphen mit Mehrfachkanten und ohne Mehrfachkanten. Hypergraphen sind eine weitere Form von Graphen, die untersucht werden.

Weitere Informationen findet man im Artikel Typen von Graphen in der Graphentheorie.