Dénes König, „Das Labyrinthenproblem“

Drittes Kapitel.

Das Labyrinthenproblem.

§ 1. Formulierung des Problems. Die Lösung von Wiener.

Der Satz II 5 steht in engem Zusammenhang mit dem Problem der Labyrinthe¹), das in diesem Kapitel behandelt werden soll. Da die Breite der Gänge nicht in Betracht kommt, darf ein Labyrinth mit einem Graphen und zwar mit einem endlichen und zusammenhängenden Graphen identifiziert werden; den Knotenpunkten dieses Graphen entsprechen im Labyrinth die Verzweigungsstellen und die Endpunkte der Sackgassen. So entspricht z. B. dem Labyrinth der Fig. 18 der Graph der Fig. 19 (oder auch der Graph der Fig. 20). Es wird nun verlangt eine Methode anzugeben, durch die man eine bestimmte Stelle, die gewöhnlich als Mittelpunkt des Labyrinthes betrachtet wird, erreichen kann. Da es gänzlich unbestimmt ist, welche Stelle als Mittelpunkt betrachtet wird, ist die Aufgabe nur so zu lösen, daß man eine Methode angibt, durch die jede Stelle des Labyrinthes erreicht wird. Ist der Plan des ganzen {36} Labyrinthes bekannt, so gibt es natürlich, da es nur eine endliche Anzahl von Möglichkeiten gibt, keine Schwierigkeit. Wir wollen aber nicht voraussetzen, daß wir den Plan des Labyrinthes kennen. Statt dessen soll nur so viel vorausgesetzt werden, daß, wenn man bei der Wanderung im Labyrinthe an irgendeiner Verzweigungsstelle X (oder am Endpunkt X einer Sackgasse) angelangt ist, das Labyrinth (der Graph) in der „Umgebung von X “ bekannt sei, d. h. die nach X laufenden Gänge (Kanten) bekannt seien und auch gewisse Eigenschaften des schon zurückgelegten Weges, soweit diese sich auf die Umgebung der erreichten Stelle X beziehen.

¹) Fast alle Werke über Unterhaltungsmathematik beschäftigen sich mit den Labyrinthen. Außer den schon erwähnten Stellen in den Büchern von Lucas, Rouse Ball und Ahrens erwähnen wir noch: H. E. Dudeney, Amusements in Mathematics, London 1917, wo man (auf S. 127–137) viele Labyrinths findet.

Wir wollen erstens annehmen, daß, wenn man bei der Wanderung nach einem Knotenpunkt P gelangt, für jede nach P laufende Kante bekannt ist, ob sie schon früher passiert wurde; außerdem setzen wir voraus, daß man (so wie Theseus mit Hilfe des Fadens der Ariadne) in jedem Moment den ganzen bereits zurückgelegten Weg in entgegengesetzter Richtung genau (mit denselben Wiederholungen) wieder zu durchwandern vermag. Bei diesen Voraussetzungen wurde das Problem durch Wiener [1]¹) gelöst, der überhaupt das uralte Problem der Labyrinthe zuerst als mathematisches Problem behandelt hat. – Die Wienersche Anweisung lautet (in einer etwas spezialisierten Form) wie folgt:

¹) Hier handelt es sich um den zweiten Teil dieser Note. Der erste Teil (wo Wiener stillschweigend sich auf ebene Labyrinthe beschränkt) ist eigentlich mathematisch inhaltlos, da die dort gelöste Aufgabe, eine Methode anzugeben, wie man zum Anfangsort zurückfinden kann, eine triviale Lösung besitzt: man bleibe stehen.

In einem (beliebigen) Knotenpunkt A als Anfangsort beginnend wähle man ganz beliebig die Kanten AB, BC, CD, … bis man zuerst einen Endpunkt Q des Graphen oder einen solchen Knotenpunkt Q erreicht, der schon einmal passiert wurde. Bei Q angelangt, kehre man um und durchschreite den schon beschriebenen Weg im umgekehrten Sinne so lange, bis man zum erstenmal einen Knotenpunkt R erreicht, in dem eine solche Kante endet, die noch nicht beschrieben wurde. In diesem R angelangt, lenke man ab und verfolge irgend eine noch nicht durchlaufene Kante RS, dann setze man die Wanderung über noch unbeschriebene Kanten in beliebiger Weise fort, bis man zuerst einen Endpunkt oder einen solchen Knotenpunkt erreicht, der schon passiert wurde; hier kehre man wieder um usw.

Wir beweisen, daß die Kantenfolge ABC…Q…RS… 1. nach A zurückführt und 2. dann jede Kante des Graphen enthält.

Gibt es überhaupt keine Ablenkung, so kommt man natürlich nach A zurück. Gibt es aber eine Ablenkung, so muß es, da bei jeder Ablenkung eine neue Kante hinzugefügt wird, wegen der endlichen Kanten{37}-zahl eine letzte Ablenkung geben. Da auch die Knotenpunkte in endlicher Anzahl vorhanden sind, muß man nach dieser Ablenkung einen Endpunkt oder einen schon passierten Knotenpunkt Z erreichen. Laut unserer Anweisung muß man dann, da keine Ablenkung mehr möglich ist, diese ganze Kantenfolge F=AB…Z in entgegengesetzter Richtung durchlaufen, wodurch man in der Tat nach A zurückgelangt.

