Glossar

Wähle eines der Schlüsselwörter auf der linken Seite…

Graphen und NetzwerkeEinführung

Lesezeit: ~10 min

Wir haben es in unserem täglichen Umfeld mit unzähligen Netzwerken und Verbindungen zu tun: Straßen und Eisenbahnschienen, Telefonleitungen, das Internet, elektronische Schaltkreise und sogar Molekülbindungen. Außerdem gibt es soziale Netzwerke zwischen Freunden und Familien. Kannst du dir noch andere Beispiele vorstellen?

Straßen- und Schienennetze

Computer-Chips

Lieferketten

Freundschaften

Neuronale Verbindungen

Das Internet

In der Mathematik können all diese Beispiele als Graphen dargestellt werden (nicht zu verwechseln mit dem Graph einer Funktion). Ein Graph besteht aus einzelnen Punkten die genannt werden, von denen einige durch verbunden sind.

Die Graphentheorie beschäftigt sich mit Graphen und ihren Eigenschaften. Sie ist eines der spannendsten und visuell ansprechendsten Gebiete der Mathematik und hat unzählige wichtige Anwendungen.

Wir können das Layout von einfachen Graphen mit Kreisen und Linien zeichnen. Die Position der Knoten (Ecken) und die Länge der Kanten spielt dabei keine Rolle - uns interessiert nur, wie sie miteinander verbunden sind. Die Kanten können sich sogar kreuzen und müssen nicht unbedingt gerade sein.

In manchen Graphen verlaufen die Kanten nur in eine Richtung. Diese werden gerichtete Graphen genannt.

Manche Graphen bestehen aus mehreren Gruppen von Knoten, die nicht durch Kanten miteinander verbunden sind. Diese Graphen nennt man nicht zusammenhängend.

Andere Graphen können mehrere Kanten zwischen denselben Knotenpaaren enthalten, oder Knoten, die mit sich selbst verbunden sind (Schleifen).

Wir können neue Graphen aus einem bestehenden Graphen erstellen, indem wir einige der Knoten und Kanten entfernen. Das Ergebnis nennt sich Teilgraph. Hier siehst du ein paar weitere Beispiele für Graphen, mit farbigen Kanten und Knoten, die auf einen möglichen Teilgraphen hinweisen:

Wir sagen, dass die Ordnung eines Graphen die Anzahl der Knoten ist, die er hat. Der [Grad]( gloss: graph-degree) eines Knotens ist die Anzahl der Kanten, die sich an diesem Knoten treffen.

Ordnung:

Ordnung:

Grad:

Grad:

Graphen, die aus einem einzigen Knoten-Ring bestehen, werden als Kreisgraphen bezeichnet. Alle Kreisgraphen haben .

Nachdem wir diese neuen Definitionen eingeführt haben, wollen wir nun einige der faszinierenden Eigenschaften und Anwendungen von Graphen näher betrachten.