Graphentheorie

Anwendungen

Wie oben erläutert, können mit Hilfe von Graphen viele Probleme modelliert werden.

Geradezu klassisch ist die Aufgabe, eine kürzeste Route zwischen zwei Orten zu finden. Sie lässt sich mit Graphen lösen, indem man das Straßennetz geeignet als kantengewichteten Graphen modelliert und in diesem mit Hilfe des Algorithmus von Dijkstra effizient ein kürzester Weg berechnet wird.

Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe Problem des Handlungsreisenden), bei der alle Orte eines Netzwerkes genau einmal besucht werden müssen. Da die Zahl der möglichen Rundreisen exponentiell mit der Zahl der Orte wächst, ist der naive Algorithmus, alle Rundreisen auszuprobieren und die kürzeste auszuwählen, für praktische Anwendungen unbrauchbar.In der Praxis wird man Orte auch mehrfach besuchen können. Dann gilt indirekt die Dreiecksungleichung, und in diesem Fall kann mit Approximationsalgorithmen gearbeitet werden, die eine Rundreise finden, die höchstens doppelt (MST-Heuristik) oder höchstens 1,5-mal (Christofides-Heuristik) so lang wie die kürzeste Rundreise ist.

Prominent ist auch das Problem, die Länder einer Landkarte mit möglichst wenig Farben so zu färben, dass aneinander angrenzende Länder nicht dieselbe Farbe erhalten. Hier wird die Landkarte ebenfalls in einen Graphen übersetzt und dann versucht, mit einem Algorithmus dieses Problem zu lösen. Ähnlich wie beim Problem des Handlungsreisenden lässt sich dieses Problem nach heutigem Wissensstand selbst mit Computern ab einer gewissen Größe der Landkarte nicht in vernünftiger Zeit exakt lösen. Das Problem, allgemeine Graphen optimal zu färben, gilt als eines der schwierigsten Probleme in der Klasse der NP-vollständigen Probleme überhaupt. Unter der Voraussetzung (siehe P-NP-Problem) ist selbst eine approximative Lösung nicht bis auf einen konstanten Faktor möglich.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Graphentheorie aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung