Anwendungen der Knotentheorie

In diesem Artikel geht es darum, wie man mehr oder weniger alltägliche Probleme mithilfe der Kontentheorie beschreiben und sogar lösen kann. Wie nützlich die hier gezeigten Lösungen zu Problemen vom Schuhe schnüren über das Krawatte binden bis hin zum Bilder aufhängen ist, mag der geneigte Leser selbst entscheiden.

Knoten und Graphen

Jeder Knoten lässt sich auch als Graph darstellen. Hierfür betrachtet man den Außenbereich des Knoten, der durch die äußerste Linie abgetrennt wird und sein Inneres. Dann färbt man den Knoten schachbrettartig ein, indem man außen mit weiß beginnt und dann die einzelnen Gebiete gerade entgegengesetzt zu denjenigen auf der anderen Seite eines Strangs färbt. Dann verbindet man die Mittelpunkte, die so zu Ecken des Graphen werden, der eingefärbten Gebiete, die damit zu Ecken des Graphen werden, so, dass die Verbindungslinie stets den Punkt schneidet, an dem sich benachbarte eingefärbte Flächen treffen und erhält so die Kanten des Graphen. Schneidet die Kante des Graphen eine positive Kreuzung, d.h. eine Kreuzung, bei der der von links kommende Strang oben liegt, so wird die Kante durchgezogen. Handelt es sich um eine negative Kreuzung, bei der der von links kommende Strang unten liegt, so wird die Kante gestrichelt.

• 

  Beliebiger Knoten

• 

  Schachbrettartige Schraffierung und eingezeichnete Ecken des Graphen

• 

  Verbindung der Eckpunkte zu einem Graphen

• 

  Zugrundeliegender Graph

Umgekehrt können aus Graphen Knoten entstehen. Hierfür zeichnet man je in die Mitte der Kante ein Kreuz, das die Kante in einem Winkel von 45° schneidet. Die Enden nebeneinanderliegender Kreuze, d.h. solcher Kreuze, deren Kanten sich in einer Ecke treffen, werden verbunden. Anschließend verteilt man abwechselnd an den Kreuzen linke und rechte Kreuzungen. Auf diese Art sind einige berühmte keltische Muster entstanden.

• 

  Dreieckiger Graph

• 

  Graph mit Kreuzen

• 

  Verbundene Kreuze

• 

  Fertiger Kleeblattknoten

Die Mathematik des Krawattenbindens

Krawatten sind seit Ludwig dem XIV als modisches Accesoire bekannt und seither müssen sich die Träger um einen Knoten bemühen, um ihre Krawatte zu befestigen. Auswahl gibt es genug, den einfachen Four-in-Hand, den (halben) Windsorknoten, den Cavendish-Knoten, den kleinen Knoten und viele mehr. Die meisten dürften nicht sehr viele verschiedene Arten der Krawattenbefestigung kennen, dabei existieren 85 mögliche Knoten zum Binden einer Krawatte mit 8 Zügen, die allerdings nicht alle Balance, Symmetrie und Form berücksichtigen, wie der theoretische Physiker Thomas Fink und die Mathematikerin Yong Mao herausfanden . Aus praktischen Gründen werden also nicht alle davon realisiert, zum Einen sind unendlich lange Krawatten leider noch nicht erfunden, zum Anderen müsste man dann eventuell einen sehr schweren, unförmigen Krawattenknoten um den Hals tragen und bekäme davon bestimmt Rückenschmerzen. Dieser Gedanke lässt sich auch noch weiterführen. Wir wollen uns fragen, wie viele Möglichkeiten es gibt, eine Krawatte mit 13 Zügen zu binden, denn gerade schmale Krawatten werden häufiger umeinandergeschlungen und -gewickelt als breite . Diese Anzahl ergibt sich daraus, dass breite Krawatten gewöhnlicherweise 9 Mal binden lassen, während schmale maximal 15 Mal umeinander gewickelt werden. Um den Komfort zu erhalten, nehmen wir eine etwas kleinere Zahl als möglich an.