Daß auch jede Kante des ursprünglichen Graphen G durchlaufen wurde, ergibt sich folgendermaßen. Nehmen wir an, dies wäre nicht der Fall; dann bilden die nicht durchlaufenen Kanten einen eigentlichen Teilgraphen G″ von G, während die durchlaufenen Kanten den (zusammenhängenden) Teilgraphen G′ von G bilden. G′ und G″ haben keine gemeinsame Kante; sie haben aber wenigstens einen gemeinsamen Knotenpunkt P, da sonst G=G′+G″ (Satz I 24) nicht zusammenhängend wäre. Da P zu G′ gehört, ist P ein Knotenpunkt der Kantenfolge F=AB…Z. Da P auch zu G″ gehört, gibt es eine in P endende nicht durchlaufene Kante. Bei der oben erwähnten Durchlaufung von G in der Richtung nach A müssen wir also in P ablenken. Und dies widerspricht dem Umstande, daß die letzte Ablenkung schon früher stattgefunden hat.

§ 2. Die Lösung von Trémaux.

Das geschilderte Verfahren von Wiener kann nicht ökonomisch genannt werden, da die Kanten im allgemeinen sehr oft durchwandert werden müssen. Dies ist um so mehr zu beachten, als – laut Satz II 5 – auch eine solche Wanderung auf sämtlichen Kanten des Graphen existiert, bei der keine Kante öfter als zweimal durchlaufen wird. Wir werden zeigen, daß eine solche Lösung auch dann gefunden werden kann, wenn nicht der ganze Graph als bekannt vorliegt, sondern nur gewisse lokale Eigenschaften in jedem Moment der begonnenen Wanderung bekannt sind.

Wir wollen aber jetzt nicht voraussetzen, daß man den zurückgelegten Weg stets im entgegengesetzten Sinne wieder zu durchwandern vermag, sondern statt dieser Wienerschen Voraussetzung die (teilweise stärkere und teilweise schwächere) Annahme machen, daß, wenn man bei der Wanderung nach irgendeinem Knotenpunkt P gelangt ist, für jede nach P laufende Kante bekannt ist, ob sie schon und wie oft sie beschrieben wurde (die Richtungen, in denen die Kanten beschrieben wurden, werden dabei nicht als bekannt vorausgesetzt). Unter dieser Annahme wurde das Labyrinthenproblem in eleganter Weise von Trémaux gelöst¹). Seine Anweisung lautet folgendermaßen:

¹) S. Lucas [1, Bd. I, S. 47–51].

{38} Wenn man in einem beliebigen Anfangsknotenpunkt A₁ beginnend durch eine Kante PQ nach einem Knotenpunkt Q gelangt, der kein Endpunkt des Graphen ist und den man das erstemal erreicht, so setze man die Wanderung mit einer beliebigen anderen Kante QR fort. Wenn aber Q entweder schon früher aufgetreten ist oder ein Endpunkt ist und PQ zum erstenmal beschrieben wurde, so kehre man um, d. h. setze die Wanderung mit derselben Kante PQ (im entgegengesetzten Sinne QP) fort. Ist sowohl Q wie auch PQ schon früher aufgetreten, so schreite man auf einer noch nicht beschriebenen anderen Kante QR fort oder, wenn keine solche vorhanden ist, auf einer Kante QR, die nur einmal beschrieben wurde.

Folgt man diesen Regeln, so wird jede Kante höchstens zweimal durchlaufen; wegen der Endlichkeit der Kantenzahl muß also die Wanderung ein Ende haben, d. h. man muß einmal nach einem solchen Knotenpunkt K gelangen, daß alle nach K laufenden Kanten schon zweimal durchlaufen wurden. Und zwar muß K=A₁ sein, da wir sonst (für den Endpunkt K einer offenen Kantenfolge) einen Widerspruch mit Satz I 2 hätten. Jetzt wollen wir den Satz von Trémaux beweisen, welcher besagt, daß beim Abbrechen des Verfahrens bei einer¹) Ankunft in A₁ jede Kante zweimal beschrieben wurde und zwar je einmal in beiden Richtungen. Wir wollen unseren etwas umständlichen Beweis ganz ausführlich darstellen, um so mehr, als uns aus der Literatur kein vollständiger Beweis des Trémauxschen Satzes bekannt ist²).

¹) Die Wanderung muß nicht unbedingt abbrechen, wenn man das erstemal nach A₁ zurückgelangt.

