Graphentheorie
Die Graphentheorie ist ein Teilgebiet der Mathematik, das sich mit Graphen befasst – abstrakten Modellen aus Knoten (Ecken) und Kanten (Verbindungen). Graphen können ungerichtet oder gerichtet, schlicht oder mehrstufig, gewichtet oder ungewichtet sein. Zentrale Begriffe sind Pfad, Kreis, Baum, Konnektivität sowie Grad und Nachbarschaft der Knoten. Graphen dienen als Modelle für Netzwerke, wobei Kanten die Verbindungen zwischen Elementen darstellen.
Die Wurzeln der Graphentheorie liegen in der Königsberger Brückenproblem von Leonhard Euler im 18. Jahrhundert. Seitdem
Zu den wichtigsten Problemen gehören die Bestimmung kürzester Wege (Dijkstra, Bellman-Ford), Minimaler Spannbaum (Prim, Kruskal), maximale
Anwendungen reichen von Computer- und Kommunikationsnetzen über Verkehrs- und Logistikplanung bis hin zu Biologie, Chemie und
Die Graphentheorie verbindet rein abstrakte Ergebnisse mit praktischen Anwendungen. Viele grundlegende Probleme sind NP-vollständig oder NP-schwer;