Zunächst führen wir eine Sprache ein, um eine Krawatte und ihren Knoten allgemein beschreiben zu können. Wir führen ein, dass wir immer ein aktives schmales Ende der Krawatte haben und das andere, breite Ende festhalten, damit es nicht verrutscht. Weiterhin teilen wir den Krawattenbinder in drei Regionen ein, die durch seine Krawatte eingeteilt werden, einen linken, einen rechten und einen zentralen Teil und bezeichnen sie mit [math] L [/math], [math] C [/math] und [math]R[/math] (left, center, right). Wir schreiben [math]\odot[/math], wenn wir die den schmalen Teil der Krawatte "aus der Ebene hinaus" ziehen und [math]\otimes [/math], wenn wir den schmalen Teil der Krawatte "in die Ebene hinein" ziehen. Außerdem schreiben wir [math]U[/math] dafür, wenn wir die schmale Seite der Krawatte durch eine zuvor entstandene Schlaufe ziehen, wie es am Ende eines jeden Krawattenknotens der Fall ist. Dies ist offensichtlich nur dann erlaubt, wenn wir die Krawatte im letzten Zug "aus der Ebene heraus" gezogen wurde. Mit großen Symbolen beschreiben wir also jeweils die Lage des breiten Endes der Krawatte, wenn das schmale Ende sich um das Zentrum [math]C[/math] schlingt, mit dem Index die Richtung, in der wir die Krawatte ziehen und [math]U[/math] beschreibt eine Umwicklung, wie oben beschrieben. Somit erhalten wir die folgenden möglichen Bewegungen, die wir mit der Krawatte durchführen können: [math]\{L_{\otimes}, L_{\odot}, C_{\otimes}, C_{\odot}, R_{\otimes}, R_{\odot}, U\}[/math] Um die Stabilität der Krawatte zu gewährleisten führen wir einige Regeln ein:

1. [math](L,C,R)[/math] darf sich nicht wiederholen, d.h. gleiche Symbole dürfen nicht aufeinander folgen. [math]U[/math] ist davon unabhängig und auch eine Folge aus [math](LCR)U(LCR)[/math] ist nicht erlaubt.
2. [math]\otimes[/math] und [math]\odot[/math] dürfen sich nicht direkt wiederholen. [math]U[/math] ist unabhängig davon.
3. [math]U[/math] darf nur direkt auf eine Bewegung nach außen folgen.
4. Ein Knoten darf nur mit [math]C_{\otimes}, C_{\odot}, U[/math] enden.
5. Eine [math]k[/math]-fache Umschlingung ist erst erlaubt, wenn zuvor [math]2k[/math] andere Bewegungen ausgeführt wurden.

Wir können im Folgenden die Symbole [math]\otimes[/math] und [math]\odot[/math] direkt weglassen, da sich stets aus dem letzten rekonstruieren lässt, mit welcher Bewegung wir begonnen haben (die letzte Bewegung muss nach außen gehen, da wir den Knoten mit [math]U[/math] beendet werden muss und Regel 3 erfüllt ist und außen und innen müssen sich stets abwechseln). Weiterhin können wir die Krawatte entweder im ([math]T[/math]) oder gegen den Uhrzeigersinn ([math]W[/math]) umschlingen, denn [math] RUR [/math], [math] CUC [/math] und [math] LUL [/math] können nicht auftreten wegen unserer ersten Annahme. Die Position des aktiven (schmalen) Teils der Krawatte lässt sich dann beschreiben als [math]\#W-\#T (mod 3)[/math]. Elementare Überlegungen führen uns auf die Tatsache, dass wenn wir den Krawattenknoten mit [math]W[/math] begonnen haben gelten muss [math]\#W-\#T = 2 (mod 3)[/math] und wenn wir den Knoten mit [math]T[/math] begonnen haben gelten muss [math]\#T-\#W = 2 (mod 3)[/math] für eine k-fache Umwicklung einer 2k-langen Sequenz. Hierbei fließt mit ein, dass die erste Bewegung die Schlaufe bildet, durch die das schmale Krawattenende zum Schluss gezogen wird. Gewöhnlicherweise muss die Krawatte von der Seite kommen, von der die Schlaufe kommt. Jede andere Schlaufe von links nach rechts oder rechts nach links muss vor oder hinter dem Knoten liegen und zwischen dem ersten und dem vorletzten liegen [math]2k-1[/math] Umschlingungen. In diesen muss die Krawatte die Krawatte auf die richtige Seite gebracht werden und daraus folgt die oben aufgestellte Behauptung.

