Die ersten Wurzeln der Graphentheorie findet man in einer Abhandlung des Schweizer Genies Leonhard Euler aus dem Jahre 1736. Angeregt durch das bekannte Königsberger Brückenproblem stellte Euler 1736 Untersuchungen an (Eulerscher Graph), die gerade heute auch von großem praktischen Nutzen sind. Lassen wir zunächst Euler selbst zu Wort kommen.

“... 2. Das Problem, das ziemlich bekannt sein soll, war folgendes: Zu Königsberg in Preussen ist eine Insel A, genannt “der Kneiphof”, und der Fluss, der sie umfliesst, teilt sich in zwei Arme, wie dies aus der Fig. I ersichtlich ist.

Über die Arme dieses Flusses führen sieben Brücken a, b, c, d, e, f und g. Nun wurde gefragt, ob jemand seinen Spazierweg so einrichten könne, dass er jede dieser Brücken einmal und nicht mehr als einmal überschreite. Es wurde mir gesagt, dass einige diese Möglichkeit verneinen, andere daran zweifeln, dass aber niemand sie erhärte. Hieraus bildete ich mir folgendes höchst allgemeine Problem: Wie auch die Gestalt des Flusses und seine Verteilung in Arme, sowie die Anzahl der Brücken ist, zu finden, ob es möglich ist, jede Brücke genau einmal zu überschreiten oder nicht.

... 4. Meine ganze Methode beruht nun darauf, dass ich das Überschreiten der Brücken in geeigneter Weise bezeichne, wobei ich die grossen Buchstaben A, B, C, D gebrauche zur Bezeichnung der einzelnen Gebiete, welche durch den Fluss voneinander getrennt sind. Wenn also einer vom Gebiet A in das Gebiet B gelangt über die Brücke a oder b, so bezeichne ich diesen Übergang mit den Buchstaben AB, …”

Man erkennt deutlich, wie Euler hier implizit die Ecken A, B, C, D und die Kanten AB, … eines Graphen, ja sogar Multigraphen, eingeführt hat. Graphentheoretisch formuliert fragt das Königsberger Brückenproblem danach, ob in dem unten skizzierten Multigraphen KBP ein sogenannter Eulerscher Kantenzug existiert. Als Folgerung aus Eulers Untersuchungen ergibt sich schließlich, daß das Königsberger Brückenproblem keine gewünschte Lösung besitzt.

Ein weiteres fundamentales Resultat trägt ebenfalls Eulers Namen, dem wir heute einen Platz in der Theorie der planaren Graphen eingeräumt haben, nämlich die berühmte Polyederformel \begin{eqnarray}n+l=m+2,\end{eqnarray}

wobei n, l und m die Anzahl der Ecken, Flächen und Kanten eines (konvexen) Polyeders bedeuten. Diese von Euler 1750 gefundene Identität und sein berühmter Artikel über das Königsberger Brückenproblem lösten aber noch keine systematische Beschäftigung mit Graphen aus.

Der erste starke Anstoß ging dann von den sich im 19. Jahrhundert schnell entfaltenden Naturwissenschaften aus. Im Jahre 1847 erschien die grundlegende Arbeit von Gustav Robert Kirchhoff über elektrische Ströme und Spannungen in Netzwerken, deren Zweige mit Ohmschen Widerständen behaftet sind. Hier ist der Graph durch das elektrische Netzwerk unmittelbar gegeben. In Kirchhoffs Abhandlung findet man die Wurzeln der heute so bedeutungsvollen Theorie der Netzwerkflüsse, die insbesondere in den Jahren 1956 bis 1962 von L.R. Ford und D.R. Fulkerson ausgebaut wurde und sich vor allem mit Verkehrs- und Transportproblemen befaßt.

Sowohl Arthur Cayley als auch James Joseph Sylvester gelangten über die Chemie zu graphentheoretischen Strukturen. Ausgangspunkt für Cayleys Untersuchungen war die Frage nach der Anzahl isomerer Alkane gleicher Summenformel. Cayley entwickelte 1874/75 die erste sytematische Methode zur Anzahlbestimmung von Isomeren und schaffte damit die mathematische Grundlage für eine allgemeine Abzähltheorie, die 1937 durch George Pó-lya zur vollen Entfaltung gelangte. Als Bezeichnung für graphische Darstellung von Molekülen benutzte Sylvester 1878 erstmalig das Wort “Graph” im heutigen Sinne.

Die heftigsten Impulse für die Entwicklung der Graphentheorie gingen jedoch von dem berühmtberüchtigten Vierfarbenproblem aus, das Mitte des Jahrhunderts von dem Studenten Francis Guthrie aufgeworfen wurde. Es fragt danach, ob man die Länder einer Landkarte stets mit höchstens vier Farben so färben kann, daß benachbarte Länder verschiedene Farben tragen. Die mannigfachen (allerdings meist vergeblichen) Lösungsversuche dieses Problems waren die Wurzeln ganzer Teilgebiete der Graphentheorie, wie etwa der Topologische Graphentheorie, der Theorie der Eckenfärbung, Kantenfärbung und Hamiltonschen Graphen. Den kürzesten, aber immer noch langen, komplizierten und computerunterstützten, Beweis des Vier-Farben-Satzes gaben 1997 N. Robertson, D.P. Sanders, P. Seymour und R. Thomas.

Die neueren Fragestellungen nach der algorithmischen Komplexität von Entscheidungs- und kombinatorischen Optimierungsproblemen bildeten eine weitere treibende Kraft für die Graphentheorie. Diese Disziplinen haben sich in den letzten drei Jahrzehnten besonders stürmisch entwickelt, denn sie bieten hochinteressante Anwendungen in Wirtschaft, Technik und Naturwissenschaften. Insbesondere heute, in der Zeit der schnellen Rechner, hat sich die Graphentheorie immer mehr als geeigneter Rahmen für die Bereitstellung von Modellen und Methoden zur Lösung diskreter Organisationsund Optimierungsaufgaben erwiesen, und darüber hinaus liefert sie geradezu die Musterbeispiele und Standardprobleme (z. B. das Travelling Salesman Problem oder das Graphenisomorphieproblem) für wichtige Bereiche der Komplexitätstheorie. Die Problematik der Theorie der NP-Vollständigkeit (insbesondere die Frage, ob P = NP gilt oder nicht) ist sowohl für den Grundlagenforscher als auch für den Anwender von großer Bedeutung und stellt somit eine markante Schnittstelle von Theorie und Praxis dar.

Derjenige, der vielleicht die Zukunft voraussah und der – allen Widerständen und Anfeindungen zum Trotz – zum Bahnbrecher für die Graphentheorie wurde, war Dénes König mit seinem wundervollen Buch [5] aus dem Jahre 1936. In diesem ersten Lehrbuch über Graphentheorie faßte König nahezu alle am Anfang der 1930er Jahre bekannten, in verschiedenen Zeitschriften weit verstreuten Einzelresultate in seinem vorbildlich geschriebenen Werk zu einer einheitlichen Disziplin – eben der Graphentheorie – zusammen.

Weitere Informationen zu den Wurzeln der Graphentheorie findet man in dem Buch von N.L. Biggs, E.K. Lloyd und R.J. Wilson [1].

[4] Diestel, R.: Graphentheorie. Springer Berlin, 1996.

[5] König, D.: Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft M.B.H. Leipzig, 1936.

[6] Volkmann, L.: Fundamente der Graphentheorie. Springer Wien New York, 1996.