Graphentheorie: Grundlagen

Kurz: Ein Graph besteht aus Knoten (Punkten) und Kanten (Verbindungen zwischen ihnen) und beschreibt abstrakt Beziehungen zwischen Objekten. Von sozialen Netzwerken über Straßenkarten bis zu Computernetzwerken lassen sich unzählige reale Systeme als Graphen modellieren.

Genauer: Die Graphentheorie entstand im 18. Jahrhundert, als Leonhard Euler das berühmte Königsberger Brückenproblem mit abstrakten Knoten und Kanten löste.

Im Detail

• Gerichtete und ungerichtete Graphen: Bei gerichteten Graphen haben Kanten eine Richtung, etwa bei Einbahnstraßen, bei ungerichteten verbinden sie Knoten symmetrisch.
• Gewichtete Graphen: Kanten können Zahlenwerte tragen, etwa Entfernungen oder Kosten, was Optimierungsprobleme wie kürzeste Wege ermöglicht.
• Grad eines Knotens: Die Anzahl der mit einem Knoten verbundenen Kanten zeigt, wie stark dieser Knoten vernetzt ist.
• Bäume als Spezialfall: Ein Baum ist ein zusammenhängender Graph ohne Kreise und bildet die Grundlage für viele Datenstrukturen in der Informatik.
• Kürzeste-Wege-Algorithmen: Verfahren wie der Dijkstra-Algorithmus finden effizient die günstigste Route zwischen zwei Knoten in einem gewichteten Graphen.
• Reale Anwendungen: Navigationssysteme, soziale Netzwerke, Stromnetze und das Internet selbst lassen sich alle als riesige Graphen beschreiben.
• Färbungsprobleme: Das Einfärben von Knoten oder Karten so, dass benachbarte Elemente unterschiedliche Farben haben, ist ein klassisches Graphenproblem mit praktischen Anwendungen (matrizen-grundlagen).