Nun wollen wir eine Grammatik aufbauen, die beschreibt, wie wir die Krawatte binden können. Hierfür verwenden wir die Backus-Naur-Form . Es handelt sich hierbei um eine kontextfreie Grammatik, die in der Informatik Anwendung findet. Dabei werden neue Symbole definiert, indem bereits bekannte Symbole durch Leer-, Zeilen- und Spaltentrennzeichen definiert werden. Hierdurch können Umschlingungsfolgen zusammengefasst werden.

Nun können wir für unseren Krawattenknoten unter Verwendung der oben erwähnten Grammatik Erzeugende Funktionen finden, die sich durch eine formale Potenzreihe [math] \begin{align}f(z) = \sum\limits_{n=0}^{\infty} a_nz^n \end{align}[/math] darstellen lassen. Mittels eines Computers und der zuvor definierten Grammatik lässt sich eine solche Erzeugenden Funktion finden. So wird ein einfacher Krawattenknoten beschrieben durch [math]\begin{align} \frac{2z^2(2z+1)}{1-6z^2} = 2z^3 + 4z^4 + 12z^5+24z^6+72z^7+144z^8+432z^9+864z^{10}+2592z^{11}+5184z^{12}+15552z^{13}+\mathcal{O}(z^{14}) \end{align} [/math]

Der Exponent beschreibt dabei stets die Windungszahl der Krawatte, also wie oft wir sie gewickelt haben und der Vorfaktor die jeweils möglichen Umschlingungen. Da wir uns, wie weiter oben erwähnt, auf Knoten mit 13 Umschlingungen beschränken, können wir die Potenzreihe bei einem Exponenten von 13 abschneiden. Nun lässt sich für einen jeden Krawattenknoten eine solche Erzeugende Funktion finden, wobei wir durch zuvor gesetzte Parameter festlegen können, wie die Sequenz von Umschlingungen endet. Für 13 Windungen erhalten wir die folgenden Möglichkeiten:

Windungszahl	3	4	5	6	7	8	9	10	11	12	13	total
#right windings	1	1	3	5	11	21	43	85	171	341	683	1365
#left windings	0	2	2	6	10	22	42	86	170	342	682	1364
#center windings	1	1	3	5	11	21	43	85	171	341	683	1365
#left knots	0	2	4	8	24	48	144	288	864	1728	5184	8294
#right knots	1	1	4	8	24	48	144	288	864	1728	5184	8294
#center knots	1	1	4	8	24	48	144	288	864	1728	5184	8294
#single tuck knots	2	4	12	24	72	144	432	864	2592	4146	15552	84882
total #knots	2	4	20	40	192	384	1896	3792	19320	38640	202329	2666682

In dieser Zählung sind allerdings noch solche Krawattenknoten erlaubt, bei denen der die Krawatte falsch herum durchgezogen wurde und deshalb nicht ganz korrekterweise ein Krawattenknoten ist. Ziehen wir diesen Fehler ab, so erhalten wir eine maximale Anzahl möglichen Krawattenknoten mit 13 Bewegungen von 177146 Knoten.

Schuhe binden

Überkreuz- und Sägezahnschnürung

Was ist die effizienteste Methode, seine Schuhe zu binden, sodass man mit einem möglichst kurzen Schnürsenkel auskommt? Ist es die klassische Überkreuzschnürung?

