Steiners Verhältnis
Eine geniale Theorie zeigt, daß die Möglichkeiten, durch Optimierung Material zu sparen, manchmal begrenzt sind – so sehr, daß häufig das Optimieren den Aufwand nicht lohnt.
Aber die kürzeste Verbindung zwischen zwei Punkten ist doch eine Gerade!" schrie Friedrich Spanner aufgebracht.
"Das bestreite ich ja nicht", entgegnete Franz Steiner ruhig. "Ich meine nur, daß wir nicht unbedingt alle Knoten in die Städte legen müssen, die vernetzt werden sollen."
"Und wo wollen Sie dann all diese Extrapunkte hinlegen?"
"Das ist genau meine Frage."
Die Oberpfälzer Infobahn GmbH, eine neue Firma mit großen Plänen und knapper Kapitaldecke, wollte Vohenstrauß, Tirschenreuth und Pressath durch Glasfaserkabel verbinden. Nur konnten sich die beiden Chefs nicht über die Strategie einigen. Spanner meinte, es sei am besten, eine Stadt herauszugreifen und von dort zu den beiden anderen Kabel in gerader Linie zu verlegen.
"Welche Stadt?" fragte Steiner.
"Das hängt von den Entfernungen ab, ist aber gar nicht schwer zu entscheiden. Von dem Dreieck aus den drei Städten streiche man die längste Seite weg und lege Kabel entlang den beiden anderen Seiten."
"Klingt vernünftig. Aber..." Steiner hatte die vage Vorstellung, die Gesamtlänge würde sich noch verkürzen lassen, wenn man eine vierte Stadt mit in das Netz aufnähme. Das ist auf den ersten Blick zwar nicht besonders einleuchtend; wenn er aber recht hätte, wo müßte der zusätzliche Knotenpunkt liegen, und wieviel Kabellänge könnte man damit einsparen?
Vohenstrauß, Tirschenreuth und Pressath sind jeweils ungefähr 30 Kilometer voneinander entfernt (Bild 1). Spanners Netzwerk wäre – unter Weglassung der Direktverbindung Pressath-Vohenstrauß – 57 Kilometer lang. Wie steht es nun mit Steiners windiger Idee? Ungefähr in der Mitte des Dreiecks, am Ufer des Flüßchens Waldnaab, liegt eine Ansiedlung mit vielsagendem Namen ungefähr 15 bis 18 Kilometer von jeder der drei Städte entfernt.
"Schauen Sie sich das an, Herr Spanner. Mitteldorf. Wenn wir einen Knotenpunkt dorthin legen und Leitungen zu allen drei Städten..."
"Quatsch! Mehr Knoten heißt mehr Kabel."
"Eben nicht. Kann man ausrechnen. Eine Leitung von Mitteldorf aus zu jeder Stadt macht zusammen – Moment, haben wir gleich – 52,2 statt 57 Kilometer nach Ihrer Methode. Das sind achteinhalb Prozent weniger."
Spanner schaute ungläubig auf die Karte, kratzte sich am Kopf und gab sich schließlich geschlagen. Das Faxgerät piepte, aber sie achteten nicht darauf.
"Ich überlege gerade: Man kann sich die gleiche Frage für jede beliebige Menge von Städten stellen", fuhr Steiner fort. "Wie lang ist das kürzeste Netzwerk, das jede mit jeder verbindet, wenn alle Knotenpunkte in den gegebenen Städten liegen müssen? Und wie sieht das kürzeste Netzwerk aus, wenn wir uns die Freiheit nehmen, irgendwo weitere Knoten anzulegen?"
Spanner hatte etwas Entscheidendes begriffen: "Wenn man mehr Möglichkeiten zur Auswahl hat, kann das Optimum nur besser werden. Schließlich sind wir ja nicht gezwungen, neue Knoten einzuführen. Aber um wieviel besser?"
Während Steiner entschwand, um in einer Datenbank nach einer Antwort zu suchen, rief Spanner nach der Sekretärin, weil sich die eingehenden Faxe zu türmen begannen. Es wäre ihm nicht eingefallen, sie selber zu sortieren.
Einige Stunden später kam Steiner zurück. "Wir sind nicht die ersten, die sich diese Fragen stellen. Es gibt sogar eine große Menge Literatur dazu. Edgar Gilbert und Henry Pollak von den AT&T Bell-Laboratorien in Murray Hill (New Jersey) haben 1968 folgende Vermutung aufgestellt: Einerlei, wie die Städte liegen, kann man durch Einführen zusätzlicher Knotenpunkte nicht mehr als 13,4 Prozent der Kabellänge einsparen. Man spricht von der Vermutung zum Steinerschen Verhältnis oder auch von der Steiner ratio conjecture."
"Was haben Sie für ein Verhältnis?"
"Nicht ich. Jakob Steiner." Nach einem kurzen Blick auf die mitgebrachten Zettel: "Mathematiker aus Bern. 1796 bis 1863."
"Und warum sagt man nicht Gilbert-Pollak-Vermutung?"
"Das liegt an den Zuschreibungsgewohnheiten der Mathematiker."
"Und die besagen?"
"Benenne die Idee nach einem bereits verstorbenen Menschen, der sie zwar nicht hatte, aber irgendwie vage damit befaßt war. Jedenfalls ist es keine Vermutung mehr, sondern der Satz vom Steinerschen Verhältnis..."
"Satz von Gilbert-Pollak", beharrte Spanner.
"Eigentlich wäre ,Satz von Du und Hwang' die korrekte Bezeichnung. Denn 1991, nach 23 Jahren unnachgiebiger, aber weitgehend unergiebiger Anstrengungen haben Ding-Zhu Du von der Universität Princeton und Frank Hwang von den Bell-Laboratorien die Vermutung bewiesen" (Spektrum der Wissenschaft, November 1991, Seite 26).
Spanner stieg gedankenverloren über den Haufen Faxpapier und holte sich eine Tasse längst erkalteten Kaffees. "Ach so. AT&T ist eine Telephongesellschaft, da ist das naheliegend."
Gerüste und Steiner-Bäume
"Dazu gibt es eine interessante Geschichte, aber die erzähle ich Ihnen später. Wichtig ist zunächst, wie ich bei meiner Recherche gelernt habe, die Sache mathematisch sauber zu formulieren. Wir denken uns die zu verbindenden Städte als Punkte in einer Ebene und die Verbindungskabel als gerade Strecken. Ob wir nun neue Verbindungsknoten einführen oder nicht – unser Netz aus Punkten und Strecken muß auf jeden Fall einen sogenannten Baum bilden. Das heißt, es darf kein geschlossener Rundweg entstehen; denn sonst gäbe es ja zwei verschiedene Verbindungen zwischen zwei Punkten, und von denen könnte man eine weglassen. Ein solches Netz, das jede Stadt mit jeder auf genau eine Weise verbindet, ohne neue Knotenpunkte einzuführen, heißt aufspannender Baum oder auch Gerüst. Es gibt viele mögliche Gerüste zu einer gegebenen Menge von Städten, aber im Prinzip könnte man sie alle auflisten und unter ihnen das kürzeste auswählen."
Nehmen wir beispielsweise Ahlen, Bochum, Coesfeld und Dülmen. Bild 2 zeigt einige Gerüste und deren Gesamtlängen. Bei dem kürzesten gehen von einem Verzweigungspunkt in Dülmen Verbindungen zu den anderen drei Städten aus. Für Ahaus, Bergkamen, Coesfeld und Dülmen hingegen, die annähernd auf einer Geraden liegen, besteht der kürzeste aufspannende Baum aus der Verbindung Ahaus-Coesfeld-Dülmen-Bergkamen, in dieser Reihenfolge, und hat keinen Verzweigungspunkt.
Das Problem ist viel komplizierter, wenn die Kabel sich auch außerhalb der Städte verzweigen dürfen. Das kürzeste Netzwerk zwischen Tirschenreuth, Pressath und Vohenstrauß beispielsweise ist dasjenige, das alle drei mit Mitteldorf – genauer: einem namenlosen Punkt zwischen Mitteldorf, Kotzenbach und Rotzendorf – verbindet. Im allgemeinen muß das kürzeste Netzwerk, das eine gegebene Menge von Städten verbindet, ebenfalls ein Baum sein, der sogenannte Steiner-Baum (Spektrum der Wissenschaft, März 1989, Seite 78).
"Wer war eigentlich dieser Steiner?" unterbrach Spanner, als sein Kollege mit der Erklärung so weit gekommen war. "Was hat er mit dem Problem zu tun?"
"Nicht allzuviel", erwiderte Steiner. "Er hat halt 1837 das Problem für drei Städte gelöst. Richard Courant und Herbert Robbins haben seinen Namen 1941 in ihrem klassischen populären Buch ,Was ist Mathematik?' mit dem Problem verbunden. Weder diese beiden noch Steiner scheinen gewußt zu haben, daß Evangelista Torricelli" - wieder ein Blick auf den Spickzettel – "1608 bis 1647, und Bonaventura Cavalieri, 1598 bis 1647, ihm schon 1640 zuvorgekommen waren." Steiner wußte, daß Spanner ein Faible für historische Daten hatte.
"War dieser Torricelli nicht der Typ, der das Barometer erfunden hat?"
"Eben der. Und Cavalieri war einer der Urväter der modernen Infinitesimalrechnung. Die beiden haben zwei Fälle unterschieden. Wenn einer der Winkel des Dreiecks 120 Grad oder größer ist, besteht das kürzeste Netzwerk aus den zwei Dreiecksseiten, die dieser stumpfen Ecke anliegen. Im anderen Falle besteht es aus den drei Strecken, die von den drei Städten aus zu dem sogenannten Steiner-Punkt laufen. Das ist der eindeutig bestimmte Punkt, an dem sich diese drei Verbindungen unter einem Winkel von jeweils 120 Grad treffen" (Bild 3).
Steiner fuhr fort, seinen Namensvetter zu preisen. "Auch bei mehr als drei Städten müssen sich die Kanten des Steiner-Baumes in jedem neu eingeführten Knoten unter 120 Grad treffen. Das ist nicht besonders schwer zu sehen und wurde ebenfalls von Steiner bewiesen. Wesentlich schwerer ist es, einen solchen Baum tatsächlich zu finden. Die ersten ernsthaften Untersuchungen dazu stammen von Milos Kössler und Vojtech Jarník aus dem Jahre 1934."
"Es leuchtet ein, daß das nicht einfach ist", erwiderte Spanner. "Man muß ja ei-ne ungeheure Menge denkbarer Steiner-Punkte in Betracht ziehen."
"Sie haben es erfaßt. Stellen Sie sich zum Beispiel sechs Städte in den Ecken zweier benachbarter Quadrate vor. Einen Steiner-Baum für ein einzelnes Quadrat zu finden ist nicht schwer. Dann bleibt noch, die zwei verbleibenden Städte des anderen Quadrats anzuhängen; das ist auch nicht schwer" (Bild 4 a).
"Aha. Ist das nun ein Steiner-Baum?"
"Ja."
"Also ist es das optimale Netzwerk?"
"Nein."
"Aber Sie haben mir doch gerade gesagt, daß die kürzesten Netzwerke Steiner-Bäume heißen."
"Diese Mathematiker verallgemeinern manchmal so schnell, daß man kaum mitkommt. Man nennt ein Netz einen Steiner-Baum, wenn jeder neu eingeführte Knoten aus drei Kanten mit Winkeln von 120 Grad besteht. Also: Jeder optimale Baum ist ein Steiner-Baum, aber nicht umgekehrt."
"Aha. Und was Sie da gezeichnet haben, ist der optimale Steiner-Baum?" (Bild 4b)
"Ein optimaler Steiner-Baum."
"Also der mit der kürzesten Länge?"
"Einer von zwei gleich langen optimalen. Den anderen bekommen Sie durch Spiegelung an der horizontalen Mittellinie."
"Spitzfindigkeiten."
"Jedenfalls sieht man an dem Beispiel, daß man kürzeste Steiner-Bäume nicht schrittweise, eine Stadt nach der anderen einbeziehend, konstruieren kann."
"Das sehe ich ein", sagte Spanner, rief zwischendurch abermals barsch – und erfolglos – nach der Sekretärin und fragte weiter: "Was haben Gilbert und Pollak nun getan?"
"Sie fragten sich, was die Länge eines minimalen aufspannenden Baums und die eines optimalen Steiner-Baums miteinander zu tun haben. Nennen wir die erste Größe die Gerüstlänge der Städte und die zweite die Steiner-Länge. Nun ist jedes Gerüst auch ein Steiner-Baum."
"Wieso? Ich denke, Steiner-Baum ist, wenn in jedem neu eingeführten Knoten..."
"Wir führen aber keine neuen Knoten ein."
"Also ist die Bedingung trivialerweise erfüllt?"
"Richtig."
"Was soll dann diese Spielerei mit Worten?"
"Ganz einfach: Für jede gegebene Menge von Städten ist die Gerüstlänge stets größer oder gleich der Steiner-Länge; denn die ist definiert als die Länge des kürzesten unter allen Steiner-Bäumen. Die Frage ist: Wie groß kann der Unterschied sein?"
Der klassische Steiner-Baum
"Na schön", erwiderte Spanner, "nehmen wir als Beispiel zum Probieren ein gleichseitiges Dreieck mit Seitenlänge 1. Dann beträgt die Gerüstlänge 2 und die Steiner-Länge
Leichte und schwere Probleme
"Bleiben wir mal bei der Theorie", sagte Steiner. "Nehmen wir an, ein Problem ist gegeben, in das irgendeine Anzahl n von Objekten (bei uns Städten) eingeht. Wie stark wächst dann die Laufzeit eines Algorithmus zur Lösung des Problems mit wachsendem n an? Wenn diese Zeit nicht schneller wächst als ein festes Vielfaches einer festen Potenz von n, sagen wir
Der Beweis
"Für das gleichseitige Dreieck, mit dem alles begann, gibt es eine recht natürliche Lösung. Das legt nahe, daß es einen einfachen Beweis der Vermutung geben müßte. Aber wenn es den gibt, dann hat ihn bisher niemand gefunden. Die Einfachheit des Spezialfalls ist also irreführend. Selbst der Beweis von Du und Hwang ist ziemlich trickreich. Wer es für kleine Anzahlen mit direkten Methoden versucht, versinkt in einem Wust von Formeln. Gilbert und Pollak hatten für ihre Vermutung zahlreiche Hinweise; sie vermochten zum Beispiel zu zeigen, daß das Steiner-Verhältnis stets mindestens 0,5 beträgt. Um 1990 hatten diverse Leute durch heroische Rechnungen die Vermutung für Netze mit 4, 5 und 6 Städten bestätigt. Für beliebig viele Städte war die untere Abschätzung für das Verhältnis nacheinander von 0,5 auf 0,57, 0,74 und schließlich auf 0,8 angehoben worden. Vor einigen Jahren verbesserten Graham und Fang Chung von den Bell-Laboratorien die Schranke auf 0,824. Die dazu erforderliche Rechnung nannten sie selber ,fürchterlich'. Es war deutlich geworden, daß dies der falsche Weg war." "Sehr hilfreich", meinte Spanner in einem Anflug von Sarkasmus. "Lästern Sie nicht. Das war vielleicht hilfreicher, als Sie denken. Dadurch wurde die Aufmerksamkeit auf abstraktere Methoden gelenkt. Weitere Fortschritte waren nur zu erwarten, wenn man die fürchterlichen Rechnungen vereinfachen könnte. Es gelang Du und Hwang, sie vollständig zu umgehen. Die Grundfrage ist: Wie bringt man gleichseitige Dreiecke ins Spiel? Für die weiß man alles, aber von da bis zu einer allgemeinen Anordnung von Städten, die derselben Schranke genügen soll, klafft eine Riesenlücke. Wie kann man dieses Niemandsland durchqueren?" "Wollen wir darauf nicht lieber erst eingehen, wenn alle diese Faxe beantwortet sind?" "Ach, warten Sie noch einen Moment. Dies hier ist wirklich unglaublich faszinierend. Es gibt eine Art Zwischenstation im Niemandsland. Stellen Sie sich die Ebene eingeteilt in lauter gleichseitige Dreiecke vor, also ein reguläres Dreiecksgitter. Städte setzen wir nur in die Ecken dieser Dreiecke. Es stellt sich heraus, daß dann als Kandidaten für Steiner-Punkte lediglich die Mittelpunkte der Dreiecke in Frage kommen. Kurz gesagt, wir haben jetzt viel mehr Überblick, nicht nur über die Rechnung, sondern auch über die theoretische Untersuchung" (Bild 6). "Wundervoll. Aber normalerweise liegen Städte nicht auf den Ecken eines Dreiecksgitters." "Doch. Jedenfalls die, auf die es wirklich ankommt. Das haben Du und Hwang gezeigt. Nehmen wir an, die Vermutung wäre falsch. Dann muß es ein Gegenbeispiel geben: irgendeine Anordnung von Städten, für die das Verhältnis kleiner als
Literaturhinweise
- Was ist Mathematik? Von Richard Courant und Herbert Robbins. 4. Auflage. Springer, Heidelberg 1992.
– Mathemagische Tricks. Von Martin Gardner. Vieweg, Braunschweig 1981.
– Steiner Minimal Trees. Von Edgar N. Gilbert und Henry O. Pollak in: SIAM Journal of Applied Mathematics, Band 16, Seiten 1 bis 29, 1968.
– Companion to Concrete Mathematics. Von Z. A. Melzak. Wiley, New York 1973.
– Studentenfutter. 100 Aufgaben für Mathe-Feinschmecker. Von Hugo Steinhaus. Urania, Leipzig 1991.
– Steiner Problems in Networks: A Survey. Von Pawel Winter in: Networks, Band 17, Seiten 129 bis 167, 1987.
Aus: Spektrum der Wissenschaft 4 / 1995, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH
Schreiben Sie uns!
Beitrag schreiben