²) Trémaux hat seinen Beweis, wie es scheint, nicht publiziert. Der Beweis von Lucas [1, Bd. I, S. 47–51] ist – wie er sagt – eine geringe Modifikation des Trémauxschen Beweises. Dieser Lucassche Beweis ist nicht vollständig, denn erstens wird der Fall, daß die dort mit ZA und ZY bezeichneten Kanten identisch sind (ein Fall, der tatsächlich vorkommen kann) außer acht gelassen, und zweitens wird eine wesentliche Behauptung am Ende des Beweises mit der kurzen Bemerkung „on demontrera de même“ erledigt. – Bei Ahrens [2, Bd. II, S. 192–194] werden diese beiden kritischen Punkte ausführlicher behandelt, aber auch sein Beweis enthält eine wesentliche Lücke, auf die wir gleich zurückkommen werden (s. die folgende Fußnote). – Es sei hier noch bemerkt, daß weder bei Lucas noch bei Ahrens der Zusatz, daß die Kanten zweimal in entgegengesetzter Richtung beschrieben werden, erwähnt wird.

Es seien

A₁A₂,A₂A₃,…,A_ρ−1A_ρ,A_ρA_ρ+1,…,A_nA₁ (1)

die Kanten, die bei einer regelrechten (d. h. die Trémauxschen Regeln befriedigenden) Wanderung auf dem endlichen und zusammenhängenden Graphen G der Reihe nach beschrieben werden. Wir beweisen zunächst, {39} daß es in (1) eine solche Kante geben muß, nach deren Beschreibung unmittelbar dieselbe Kante (im entgegengesetzten Sinne) beschrieben wird, daß man also wenigstens einmal umkehren muß. Es sei nämlich A_μ das erste Element in der Folge A₁,A₂,A₃,…, welches schon früher, etwa als A_ν (ν<μ), aufgetreten ist. Nun sind zwei Fälle möglich. α) Die Kante A_μ−1A_μ ist früher nicht aufgetreten; dann muß man, da A_μ als A_ν schon früher aufgetreten ist, hier umkehren, d. h. A_μ−1A_μ besitzt die verlangte Eigenschaft. β) A_μ−1A_μ ist schon früher aufgetreten, d. h. es ist für ein ρ<μ: A_μ−1A_μ=A_ρ−1A_ρ; nun ist aber A_μ−1 früher nicht aufgetreten, kann also wegen ρ−1<μ−1 nicht = A_ρ−1 sein, folglich ist A_μ−1=A_ρ; dies kann aber, da für ρ<μ−1 sicherlich A_μ−1≠A_ρ ist, nur im Falle ρ=μ−1 stattfinden. Setzt man diesen Wert von ρ ein, so erhält man A_μ−1A_μ=A_μ−2A_μ−1, folglich besitzt jetzt A_μ−2A_μ−1 die verlangte Eigenschaft. (Man kann leicht zeigen, daß der Fall β dann und nur dann auftritt, falls A_μ−1 ein Endpunkt von G ist.)

Es sei also A_ρA_ρ+1 eine Kante, die mit der in (1) ihr unmittelbar vorangehenden Kante A_ρ−1A_ρ identisch ist; also ist A_ρ+1=A_ρ−1. Entfernt man aus G diese Kante A_ρA_ρ+1 (=A_ρ−1A_ρ), so bilden die übrigen Kanten einen Teilgraphen G′ von G. Wir beweisen, daß auch der Graph G′ zusammenhängend ist. Ist A_ρ ein Endpunkt von G, so folgt dies aus Satz I 14. Ist A_ρ kein Endpunkt, so kann das Umkehren in A_ρ nur dann regelrecht sein, wenn A_ρ auch schon früher passiert wurde, und dann ergibt eine Teilfolge der Kantenfolge (1) eine die Kante A_ρ−1A_ρ nicht enthaltende offene Kantenfolge, die A_ρ−1 mit A_ρ verbindet. Laut Satz I 3 gibt es dann in G auch einen die Kante A_ρ−1A_ρ nicht enthaltenden Weg, der diese zwei Punkte verbindet. Dann besagt aber Satz I 13, daß G′ tatsächlich zusammenhängend ist.

Streicht man in (1) A_ρ−1A_ρ und A_ρA_ρ+1, so ergibt sich, da A_ρ−1=A_ρ+1 ist, ebenfalls eine Kantenfolge:

A₁A₂,A₂A₃,…,A_ρ−2A_ρ−1,A_ρ+1A_ρ+2,…,A_μA₁. (2)

Diese stellt eine Wanderung auf G′ dar, da A_ρ−1A_ρ (so wie überhaupt jede Kante) höchstens zweimal in (1) vorkommen kann, also A_ρ−1A_ρ in (2) nicht enthalten ist. Wir beweisen, daß (2) eine regelrechte Wanderung auf G′ ergibt, d. h. daß, wenn man durch irgendeine Kante A_σ−1A_σ (wo σ von ρ und von ρ+1 verschieden ist) nach A_σ gelangt ist, die Wahl der auf A_σ−1A_σ laut (2) unmittelbar folgenden Kante den Trémauxschen Regeln entspricht¹).

¹) In dem oben erwähnten Ahrensschen Beweis des Trémauxschen Satzes wird dieser Satz (auf S. 193 und auf S. 194) ohne Beweis und ohne formuliert zu sein, implizite wesentlich benutzt.