Wir gehen von einem idealen Schuh aus, welcher [math] 2n [/math] [math](n\in \mathbb{N})[/math] Ösen besitzt, [math]n[/math] auf jeder Seite, um die Schnürsenkel zu binden. Um den Schnürsenkel mathematisch beschreiben zu können, muss er geschlossen sein. In der realen Welt ließe sich dies durch das Binden einer Schleife realisieren. Unsere Schnürung besteht aus [math]2n[/math] Segmenten, wobei ein Segment jeweils die Verbindung zwischen zwei Ösen ist. Das heißt demzufolge auch, dass jede Öse nur einmal verwendet wird. Als weitere Anforderung verlangen wir, dass mindestens eines der beiden einlaufenden Schnürsenkelsegmente je Öse seinen Ursprung in der anderen Reihe der Ösen besitzt. Damit wollen wir sicherstellen, dass die zwei Seiten des Schuhs wirklich festgezogen werden.

Besitzt der Schuh auf jeder Seite gerade [math] n=1[/math] Löcher, so gibt es genau eine Möglichkeit, seinen Schuh zu binden. Betrachten wir also nun einen Schuh mit [math] n\geq2[/math] Löchern auf jeder Seite. Die Anzahl der möglichen Schnürungen bei [math] n[/math] Löchern ergibt sich nach einer komplizierten Rechnung zu

[math]\#(n)= \frac{(n!)^2}{2} \sum\limits_{k=0}^{m}\frac{1}{n-k}\binom{n-k}{k}^2 [/math]

mit [math] m=n/2[/math] für gerade [math]n[/math] und [math]m=(n-1)/2[/math] für ungerade [math]n[/math].

Die Länge einer Schnürung ist die Summe aus allen einzelnen Teilsegmenten. Unter Verwendung von Symmetrien und Vereinfachungen ergibt sich folgendes Muster für die kürzeste Schnürung unter unseren Vorraussetzungen, wobei hier allerdings noch zwischen [math]n[/math] gerade oder ungerade unterschieden werden muss.

Unter unseren Voraussetzungen kürzeste Schnürung, links für [math] n[/math] gerade, rechts zwei Beispiele für [math] n[/math] ungerade

Diese Schnürung ist allerdings nicht die stärkste. Der Schnürsenkel funktioniert wie ein Flaschenzug, wenn er die zwei Reihen zusammenzieht. Allerdings hängt die Stärke der Schnürung vom Verhältnis der Abstände zwischen den einzelnen Ösen und den beiden Reihen ab. Es lässt sich ein kritisches Verhältnis [math]x_n[/math] finden, sodass für [math]x\leq x_n[/math]die Überkreuzbindung die stärkste Verbindung ist und für [math] x\geq x_n [/math]die Sägezahnbindung die stärkste Verbindung ist (siehe Bild rechts oben). Für reale Schuhe hingegen ist dieses Verhältnis meistens in der Nähe von [math] x_n[/math], sodass die Art der Bindung keine entscheidende Rolle spielt.

Zwei Nägel und ein Bild

Lösung des Zweinagelproblems

Meist werden Bilder bekanntermaßen ganz simpel und ohne mathematische Rafinesse mit einem oder zwei Nägeln an der Wand befestigt. Möchte man jedoch eine Weise finden, bei einer Aufhängung mit 2 Nägeln das Bild nur durch die Entfernung eines der beiden Nägel abhängen zu können (etwa um an den dahinterliegenden Tresor zu gelangen), so braucht es hierfür eine geschicktere Konstruktion.

Eine mächtige Methode, einen geeigneten Knoten zu finden, funktioniert auf die folgende Art und Weise : Man definiert für die Notation zunächst die Symbole [math]x_1,{x_1}^{-1},...,x_n, {x_n}^{-1}[/math], während hierbei jeweils [math]x_i[/math] die Umschlingung des [math]i[/math]-ten Nagels im Urzeigersinn und [math]{x_i}^{-1}[/math] jene gegen den Uhrzeigersinn beschreibt. Eine Umschlingung meint hierbei eine vollständige Umrundung des Nagels, wobei der Faden von unten kommt und auch wieder nach unten abgeführt wird. und außerdem von der linken Bildecke kommend so gelegt wird, dass bei Kreuzungen die zuvor gelegten Teile des Fadens immer überkreuzt werden. Somit lässt sich schließlich aus der Notation eindeutig der zugehörige Knoten konstruieren. Zur Verdeutlichung werden wir im Folgenden bei der Lösung des Zweinagelproblems zunächst die auf diese Weise systematisch beschriebene und anschließend eine äquivalente, aber übersichtlichere Darstellung des Knotens zeigen. Wendet man diese Notation auf das oben beschriebene Problem mit zwei Nägeln an, so kann man sich leicht davon überzeugen, dass

