Algorithmische Topologie

Lektion 1. THEORIE DER NORMALEN FL¨ACHEN.

Der Gegenstand der Algorithmischen Topologie ist die Konstruktion von Algorithmen, die verschiedene geometrische Probleme lösen.

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 $M$ zu verstehen, besteht darin, die Menge von "interessanten" Flächen, die in $M$ 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 $M$ eine Fläche mit einer Triangulation $T$. Eine einfach geschlossene Kurve $C\subset M$ heißt normal (bezüglich $T$), wenn das folgende gilt:

1. $C$ ist in allgemeiner Lage bezüglich $T$ ($C$ geht nicht durch die Eckpunkte und schneidet die Kanten transversal);
2. Der Schnitt von $C$ mit jedem Dreieck von $T$ besteht aus Bögen, so daß jeder Bögen zwei verschiedene Kanten verbindet (keine geschlossene Komponenten, keine Rückkehrungen).

Bezeichnen wir mit ${\cal N}$ die Menge aller normalen (nicht unbedingt zusammenhängenden) Kurven in $M$. Dann gilt:

1. ${\cal N}$ ist informativ (jede nicht-triviale Kurve ist zu einer normalen Kurve isotop);
2. ${\cal N}$ läßt eine offenbare alogorithmische Beschreibung zu.

Stellen wir jedem Winkel jedes Dreiecks der Triangulation einen Buchstaben $x_i$ gegenüber, und für jede Kante schreiben wir die Gleichung

$$x_i+x_j=x_k+x_m,$$

siehe Figure 1.

Figure: Typische Gleichung

Die Menge aller ganzzahligen nicht-negativen Lösungen des so entstandenen Gleichungsystems $S$ von homogenen linearen Gleichungen wird mit ${\cal L}$ bezeichnet.

Satz 1. Es existiert eine natürliche Bijektion zwischen ${\cal N}$ und ${\cal L}$.

Beweis. Wenn $C$ eine gegebene Kurve ist, dann nehmen wir als $x_i$ die Anzahl der entsprechenden Bogen in dem Schnitt von $C$ 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 ${\cal U}$ ein System von homogenen linearen Ungleichungen mit ganzzahligen Koeffizienten. Eine ganzzahlige nicht-negative Lösung zu ${\cal U}$ ist fundamental, falls sie nicht als eine nicht-triviale Summe ähnlicher Lösungen dargestellt werden kann.

Satz 2. Für jedes ${\cal U}$ ist die Menge von fundamentalen Lösungen endlich und läßt sich algorithmisch konstruieren.

Beweis. Sei $\sigma^{n-1}$ der Simplex in $R^n$ mit Eckpunkten

$(1,0,\ldots, 0), (0,1,\ldots, 0), \ldots, (0,0,\ldots, 1)$. Bezeichnen wir mit $L$ die Hyperebene, die $\sigma^{n-1}$ enthält, und mit ${\cal L}$ die Menge von allen rationellen Lösungen zu ${\cal U}$. Der konvexe Polyheder $P={\cal L}\cap L$ ist begrenzt, weil er in $\sigma^{n-1}$ liegt. Wir können ${\cal L}$ mit dem unendlichen Kegel über $P$ identifizieren, siehe Figire 2.

Figure: Die Lösungsraum ist einen Kegel über $P$

Sei $(\bar{v}_1,\bar{v}_2,\ldots , \bar{v}_N)$ die Eckpunkten von $P$. Sie haben rationellen Koordinaten. Multiplizierend die Vektoren $\bar{v}_j$ bei ganzen Zahlen $k_j>0$, bekommen wir die Menge $\{ \bar{V}_j=k_j\bar{v}_j, 1\leq j\leq N, \}$ von so-genannten Kantenlösungen. Die Kantenlösungen sind fundamental.

Bemerken wir, daß  jeder Punkt von $P$ in einem Dreieck mit Eckpunkten $\bar{v}_i, \bar{v}_j, \bar{v}_k$ liegt, wobei $1\leq i,j,k\leq N$ ist. Es folgt daß  jede ganzzahlige nicht-negative Lösung $\bar{x}$, die in dem Kegel über dem Dreieck liegt, läßt sich als eine lineare Kombination $\bar{x}=\alpha_i \bar{V_i}+\alpha_j \bar{V_j}+\alpha_k \bar{V_k}$ darstellen, wobei die Koeffizienten $\alpha_i,\alpha_j,\alpha_k$ nicht negative sind. Falls einer von der Koeffizienten (sei $\alpha_i$) größer als 1 ist, dann kann man $\bar{x}$ in die Form $\bar{x}=(\bar{x}-\bar{V}_i) +\bar{V}_i$ darstellen, wobei $(\bar{x}-\bar{V}_i)$ wieder eine ganzzahlige nicht-negative Lösung ist. Daraus folgt, daß  $\bar{x}$ nicht fundamental ist. Da die Menge der linearen Kombinationen $\bar{x}=\alpha_i \bar{V_i}+\alpha_j \bar{V_j}+\alpha_k \bar{V_k}, 0\leq \alpha_i,\alpha_j,\alpha_k\leq 1$, 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.

Figure: Fundamentale Lösungen sind als dicke Punkte gezeigt

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.