{40} Dies ist klar, wenn A_σ sowohl von A_ρ wie von A_ρ+1 (=A_ρ−1) verschieden ist, und auch dann, wenn σ<ρ−1 ist, da in diesen Fällen die Trémauxschen Regeln dieselben Möglichkeiten für G′ wie für G erlauben. Da σ=ρ und σ=ρ+1 ausgeschlossen sind, sind also nur folgende drei Fälle zu erledigen:  α) σ=ρ−1;  β) σ>ρ+1 und A_σ=A_ρ;  γ) σ>ρ+1 und A_σ=A_ρ−1 (=A_ρ+1).

α) Wir müssen zeigen, daß beim Übergang von A_σ−1A_σ=A_ρ−2A_ρ−1 auf A_ρ+1A_ρ+2 die Regeln nicht verletzt werden. Es sei erstens (Fig. 21) A_ρ−2A_ρ−1=A_ρ+2A_ρ+1 (also A_ρ−2=A_ρ+2). Dann ist der Übergang auf die identische Kante (das Umkehren) in G′ sicherlich regelrecht, wenn A_ρ−1 ein Endpunkt von G′ ist oder schon früher passiert wurde. Und eines von beiden ist sicher der Fall, da es sonst eine dritte und noch nicht passierte nach A_ρ+1 laufende Kante A_ρ+1K geben müßte und dann hätte man bei der Wanderung auf G nach A_ρA_ρ+1 nicht die Kante A_ρ+1A_ρ+2, die schon passiert wurde, sondern etwa diese Kante A_ρ+1K wählen müssen. – Zweitens sei A_ρ+1A_ρ+2≠A_ρ−2A_ρ−1 (Fig. 22). Nach der Beschreibung von A_ρ−2A_ρ−1 in G′ muß man nicht umkehren, da A_ρ−1 kein Endpunkt von G′ ist und da man sonst auch bei der Wanderung auf G hätte umkehren müssen, also A_ρ−2A_ρ−1 nicht mit A_ρ−1A_ρ hätte fortgesetzt werden können. Beim Übergang von A_ρ−2A_ρ−1 auf A_ρ+2A_ρ+1 in G′ würden wir also die Regeln nur dann verletzen, wenn A_ρ+1A_ρ+2 schon früher passiert und eine dritte Kante A_ρ+1K noch überhaupt nicht passiert wäre. Dann hätte aber auch bei der Wanderung in G auf A_ρA_ρ+1 nicht A_ρ+1A_ρ+2 sondern A_ρ+1K folgen müssen.

β) Wir beweisen, daß man den Regeln entspricht, wenn man bei der Wanderung auf G′ der Kante A_σ−1A_σ=A_σ−1A_ρ die Kante A_σA_σ+1=A_ρA_σ+1 folgen läßt, vorausgesetzt, daß σ>ρ+1 ist, daß also das doppelte Passieren von A_ρ−1A_ρ schon früher stattgefunden hat. Da A_ρ kein Endpunkt von G ist (es gibt ja wenigstens zwei nach A_ρ laufende Kanten: A_ρ−1A_ρ und A_σ−1A_ρ), muß A_ρ noch früher schon einmal passiert worden sein, da sonst dieses doppelte Passieren nicht regelrecht sein könnte. Ist also erstens A_σ−1A_ρ=A_σ+1A_ρ und somit A_σ−1=A_σ+1, so ist dieses Umkehren auch bei der Wanderung auf G′ regelrecht. Sind aber zweitens A_σ−1A_ρ und A_ρA_σ+1 verschieden (Fig. 23), so muß A_σ−1A_ρ schon zum zweitenmal beschrieben werden (da man sonst hätte umkehren müssen); wir können also die Regeln {41} nur dann verletzt haben, wenn es eine vierte und noch nicht passierte Kante A_ρK geben würde und A_ρA_σ+1 schon einmal passiert wäre; dann hätten wir aber die Regeln bei demselben Übergange schon bei der Wanderung in G verletzt.

γ) Wir zeigen, daß der Übergang von A_σ−1A_ρ−1 auf A_ρ−1A_σ+1 bei der Wanderung auf G′ regelrecht ist, falls für G dies der Fall war und σ>ρ+1 ist. Erstens seien diese zwei Kanten identisch, also A_σ+1=A_σ−1. Dieses Umkehren ist regelrecht, da A_ρ−1 auch bei der Wanderung auf G′ schon früher passiert wurde. Ist zweitens A_σ−1A_ρ−1≠A_ρ−1A_σ+1 (Fig. 24), so muß A_σ−1A_ρ−1 schon früher einmal passiert worden sein, und man kann ebenso schließen, wie im zweiten Fall von β.

Hiermit ist bewiesen, daß (2) eine regelrechte Wanderung auf G′ darstellt.

