Grundlagen der Graphentheorie

Ein Graph besteht aus einer Menge von Knoten (V) und Kanten (E), die diese Knoten verbinden. Stell dir das wie Städte (Knoten) und Straßen dazwischen (Kanten) vor. Diese einfache Struktur ist die Basis für viele Probleme der Informatik.

Es gibt verschiedene Arten von Graphen: Bei gewichteten Graphen haben die Kanten unterschiedliche Werte (z.B. Entfernungen zwischen Städten). Gerichtete Graphen haben Kanten mit einer Pfeilrichtung, ähnlich wie Einbahnstraßen. Ungerichtete Graphen hingegen erlauben Bewegungen in beide Richtungen.

Ein Pfad oder Weg ist eine Folge von Knoten, die durch Kanten verbunden sind (z.B. München-Nürnberg-Würzburg). Ein einfacher Pfad wiederholt keinen Knoten. Ein Zyklus ist ein besonderer Pfad, der am Startknoten endet. In einem vollständigen Graph ist jeder Knoten direkt mit jedem anderen verbunden.

💡 Praxistipp: Die Eulerbedingung hilft dir zu erkennen, ob ein Graph einen Euler-Weg hat: Von jedem Knoten, außer maximal zwei, muss eine gerade Anzahl von Kanten weggehen!

Die Adjazenzmatrix ist eine wichtige Darstellungsform für Graphen. Sie zeigt in einer n×n-Tabelle, welche Knoten direkt miteinander verbunden sind. Bei ungerichteten Graphen ist diese Matrix symmetrisch zur Hauptdiagonale. Die Adjazenzliste ist eine alternative Darstellung, die besonders bei großen, dünn besetzten Graphen Vorteile bietet.