Graphentheorie

Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander.

Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Verwandtschaftsbeziehungen, Computernetze, elektrische Schaltungen, Versorgungsnetze oder chemische Moleküle). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Es verbleiben jedoch viele allgemeingültige Graphen-Eigenschaften, die bereits auf dieser Abstraktionsstufe untersucht werden können und sich in allgemeingültigen Aussagen (Sätze der Graphentheorie) wiederfinden.^[1] Ein Beispiel hierfür ist das Handschlaglemma, wonach die Summe der Knotengrade in einem Graphen stets gerade ist (in der nebenstehenden Abbildung: 14).

Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Insbesondere lassen sich viele Aufgaben der kombinatorischen Optimierung in der Sprache der Graphentheorie formulieren und umgekehrt graphentheoretische Probleme als lineare ganzzahlige Optimierungsprobleme modellieren.^[2] Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie. Graphen werden insbesondere durch die Datenstrukturen Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert.

1. ↑ Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3., aktualisierte Auflage. München, ISBN 978-3-446-46052-2, S. 1. 
2. ↑ Bernhard Korte, Jens Vygen: Combinatorial Optimization. In: Algorithms and Combinatorics. 2002, ISSN 0937-5511, doi:10.1007/978-3-662-21711-5 (uni-muenchen.de [PDF; abgerufen am 16. Januar 2024]).