Nun können wir den Trémauxschen Satz durch vollständige Induktion in bezug auf die Kantenzahl beweisen, da der Satz für den Graphen mit einer einzigen Kante, wie unmittelbar zu sehen ist, besteht. Würde man bei der durch (1) gegebenen Wanderung auf G, die den Trémauxschen Regeln genügt, nicht jede Kante von G, in beiden Richtungen je einmal, durchlaufen, so würde natürlich bei der Wanderung (2) auf G′ nicht jede Kante von G′, je einmal in beiden Richtungen, durchlaufen werden. Da wir aber bewiesen haben, daß G′ zusammenhängend ist und daß die Wanderung (2) auf G′ den Trémauxschen Regeln genügt, so ist dies unmöglich; wir haben nämlich die Richtigkeit des Satzes für den zusammenhängenden endlichen Graphen G′, der um 1 weniger Kanten besitzt als G, vorausgesetzt.

Der Trémauxsche Satz ist hiermit bewiesen.

§ 3. Die Lösung von Tarry.

Man kann das Labyrinthenproblem in etwas einfacherer Weise lösen, wenn man statt der Voraussetzungen, die der Trémauxschen Lösung zugrunde liegen, folgende Voraussetzungen trifft. Es soll bei jeder Ankunft in irgendeinem Knotenpunkt P für jede nach P laufende Kante PK bekannt sein, ob sie schon in der Richtung nach K beschrieben würde, und man soll stets diejenige Kante bestimmen können, auf der P zum erstenmal erreicht wurde („Eintrittskante“ von P).

{42} Für diesen Fall wurde das Problem von Tarry [1]¹) gelöst. Die Vorschrift von Tarry lautet folgendermaßen:

¹) Mit Berufung auf diese Arbeit gibt Rouse Ball [1, S. 207] eine noch einfachere „Lösung“, die aber unrichtig ist. Einfache Beispiele zeigen nämlich, daß man beim Verfahren von Rouse Ball schon steckenbleiben kann, bevor man sämtliche Kanten beschrieben hat. – Auf derselben Stelle beschränkt Rouse Ball die Behandlung der Frage ausdrücklich auf zweidimensionale Labyrinthe. Dies ist gänzlich überflüssig. Alles bleibt auch z. B. für Katakomben richtig, wo die Gänge in beliebiger Weise auch unter- und übereinander verlaufen können.

Kommt man auf einer Kante PQ nach einem Knotenpunkt Q, so setze man die Wanderung mit irgendeiner Kante QR fort, die in der Richtung nach R noch nicht beschrieben wurde; man wähle aber für QR nur dann die Eintrittskante von Q, falls alle übrigen nach Q laufenden Kanten QK schon in der Richtung nach K beschrieben wurden.

Durch diese Regel ist es gesichert, daß jede Kante in beiden Richtungen höchstens einmal, also insgesamt höchstens zweimal beschrieben wird. Ebenso, wie oben für die Trémauxschen Wanderungen, ergibt sich auch hier, daß die Wanderung einmal abbrechen muß, und daß dies nur dann geschehen kann, wenn man zum Anfangspunkt A₁ der Wanderung zurückgelangt ist. Jetzt wollen wir den Satz von Tarry beweisen, welcher besagt, daß beim Abbrechen der Wanderung jede Kante genau zweimal beschrieben wurde, je einmal in beiden Richtungen²).

²) Der erste Teil des hier folgenden Beweises stammt von Tarry.

Es seien A₁,A₂,A₃,… die Knotenpunkte, die bei der Wanderung der Reihe nach getroffen werden. Es ist klar, daß sämtliche Kanten A₁K, die nach dem Anfangspunkt A₁ laufen, in der Richtung nach K schon beschrieben wurden, da sonst die Wanderung in A₁ nicht abbrechen könnte. Da A₁ ebensooft erreicht wie verlassen wurde, muß dann jede Kante A₁K auch in der Richtung nach A₁ beschrieben worden sein. Wir zeigen, daß auch die Kanten, die in den übrigen passierten Knotenpunkten A_n enden, ebenfalls in beiden Richtungen beschrieben wurden. Wäre dies nicht der Fall, so gäbe es in der Folge A₁,A₂,A₃,… einen ersten Punkt A_n derart, daß eine Kante A_nK nicht zweimal beschrieben wurde. Da auch A_n so oft verlassen wie erreicht wurde, muß es dann sowohl eine Kante A_nK₁ geben, die in der Richtung nach K₁, wie auch eine Kante A_nK₂, die in der Richtung nach A_n nicht beschrieben wurde. Nun ist aber für die Eintrittskante A_αA_n von A_n, sicherlich α<n, also wurde A_αA_n (wie alle nach A_α laufenden Kanten) auch in der Richtung nach A_α beschrieben. Dies ist aber, nach der Tarryschen Regel, nur dann regelrecht, wenn alle nach A_n laufenden Kanten A_nK in der Richtung nach K beschrieben wurden. Und dies {43} widerspricht dem Umstand, daß A_nK₁ in der Richtung nach K₁ nicht beschrieben wurde.