[math]S_2:=x_1x_2{x_1}^{-1}{x_2}^{-1}[/math]

eine Lösung ist, die die Voraussetzungen erfüllt. Denn sobald man nun einen Nagel hinauszieht, werden die darauf bezogenen Umschlingungen obsolet und es bleibt eine Umschlingung um den anderen Nagel im und eine gegen den Uhrzeigersinn übrig, wodurch das Bild auch diese scheinbare Aufhängung verliert und hinabfällt. Für die späteren Überlegungen lohnt es sich, dies als Kommutator [math][x_1,x_2]=x_1x_2{x_1}^{-1}{x_2}^{-1}[/math] einzuführen.

n-Nagel-Problem

Eine Lösung des Dreinagelproblems

Nun lässt sich diese Erkenntnis auch auf das Problem erweitern, ein Bild mit n Nägeln aufhängen zu wollen, welches erneut durch das Ziehen eines beliebigen Nagels abgehängt werden kann. Für das 3-Nagel-Problem wäre etwa eine Lösung, die bekannte 2-Nagel-Lösung [math]S_2[/math] zu nutzen und durch

[math][S_2,x_3]=S_2x_3{S_2}^{-1}{x_3}^{-1}=x_1x_2{x_1}^{-1}{x_2}^{-1}x_3x_2x_1{x_2}^{-1}{x_1}^{-1}{x_3}^{-1}[/math]

zu variieren. (Dies löst offensichtlich unser Problem, da bei Ziehung des ersten oder zweiten Nagels sowohl [math]S_2[/math] als auch dessen Inverses hinfällig wird und auch bei Ziehung des dritten Nagels nur noch eine Folge von Umschlingungen und ihr Inverses übrigbleiben, also das Bild ebenfalls hinabfällt.)

Analog ergibt sich für 4 Nägel erneut induktiv die folgende Lösung:

[math][S_3,x_4]=S_3x_4{S_3}^{-1}{x_4}^{-1}=...=x_1x_2{x_1}^{-1}{x_2}^{-1}x_3x_2x_1{x_2}^{-1}{x_1}^{-1}{x_3}^{-1}x_4x_3x_1x_2{x_1}^{-1}{x_2}^{-1}{x_3}^{-1}x_2x_1{x_2}^{-1}{x_1}^{-1}[/math]

Der bedeutende Nachteil dieser Methode ist ihre Ineffizienz: Man benötigt [math]2^n+2^{n-1}-2[/math] Umschlingungen. Der Beweis durch vollständige Induktion ist hier ausgeführt:
IA: Der behandelte Fall des 2-Nagel-Problems besitzt [math]2^2+2^1-2=4[/math] Umschlingungen.
IV: Die Aussage gelte für [math]n\in \lbrace2, i-1\rbrace[/math]
IS: Bezeichne [math]\# (S_i)[/math] die Anzahl der Umschlingungen bei der Lösung des i-Nägel-Problems. Wegen [math]S_i=[S_{i-1},x_i][/math] gilt dann mit der IV: [math]\#(S_i)=2\cdot\#(S_{i-1})+2=2\cdot(2^{i-1}+2^{i-2}-2)+2=2^i+2^{i-1}-2[/math]

Es sei hier angemerkt, dass man auch effizientere Konstruktionen der Knoten finden kann. So braucht etwa das 4-Nägelproblem auf die beschriebene Weise #(S_4)=22 Umschlingungen. [S_2,S_2] ist jedoch auch eine Lösung und benötigt lediglich 4\cdot#(S_2)=16 Umschlingungen.

Trivia

Wenn Ihnen dieser Artikel gefallen hat, könnte Ihnen auch das Museumswächterproblem gefallen. ^^

Autoren

Daniela Müller-Trefzer, Hjalmar Brunßen, Lasse Bassermann, Joris Hoffmann