next up previous
Next: About this document ...

Algorithmische Topologie

Lektion 2. THEORIE DER NORMALEN FL¨ACHEN.
2.1. Normale Flächen in triangulierten 3-Mannigfaltigkeiten.

Sei $M$ eine 3-Mannigfaltigkeit mit einer Triangulation $T$.

Definition. Eine Fläche $F\subset M$ heißt normal, wenn das folgende gilt:

  1. Der Schnitt von $F$ mit jedem Tetraeder $\Delta^3$ besteht aus Kresscheiben. Diese Kreisscheiben heißen elementar;
  2. Die Randkurve jeder Elementarscheibe ist eine normale Kurve in $\partial \Delta^3$ ;
  3. Die Randkurve jeder Elementarscheibe schneidet jede Kante von $\Delta^3$ höchstens in einem Punkt.

Es ist leicht zu zeigen, daß  es in jedem Tetraeder genau sieben Typen von zulässigen Elementarscheiben gibt: vier Dreiecke, die Eckpunkte des Tetraeders abschneiden, und drei Vierecke, siehe Figure 2.

Figure: Elementare Kreisscheiben
\begin{figure}\centering\unitlength=0.12pt
\begin{picture}(2000,1000)
\put(0,1000){\special{em:graph seven.pcx}}
\end{picture}\end{figure}

Seien $T_1, T_2, \ldots , T_n$ die Scheibentypen in allen Tetraedern, und $x_1, x_2, \ldots , x_n$ die entsprechende Variablen. Betrachten wir ein Dreieck $\Delta^2$, das zwei Tetraeder $\Delta^3_1$, $\Delta^3_2$ der Triangulation trennt. Wählen wir zwei Kanten $K_1, K_2$ von $\Delta^2$.

Dann schreiben wir die Gleichung

\begin{displaymath}x_{i}+x_{j} =x_{k}+x_{l}.\end{displaymath}

Hier sind $T_{i}, T_{j} $ und $T_{k},T_{l} $ die Scheibentypen für $\Delta^3_1$ und $\Delta^3_2$, deren Randkurven von $K_1$ zu $K_2$ im Inneren von $\Delta^2$ gehen. Es ist offensichtlich, daß jede normale Fläche eine nicht-negative ganzzahlege Lösung des so entstandenen normalen System bestimmt. Die umgekehrte Behauptung ist falsch, da sich schneiden können, so der Schnitt von zwei verschiedenen Vierecken nicht beseitigt werden kann. Eine zulässige Lösung darf nicht solche Paare mit positiven Koeffizienten enthalten.

Satz 2.1. Es existiert eine natürliche Bijektion zwischen normalenFlächen und zulässigen Lösungen.

Genau wie in der Normalkurventheorie, haben die Lösungen des normalen Gleichungsystems eine endliche Basis. Fundamentale Flächen, die zulässigen Basislösungen entsprechen, bilden eine geometrische Basis für alle normalen Flächen. Die Umschaltung besteht darin, daß wir zwei Flächen entlang alle Doppelkurven aufschneiden und dann zusammenkleben, so daß die neue Fläche normal wird. Es folgt, daß  man jede normale Fläche aus fundamentalen Flächen durch aufeinanderfolgende Umschaltungen bekommen kann.

2.2. Anwendungen

ALLGEMEINES SCHEMA F¨UR LSOSUNG ALGORITHMISCHEN PROBLEME.

Schritt 1. Wir ersetzen das gegebene Problem durch ein Problem, das Flächen in Mannigfaltigkeiten betrifft. Eine Standardvariante: ob $M$ eine Fläche enthält, die eine spezielle Eingeschaft $E$ hat. Solche Flächen werden interessant genannt.

Schritt 2. Wir beweisen, daß  wenn $M$ eine interessante Fläche enthält, dann man eine interessante Fläche unter normalen Flächen finden kann.

Schritt 3. Wir zeigen, daß  eine interessante Fläche unter fundamentalen Flächen gefunden werden kann.

Schritt 4. Man muß  auch einen Algorithmus konstruieren, der entscheidet, ob eine gegebene Fläche die Eigenschaft $E$ besitzt.

Wir beschreiben jetzt ein Beispiel, wie das Schema angewandt werden kann.

Satz 2.2. Es exitiert ein Algorithmus zur Erkennung des trivialen Knoten.