Es bleibt nur noch übrig zu zeigen, daß jeder Knotenpunkt des Graphen einer der Punkte A_i ist, also bei der Wanderung getroffen wird. Nehmen wir an, daß ein Knotenpunkt B nicht getroffen wird. Wir verbinden B mit A₁ durch einen Weg A₁B₁B₂…B_ν (B_ν=B). Sei B_α der erste Punkt in der Folge B₁,B₂,…, der bei der Wanderung nicht getroffen wird. Dann wird B_α−1 getroffen (für α=1 ist B_α−1=A₁ zu setzen), so daß, wie wir sahen, B_α−1B_α (sogar zweimal) beschrieben wurde. Also wurde auch B_α getroffen, im Widerspruch zu unserer Annahme.

Hiermit ist der Tarrysche Satz bewiesen.

§ 4. Zusammenhang zwischen der Trémauxschen und der Tarryschen Lösung.

Zwischen der Trémauxschen und der Tarryschen Wanderungen besteht ein interessanter Zusammenhang, der durch folgenden Satz ausgedrückt wird:

Jede Trémauxsche Wanderung ist zugleich eine Tarrysche Wanderung¹).

¹) S. die Remarque von Tarry [1, S. 190].

Mit anderen Worten: wir wollen jetzt folgendes beweisen:

Kommt man bei einer Trémauxschen Wanderung nach einem Knotenpunkt P, der vom Anfangspunkt der Wanderung verschieden ist, so wird die Wanderung nur dann auf der Eintrittskante von P fortgesetzt, wenn alle anderen Kanten PK, die in P enden, schon in der Richtung nach K beschrieben wurden.

Dies ist klar, wenn P zum erstenmal erreicht wird, also P ein Endpunkt des Graphen ist; wir können also voraussetzen, daß dies nicht der Fall ist. Wir wollen die Anzahl derjenigen nach P laufenden Kanten, die, nachdem P zum n-ten Mal passiert wurde (n=1,2,3,…), genau einmal beschrieben wurden, mit ρ_n bezeichnen. Es ist ρ₁=2. Kommt man zum n-ten Mal (n>1) nach P auf einer Kante, die das erstemal beschrieben wird, so muß man umkehren, und somit ist ρ_n=ρ_n−1. Wurde aber diese Kante auch schon früher einmal passiert, so hört sie jetzt auf, eine genau einmal passierte Kante zu sein. Es ist also ρ_n=ρ_n−1−2 oder ρ_n=ρ_n−1, je nachdem die Kante, auf der wir die Wanderung – nachdem P zum n-ten Mal erreicht wurde – fortsetzen, auch schon früher einmal beschrieben wurde oder nicht. Aus ρ₁=2 folgt also ρ₂=0 oder 2, also auch ρ₃=0 oder 2, usw.:  jedes ρ_n ist entweder 0 oder 2 (ist ρ_κ=0, so ist natürlich ρ_κ+1=ρ_κ+2=…=0).

{44} Nehmen wir nun an, daß nach der n-ten Ankunft in P auf der Kante Q_nP (n>1) die Eintrittskante Q₁P von P zur Fortsetzung der Wanderung gewählt wurde, (es ist Q_nP≠Q₁P da sonst, wegen n>1, Q₁P dreimal beschrieben würde). Nach dem (n−1)-ten Passieren von P wurden sowohl Q₁P wie Q_nP schon beschrieben. Für Q₁P ist das klar, da n>1 ist. Für Q_nP folgt das daraus, daß man sonst nach der n-ten Ankunft in P, statt PQ₁ zu wählen, auf Q_nP hätte umkehren müssen. Anderseits wurden diese zwei Kanten vor der n-ten Ankunft in P nur einmal beschrieben, da sonst das Beschreiben dieser Kanten beim n-ten Passieren von P nicht den Trémauxschen Regeln entsprechen würde. Also ist, da ρ_n−1 nicht größer als 2 sein kann, ρ_n−1=2. Vor der n-ten Ankunft in P sind also von allen Kanten KP nur Q₁P und Q_nP genau einmal beschrieben worden, während die übrigen nach P laufenden Kanten zweimal beschrieben wurden, da, wenn eine unbeschrieben wäre, die Wahl der einmal schon beschriebenen Kante PQ₁ nach der n-ten Ankunft in P nicht regelrecht wäre. Nach dem Trémauxschen Satz kann aber keine Kante in derselben Richtung zweimal beschrieben worden sein; also sind, mit Ausnahme von PQ₁, sämtliche Kanten PK in der Richtung nach K beschrieben worden. Bei der n-ten Ankunft in P ist also in der Tat PQ₁, die einzige Kante PK, die in der Richtung nach K noch nicht beschrieben wurde.

Hier sei noch eine Bemerkung zur Tarryschen Lösung hinzugefügt. Würde man die Regel von Tarry so modifizieren, daß man, statt zu verlangen, daß keine Kante in derselben Richtung zweimal beschrieben werde, nur so viel fordern würde, daß keine Kante dreimal beschrieben werde, so würde durch die neue Regel das Labyrinthenproblem nicht gelöst. Wie die Wanderung auf der Fig. 25 zeigt, können dann nämlich Kanten unbeschrieben bleiben.

