Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03200.jsonl.gz/968

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.