Beweis. Schritt 1. Sei $K$ einen Knoten in $S^3$. Bezeichnen wir mit $C(K)$ seinen Außenraum. In anderen Worten, $C(K)=S^3\setminus $ Int $N(K)$, wo $N(K)$ eine offene reguläre Umgebung von $K$ ist. Der Vollring $N(K)$ hat einen Meridian and einen Längskreis, der Null in der Homologiegruppe $H_1(C(K);Z)$ bestimmt. Kleben wir zu $C(K)$ eine Platte (einen Henkel $H=D^2\times I$ von Index 2) entlang des Längskreises. Die bekommene Mannifaltigkeit wird mit $M$ bezeichnet. Sei $T$ eine Triangulation von $M$, so daß  eine Strecke $I_0=\{\ast \}\times I\subset H$ als eine Kante von $T$ dient. Wir sagen, daß  eine geschlossene Fläche $S\subset M$ interessant ist, wenn $S$ zur 2-Sphäre homöomorph ist und mit $I_0$ genau einen gemeinsamen Punkt hat.

Behauptung: $K$ ist trivial dann und nur dann, wenn $M$ eine interessante Fläche enthält.

Damit ist das Trivialitätsproblem für Knoten zu einem Standardproblem über Flächen reduziert.

Schritt 2. Sei $S$ eine interessante Sphäre in $M$. Es ist nicht schwierig, $S$ so deformieren, daß nachher $S$ alle Eigenschaften einer normalen Fläche besitzt, außer einem: der Schnitt von $S$ mit Dreiecken kann kleine Kreisen enthalten. Sei $C$ ein solchen Kreis. Dann schneiden wir $S$ längs dieses Kreises auf und füllen die entstandene Löcher mit zwei Kreisscheiben . Die Prozedur gibt uns zwei Sphären, unter denen genau eine interessant ist. Man muß  bemerken, daß  die neue interessante Sphäre einfacher ist. (Wir messen die Kompliziertheit der Sphäre mit dem Kantengrad, d.h. mit der Anzahl der Punkte in dem Durchschnitt der Sphäre mit allen Kanten). Dieses Verfahren fortsetzend, bekommen wir schließlich eine normale interessante Sphäre.

Schritt 3. Nehmen wir an, daß die normale Sphäre $S$ nicht fundamental ist. Dann kann man $S$ in der Form $S=F_1+F_2$ darstellen. Wir können annehmen, daß diese Darstellung die sparsamste ist, d. h. $F_1\cap F_2$ besteht aus der minimalen möglichen Zahl von Doppelkreisen . Dann gilt:

  1. $F_1$ und $ F_2$ sind zusammenhängend;
  2. Jeder Doppelkreis mindestens eine Fläche nicht auf zwei Teile zerlegt.
(Sonst kann man die Flächen längst einigen Doppelkreise umschalten und eine sparsamere Darstellung bekommen). Da die Euler Charakteristik additiv ist (d.h. $\chi(F_1+F_2)=\chi(F_1)+\chi(F_2)$), es gibt die einzige Möglichkeit $\chi(F_1+F_2)=\chi(S^2)=2$ zu bekommen: $F_1, F_2$ sind eine Sphäre und ein Torus. Nur eine von beiden Flächen (sei $F_1$) schneidet $I_0$.

FALL 1. $F_1$ ist eine Sphäre. Dann sind wir zufrieden, da diese Sphäre interessant und einfacher ist.

FALL 2. $F_1$ ist ein Torus, $ F_2$ ist eine nicht interessante Sphäre. Die Doppelkurven aus $F_1\cap F_2$ sind auf $F_1$ nicht trivial, folglich parallel. Dann teilen sie $F_1$ in Kreisringe, unter denen nur ein Kreisring $A$ den einzigen Schnittpunkt $F_1\cap I_0$ enthält. Der Rand $\partial A$ besteht aus zwei Kreisen $C_1, C_2$, die zwei disjunkte Kreisscheiben $D_1, D_2$ auf der Sphäre $ F_2$ beranden. Dann kann man aus $A, C_1, C_2$ eine neue interessante Sphäre $S'=A\cup C_1\cup C_2$ zusammenstellen. Sicherlich ist $S'$ einfacher als $S$.

Dieses Verfahren wird schließlich mit einer fundamentalen normalen Sphäre beendet.

Schritt 4 ist offensichtlich.




next up previous
Next: About this document ...
WWW Administrator 2001-10-30