Wenn also auch, wie eben bewiesen wurde, die Trémauxschen Regeln sich aus den Tarryschen durch Spezialisierung ergeben, so wird doch durch die Trémauxsche Lösung des Labyrinthenproblems insofern ein weitergehendes Resultat erzielt als durch die Tarrysche, als bei den Trémauxschen Wanderungen die Forderung der entgegengesetzten Richtungen sozusagen automatisch erfüllt wird und die Richtung, in der eine Kante beschrieben wurde, bei der Rückkehr zu einem Endpunkt der Kante nicht als bekannt vorausgesetzt werden muß.

{45}

§ 5. Umgekehrte Wanderungen.

Endlich sollen noch zwei Bemerkungen über die Umkehrung einer Wanderung angeführt werden. Ich verdanke beide der freundlichen Mitteilung von J. Kürschák.

Ist

A₁A₂ … A_μ−1A_μA_μ+1 … A₁ (I)

eine Tarrysche Wanderung, so ist auch die umgekehrte Wanderung

A₁ … A_μ+1A_μA_μ−1 … A₂A₁ (II)

eine solche.

Es ist nämlich klar, daß die (beendeten) Tarryschen Wanderungen durch folgende drei Eigenschaften charakterisiert sind:

1. Keine Kante wird zweimal in derselben Richtung durchlaufen.

2. Die Eintrittskante irgendeines Knotenpunktes P ist mit der Austrittskante von P (auf der P zuletzt verlassen wird) identisch (sonst wäre im Gegensatz zum Tarryschen Satz diese Eintrittskante nur einmal durchlaufen).

3. Alle Kanten werden in beiden Richtungen durchlaufen (das ist der Tarrysche Satz).

Nun besitzt offenbar (II) irgendeine dieser drei Eigenschaften, falls dies für (I) der Fall ist.

Entsprechendes gilt auch für die Trémauxschen Wanderungen. Wir beweisen nämlich den Satz:

Ist (I) eine Trémauxsche Wanderung, so ist auch die umgekehrte Wanderung (II) eine solche.

Wir müssen zeigen, daß bei der Wanderung (II) der Übergang von A_μ+1A_μ auf A_μA_μ−1 den Trémauxschen Regeln entspricht. – Wird bei diesem Übergang A_μ zum erstenmal oder zum letztenmal passiert, so entspricht dieser Übergang den Trémauxschen Regeln, falls er der Tarryschen Regel entspricht (auch wenn A_μ ein Endpunkt des Graphen ist). Dies ist aber sicherlich der Fall, da (I) – als eine Trémauxsche Wanderung –, also auch (II) – als die Umkehrung einer Tarryschen Wanderung – Tarrysche Wanderungen sind. Wir müssen also nur noch den Fall in Betracht ziehen, wo beim Übergang von A_μ+1A_μ zu A_μA_μ−1 der Punkt A_μ weder zum ersten- noch zum letztenmal vorkommt. Hier sind zwei Fälle zu unterscheiden. Erstens sei A_μ+1A_μ=A_μA_μ−1. Dann wird, da jede Kante nur zweimal beschrieben wird, diese Kante nicht auch schon früher beschrieben. Das Umkehren auf dieser Kante entspricht also den Trémauxschen Regeln. Zweitens sei A_μ+1A_μ≠A_μA_μ−1. Bei dem entsprechenden Übergang von A_μ−1A_μ zu A_μA_μ+1 in (I) wird dann ebenfalls A_μ weder zum {46} ersten- noch zum letztenmal erreicht. Bei diesem Übergang wird also α) A_μ−1A_μ bereits zum zweitenmal beschrieben (da man sonst in A_μ umkehren müßte) und β) A_μA_μ+1 nur zum erstenmal. Wäre nämlich A_μA_μ+1 zum zweitenmal beschrieben, so würde bei diesem Passieren von A_μ die Anzahl ρ der nach A_μ laufenden und genau einmal beschriebenen Kanten verringert, also – wie wir oben sahen – gleich Null werden, und dies ist unmöglich, da – infolge des Umstandes, daß die Trémauxsche Wanderung zugleich eine Tarrysche ist – die Eintrittskante von A_μ bis zum letzten Passieren von A_μ genau einmal beschrieben bleibt. Nun bedeutet aber α) und β), daß in (II) bei dem betrachteten Übergang A_μ+1A_μ zum zweiten- und A_μA_μ−1 zum erstenmal beschrieben wird. Und dies entspricht den Trémauxschen Regeln.

Es sei {A,B,C,…} eine Menge von „Punkten“. Verbindet man gewisse aus zwei verschiedenen dieser Punkte gebildete Paare durch eine oder mehrere „Linen“, so nennt man das so entstehende Gebilde einen Graphen. Diejenigen der Punkte A,B,C,… die mit wenigstens einem Punkte verbunden wurden, heißen die Knotenpunkte oder Punkte des Graphen (Knotenpunkte, die man als „isoliert“ bezeichnen könnte, sind also ausgeschlossen). Die eingeführten Linien heißen die Kanten des Graphen¹).

