Graphentheorie — Knoten, Kanten & Grundbegriffe

Die Graphentheorie untersucht Graphen, also Strukturen aus Knoten und Kanten. Ein Knoten ist ein Objekt, und eine Kante zeigt eine Beziehung zwischen zwei Objekten.

Wenn du nach den Grundlagen der Graphentheorie suchst, beginne mit dieser Idee: Ein Graph ist eine klare Möglichkeit, Verbindungen zu modellieren. Personen in einem sozialen Netzwerk, Städte, die durch Straßen verbunden sind, und Webseiten, die miteinander verlinkt sind, lassen sich alle durch Graphen darstellen.

Was ein Graph in der Mathematik bedeutet

In einem ungerichteten Graphen sagt eine Kante aus, dass zwei Knoten verbunden sind, und diese Verbindung hat keine Richtung. Wenn $A$ mit $B$ verbunden ist, dann ist auch $B$ mit $A$ verbunden.

In einem gerichteten Graphen haben Kanten dagegen eine Richtung, also sind $A \to B$ und $B \to A$ verschiedene Aussagen. Viele Beispiele für den Einstieg verwenden einfache ungerichtete Graphen, das heißt: keine Schleifen und keine mehrfachen Kanten zwischen denselben zwei Knoten.

Diese Bedingung ist wichtig, weil Definitionen oft zuerst für einfache ungerichtete Graphen eingeführt werden. Wenn sich der Typ des Graphen ändert, kann sich auch die Bedeutung von Begriffen ändern.

Grundbegriffe der Graphentheorie, die du zuerst kennen solltest

Knoten und Kanten

Ein Knoten ist das Objekt, das du verfolgen möchtest. Eine Kante ist die Verbindung, die du verfolgen möchtest.

Wenn ein Graph Städte und Straßen modelliert, dann sind die Städte die Knoten und die Straßen die Kanten.

Grad

In einem ungerichteten Graphen ist der Grad eines Knotens die Anzahl der Kanten, die an ihn angrenzen.

Wenn eine Stadt Straßen zu drei anderen Städten hat, dann ist ihr Grad $3$.

Weg

Ein Weg ist eine Folge von Knoten, bei der jedes aufeinanderfolgende Paar durch eine Kante verbunden ist.

Wenn es einen Weg von einem Knoten zu einem anderen gibt, kannst du dich entlang von Kanten von einem zum anderen bewegen.

Kreis

Ein Kreis ist ein Weg, der am selben Knoten beginnt und endet. In der üblichen Grunddefinition wird dabei kein anderer Knoten wiederholt.

Ein Kreis zeigt, dass es im Graphen eine geschlossene Schleife gibt.

Zusammenhang und Zusammenhangskomponenten

Ein ungerichteter Graph ist zusammenhängend, wenn jeder Knoten von jedem anderen Knoten durch irgendeinen Weg erreicht werden kann.

Wenn das nicht gilt, zerfällt der Graph in Zusammenhangskomponenten. Jede Komponente ist ein zusammenhängender Teil des Graphen.

Durchgerechnetes Beispiel: Ein kleiner Graph

Angenommen, ein Graph hat die Knoten $A$, $B$, $C$, $D$ und $E$ sowie die Kanten

$$AB,\ AC,\ BC,\ CD$$

Das ergibt ein Dreieck auf $A$, $B$ und $C$, eine zusätzliche Kante von $C$ nach $D$ und einen isolierten Knoten $E$.

Jetzt lassen sich die wichtigsten Ideen leicht erkennen.

Die Grade sind

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Es gibt einen Weg von $A$ nach $D$:

$$A-C-D$$

Es gibt einen Kreis:

$$A-B-C-A$$

Der Graph ist nicht zusammenhängend, weil $E$ von den anderen Knoten aus nicht erreicht werden kann. Der Graph hat also zwei Zusammenhangskomponenten: eine mit $A,B,C,D$ und eine, die nur aus $E$ besteht.

Dieses eine Beispiel zeigt, wie Grad, Weg, Kreis, isolierte Knoten und Zusammenhangskomponenten zusammenhängen.

Ein schneller Check: Summe der Grade

Für jeden endlichen ungerichteten Graphen gilt:

$$\sum \deg(v) = 2|E|$$

Das funktioniert, weil jede Kante genau zwei Endpunkte hat und daher zu zwei Gradwerten jeweils $1$ beiträgt.

Im obigen Beispiel ist die Summe der Grade

$$2+2+3+1+0=8$$

und die Anzahl der Kanten ist $4$, also

$$2|E| = 2 \cdot 4 = 8$$

Das ist eine nützliche Kontrolle, wenn du Grade von Hand zählst. Wenn die Zahlen nicht übereinstimmen, ist etwas falsch.

Häufige Fehler in der Graphentheorie

Knoten und Kanten verwechseln

Knoten sind die Objekte. Kanten sind die Beziehungen zwischen ihnen.

Vergessen, welche Art von Graph vorliegt

Eine Aussage, die für einen einfachen ungerichteten Graphen stimmt, muss für einen gerichteten Graphen oder für einen Graphen mit Schleifen möglicherweise angepasst werden.

Einen Weg wie einen Kreis behandeln

Ein Weg muss nicht zu seinem Startpunkt zurückkehren. Ein Kreis schon.

Isolierte Knoten ignorieren

Ein Knoten mit Grad $0$ gehört trotzdem zum Graphen. Er kann beeinflussen, ob der Graph zusammenhängend ist.

Wo die Grundlagen der Graphentheorie verwendet werden

Diese Ideen tauchen in Computernetzwerken, Routenplanung, Terminplanung, Empfehlungssystemen und sozialen Netzwerken auf. Der Kontext ändert sich, aber dieselben Fragen kommen immer wieder vor: Was ist verbunden, was ist erreichbar, und wo gibt es Schleifen?

Deshalb erscheint die Graphentheorie früh sowohl in der diskreten Mathematik als auch in der Informatik.

Probiere einen ähnlichen Graphen aus

Zeichne vier Knoten $P$, $Q$, $R$ und $S$. Füge die Kanten $PQ$, $QR$, $RS$ und $SP$ hinzu.

Beantworte dann drei Fragen: Wie groß ist der Grad jedes Knotens, ist der Graph zusammenhängend, und enthält der Graph einen Kreis?