Warum sind Algorithmen nützlich?
1. Weil es nützlich sein würde, im voraus zu wissen, ob das Problem algorithmisch lösbar ist;
2. Da es immer eine Hoffnung gibt, daß der Algorithmus (falls er existiert) auf den Computer realisieren läßt;
3. (Die Hauptantwort). Die Aufgabe, ein Problem algorithmisch zu lösen,
ist ein gutes Ziel; versuchend es zu erreichen,
findet man immer tiefe Ergebnisse.
Wir werden verschiedene 3-dimensionale Probleme untersuchen vom algorithmischen Gesichtspunkt.
Eine richtige Methode, die Struktur einer 3-Mannigfaltigkeit
zu verstehen,
besteht darin, die Menge von "interessanten" Flächen, die in
liegen,
zu untersuchen.
Die Theorie der normalen Flächen
von W. Haken ist für diesen Zweck erfunden (1961).
Der Begriff der interessanten Fläche ändert
sich von Fall zu Fall.
Um die Sache zu
vereinfachen, steigen wir eine Dimension herab und werden Kurven
auf Flächen betrachten. Alle wesentliche Einsichten sind schon auf dieser
Stufe vorhanden.
1.1 Theorie der normalen Kurven.
Sei
eine Fläche mit einer Triangulation
.
Eine einfach geschlossene Kurve
heißt normal (bezüglich
), wenn das folgende gilt:
Bezeichnen wir mit
die Menge aller normalen (nicht unbedingt
zusammenhängenden) Kurven in
.
Dann gilt:
Stellen wir jedem Winkel jedes Dreiecks der Triangulation einen Buchstaben
gegenüber, und für jede Kante schreiben wir die Gleichung
Die Menge aller ganzzahligen nicht-negativen Lösungen
des so entstandenen Gleichungsystems
von homogenen linearen Gleichungen wird mit
bezeichnet.
Satz 1. Es existiert eine natürliche Bijektion zwischen
und
.
Beweis. Wenn
eine gegebene Kurve ist, dann nehmen wir als
die Anzahl der entsprechenden Bogen in dem Schnitt von
mit
dem entsprechenden Dreieck.
Dieser Satz hilft uns zu beweisen, daß die Kleinische Flasche genau 4 einfach geschlossene nicht-triviale Kurven enthält. Er gibt schon eine offenbare Beschreibung der normalen Kurven, aber wir wollen mehr.
Sei
ein System von homogenen linearen Ungleichungen mit ganzzahligen
Koeffizienten.
Eine ganzzahlige nicht-negative Lösung zu
ist
fundamental, falls sie nicht
als eine nicht-triviale Summe ähnlicher Lösungen dargestellt
werden kann.
Satz 2. Für jedes
ist
die Menge von fundamentalen Lösungen endlich und läßt
sich algorithmisch konstruieren.
Beweis.
Sei
der Simplex
in
mit Eckpunkten
.
Bezeichnen wir
mit
die Hyperebene,
die
enthält, und mit
die Menge von
allen rationellen Lösungen zu
.
Der konvexe Polyheder
ist begrenzt, weil
er in
liegt. Wir können
mit dem
unendlichen Kegel über
identifizieren, siehe Figire 2.
Sei
die
Eckpunkten von
. Sie haben rationellen Koordinaten.
Multiplizierend die Vektoren
bei ganzen Zahlen
, bekommen wir
die Menge
von so-genannten
Kantenlösungen. Die Kantenlösungen sind fundamental.
Bemerken wir, daß jeder Punkt von
in einem Dreieck mit Eckpunkten
liegt, wobei
ist.
Es folgt daß jede ganzzahlige nicht-negative Lösung
, die in dem Kegel über dem Dreieck liegt, läßt sich als
eine lineare Kombination
darstellen, wobei
die
Koeffizienten
nicht negative sind. Falls einer
von der Koeffizienten (sei
) größer als 1 ist, dann
kann man
in die Form
darstellen, wobei
wieder eine ganzzahlige nicht-negative Lösung ist. Daraus folgt, daß
nicht fundamental ist. Da die Menge der linearen Kombinationen
, kompakt ist, endet sich
der Beweis mit der Bemerkung, daß jede
kompakte Menge nur endlich viele
ganzzahlige Punken enthält. Siehe ein Beispiel auf Figure 3.
Da man jede Gleichung durch zwei entgegengesetzte Ungleichungen ersetzen kann, ist die Menge der fundamentalen Kurven endlich. Daraus folgt, daß jede normale Kurve als eine lineare Kombination (mit ganzzahligen nicht-negativen Koeffizienten) von fundamentalen Kurven dargestellt werden kann. Sogar mehr, die Summe von Kurven hat eine geometrische Interpretation: man muß in allen Doppelpunkten die reguläre Umschaltungen ausführen, so daß danach wir wieder eine normale Kurve bekommen.