¹) In diesem Sinne wurde wohl das Wort graph zuerst von Sylvesternbsp;[3, S. 149] 1878 benutzt. Als kurze, prägnante und in allen Sprachen brauchbare Bezeichnung scheint sie uns die entsprechendste zu sein. Im selben oder ähnlichen Sinne wurden auch folgende Ausdrücke benutzt: Linearkomplexion, Liniensystem, Streckenkomplex, Kantenkomplex, Netz. Die Franzosen benutzen größtenteils: réseau. Für Knotenpunkt sind im Englischen: node, knot, vertex; im Französischen: sommet, noeud, carrefour eingeführt worden und für Kante im Englischen: branch, edge; im Französischen: chemin, arête, lien.

Bei der Definition des Graphen haben wir vorausgesetzt, daß jede Kante zwei verschiedene Punkte miteinander verbindet. Manchmal empfiehlt es sich, die Graphen im weiteren Sinne zu betrachten, d. h. auch solche Kanten zuzulassen, welche einen Knotenpunkt P mit sich selbst verbinden. Eine solche Kante heißt eine Schlinge und kann durch PP bezeichnet werden.

Satz I 1: Eine Punktmenge Π und eine Kantenmenge Κ bilden dann and nur dann die Menge der Knotenpunkte, bzw. der Kanten eines – und zwar einzigen – Graphen, falls die Endpunkte jeder Kante aus Κ zu Π gehoren and jeder Punkt aus Π der Endpunkt einer Kante aus Κ ist.

Kann man sämtliche Kanten eines (endlichen) Graphen in einer Folge von der Form

AB,BC,CD,…,KL,LM(1)

aufzählen, wo jeder Knotenpunkt und jede Kante beliebig (endlich) oft vorkommen kann, so ist der Graph als eine Kantenfolge charakterisiert. Je nachdem A≠M oder A=M ist, heißt die Kantenfolge offen oder geschlossen. Im ersten Fall sagen wir, daß sie die Knotenpunkte A and M miteinander verbindet, oder auch, daß A und M die Endpunkte der offenen Kantenfolge sind. Die übrigen Knotenpunkte, sowie jeder Knotenpunkt einer geschlossenen Kantenfolge heißen innere Knotenpunkte. Kommt eine Kante in (1) n-mal vor, so heißt n die Multiplizität dieser Kante in bezug auf die Kantenfolge. Es gilt offenbar der

Satz I 2: Die Summe der Multiplizitäten der nach demselben Knotenpunkt P laufenden Kanten einer Kantenfolge is gerade oder ungerade, je nachdem P ein innere Knotenpunkt oder ein Endpunkt der Kantenfolge ist.

Kommt in (1) keine Kante zweimal vor, d. h. ist jede Multiplizität 1, so heißt die Kantenfolge ein (offener oder geschlossener) Kantenzug. Sind auch noch die Punkte A,B,…,L,M sämtlich voneinander verschieden, so heißt der offene Kantenzug ein Weg; ist A=M, aber A,B,…,L sämtlich voneinander verschieden, so heißt der geschlossene Kantenzug ein Kreis.

Satz I 3: Bilden gewisse Kanten eines Graphen eine offene Kantenfolge, welche die Knotenpunkte A₁ und A₂ miteinander verbindet, so bilden gewisse Kanten dieser Folge einen Weg, der ebenfalls A₁ mit A₂ verbindet.

Satz I 13: Gibt es im zusammenhängenden Graphen G einen Weg W, welcher die Endpunkte A und B einer Kante AB verbindet und diese Kante AB nicht enthält, so ist der Graph G′, der durch das Entfernen der Kante AB aus G entsteht, ebenfalls zusammenhängend.

Satz I 14: Entfernt man aus einem zusammenhängenden Graphen G einer seiner Endkanten oder eine Kante eines seiner Kreise, so bilden die übrigbleibenden Kanten einen ebenfalls zusammenhängend Graphen G′.

Hier empfiehlt es sich, den Begriff der Graphenaddition einzuführen. Sei {G_α} eine beliebige Menge von Graphen. Laut Satz 1 bilden diejenigen Knotenpunkte und Kanten, die in wenigstens einem der Graphen G_α enthalten sind, einen Graphen G. Sind die Graphen G_α paarweise fremd zueinander, so bezeichnen wir G als die Summe der Graphen G_α und schreiben G=ΣG_α. Die Voraussetzung, daß die G_α fremd zueinander seien, ist hier wesentlich; nur in diesem Falle sagen wir, daß ein Graph in die Teilgraphen G_α zerfällt und nur in diesem Falle schreiben wir Gleichungen von der Form G=ΣG_α.

Satz I 24: Ein Graph ist dann und nur dann zusammenhängend, wenn er nicht die Summe von zwei eigentlichen Graphen ist.

Satz II 5: Jeder endliche zusammenhängende Graph G kann als eine geschlossene Kantenfolge so beschrieben werden, daß jede Kante genau zweimal beschrieben wird.