Thomas Kahle
Im 18. Jahrhundert erschuf Leonard Euler ein neues Gebiet der Mathematik, welches sich vom Zählen und Messen als Ursprung aller Mathematik entfernte: die Graphentheorie. In ihr werden Abstands- und andere Informationen ignoriert und ein Graph speichert nur noch die Existenz von irgendwelchen Dingen und welche Paare dieser Dinge in einer Beziehung stehen. Das Konzept ist so vielseitig, dass es praktisch überall auftaucht und trotzdem kann man leichte und schwierige Theoreme in der Graphentheorie beweisen. In diesem ersten Teil einer Doppelfolge bespreche ich die Ursprünge der Graphentheorie.
- 8 London Tube routes that are quicker by foot.
- Königsberger Brücken
- Ikosaederspiel
- Journal of game and puzzle design
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Verwandte Folge:
Automatisch generiertes Transkript (nicht geprüft)
Ja, hallo zusammen! Ich begrüße euch an den Empfangsgeräten. Hier ist der
Eigenraum. Ich bin Thomas, ich bin Mathematiker und mache euch hier einen
kleinen Mathe-Podcast, weil ich denke, dass es nicht genug Mathe-Podcasts gibt.
Und heute erzähle ich euch eine kleine Geschichte, die beginnt mit der U-Bahn-Karte
von London, der sogenannten Tube Map. Die habt ihr bestimmt alle schon mal gesehen,
oder? Das ist so eine ikonische Karte der
Untergrundbahn in London. Da hat jede Linie so eine bestimmte Farbe und man
kann sehen, wo man von welcher Linie in welche Linie umsteigen kann, wie die
Haltestellen heißen. Und ich tue euch auch mal in diese kleinen Kapitelbildchen
so ein Bild von der Karte. Die hat eigentlich jeder schon mal gesehen, die
wurde von Harry Beck 1933 entworfen. Das ist so ein legendäres Design und viele
Karten von Transportsystemen, die man heutzutage kennt, orientieren sich daran.
So ein paar Stilelemente, die zum Beispiel immer wieder gern genommen werden, ist
dass Linien, die dann irgendwo hingehen, einfach so als gerade Linien zum Rand
der Karte laufen. Auch wenn die natürlich in Wirklichkeit nicht gerade sind oder
vielleicht auch mal so ein bisschen in die Richtung wechseln oder sich
Schlangenlinien förmlich durch irgend so ein Gebiet winden, laufen die dann
einfach gerade in irgendeine Himmelsrichtung davon und in immer
gleichen Abständen kommen die Haltestellen, sodass man immer schön den
Namen der Haltestelle auch noch daneben schreiben kann und so weiter. Und diese
Karte, die legendäre London Tube Map und deren Verwandte, deren Updates, die
haben ein bisschen seltsame Eigenschaften, die auch schon so manches
Spielchen in London für die Touristinnen und Touristen hervorgebracht haben.
Und die Spiele gehen so, dass man versucht, zwischen zwei Haltestellen
sich so schnell wie möglich zu bewegen. Eine Person macht es vielleicht zu Fuß
oder aus einer Kombination aus zu Fuß und Tube und eine andere Person benutzt
eben die Suche eines kurzen Pfades auf dieser U-Bahn-Karte. Und da kann man ganz
komische, kuriose Überraschungen erleben. Also dann sieht man zwei Stationen, die
sind auf der Karte der U-Bahn, auf der Tube Map, vielleicht durch einen Umstieg
sogar noch verbunden. Also man fährt eine Station auf der einen Linie, steigt nochmal
oben, fährt eine Station auf der anderen Linie, obwohl oben an der Oberfläche die
beiden Stationen nur 250 Meter auseinander sind. Also kann man eine 250
Meter Laufstrecke durch 15 Minuten U-Bahn fahren und in irgendwelchen
Schlangen stehen, ersetzen. Und woran das liegt, ist, dass die U-Bahn-Karte nicht
alle Informationen enthält. Zum Beispiel sind die Abstände, die wirklichen
Abstände an der Oberfläche zwischen den einzelnen U-Bahn-Stationen nicht
abgebildet, nicht maßstabsgerecht abgebildet. Die U-Bahn-Karte enthält nur
die Information, wo die Linien laufen, natürlich die Namen der Stationen, wo
sich Linien kreuzen, wo Umsteigemöglichkeiten bestehen und dann
eben noch einige Informationen, wo ist Norden, welche Station ist nördlicher als
welche Station, welche Station ist südlicher. Es enthält also auch einige
Ortsinformationen, aber diese Ortsinformationen treten in den
Hintergrund und es bleibt nur so eine, wie man sagt, eine topologische
Information über, eine Information über die Zusammenhänge zwischen den Orten.
Da ist also alles Mögliche weg abstrahiert. Man hat nur noch
Verbindungsinformationen und damit sind wir auch schon in dem mathematischen
Gebiet der Grafentheorie, dass sich eben mit solchen Informationen, abstrahierten
Informationen über Verbindungen beschäftigt. Und solche Grafen, um die es
in der Grafentheorie geht, die bestehen nur aus sogenannten Ecken und Kanten. Und
die Ecken, die sind dabei einfach irgendwelche Punkte, wie zum Beispiel die
U-Bahn-Stationen. Und die Kanten sind Verbindungen zwischen zwei Punkten. Und
das könnte zum Beispiel so eine Bahnstrecke sein, die von der einen
Station direkt zu der anderen Station führt. Und so eine London-Tube-Map ist
jetzt ein sogenannter Graf mit den Ecken, den U-Bahn-Stationen und den
Kanten, den direkten Verbindungen. Und so eine Linie, so eine Route, die ein echter
Zug dann abfährt entlang dieser Karte, würde man dann zum Beispiel ein
Weg nennen in diesem Grafen. Ein Weg ist eine Aneinanderreihung von Kanten, so dass
zwei aufeinanderfolgende Kanten sich immer an einer Station treffen, weil der
Zug natürlich diese Kanten in der passenden Reihenfolge nacheinander
abfahren muss, so dass er von einer Station immer zur nächsten fährt. Und
das ist ein total flexibles Konzept. Damit kann man alles Mögliche darstellen,
was irgendwie mit Paarbeziehungen zu tun hat. So wie eben hier, dass zwischen einem
Paar von Stationen eine U-Bahn verkehrt. Dort also so eine Paarbeziehung besteht.
Und dieses ganze Weglassen von Entfernungsinformationen oder sonstigem
Beiwerk, um was es sich handelt bei den Ecken, um was es sich bei den Kanten
handelt, wie lang die Kanten sind, welche Farbe die Kanten haben, das ist alles
Zusatzinformation, die man jetzt noch hinzufügen kann, aber in dem mathematischen
Gebiet der Grafentheorie erstmal keine Rolle spielt. Also die einfachste
Variante, es gibt nur diese Ecken und Kanten und das ist die Datenstruktur, mit
der sich dieses Gebiet beschäftigt. Und das ist so flexibel, dass es natürlich
überall auftaucht. Zum Beispiel könnte man aus Landkarten, könnte man Grafen
machen. Da macht man aus jedem Land, das man auf seine Landkarte haben möchte,
eine Ecke. Also etwas, das verbunden werden soll. Und wenn zwei Länder
benachbart sind, dann male ich eine Kante zwischen den Ecken, die zu den beiden
Ländern gehören. Und da gibt es das berühmte Vierfarb-Theorem und das
Vierfarb-Theorem, das sagt eben aus, wenn man so eine Landkarte hat, dann genügen
immer vier Farben, um alle Länder so einzufärben, dass nie zwei benachbarte
Länder die gleiche Farbe haben. Und das ist im Prinzip ein Problem aus der
Grafentheorie, das nämlich sagt, dass wenn ich so einen Grafen habe, der zu
einer Landkarte gehört, einen sogenannten planaren Grafen, dann kann ich die Ecken
mit vier verschiedenen Farben einfärben, so dass nie zwei benachbarte Ecken, nie
zwei Ecken, zwischen denen eine Kante verläuft, die gleiche Farbe haben. Oder
ich könnte als einen Grafen modellieren, die Menschen, die sich auf einer Party
befinden und mit den Kanten die, die sich mal die Hand gegeben haben. Oder das
Straßennetz oder das Internet, also die Kabel zwischen irgendwelchen Computern.
Ich könnte in einem Spiel, ein Labyrinth damit modellieren. Zum Beispiel jedes
Mal, wenn ich eine Entscheidung treffen muss, ob ich links rum oder rechts rum
oder geradeaus gehe, mache ich mir so eine Ecke in meinem Grafen und dann sind
die Wege entlang der Korridore im Labyrinth die Kanten in meinem Grafen.
Man kann diesen Begriff jetzt auch noch erweitern, indem man zum Beispiel noch
den Kantenrichtungen gibt oder auch vielleicht da noch Zahlen dran macht,
aber das wollen wir erst mal nicht machen. Also wir haben nur dieses abstrakte
Konzept. Es gibt keinerlei Axiome. Das ist auch so ein bisschen seltsames
mathematisches Gebiet, wenn man schon mal so ein bisschen in abstrakte
Mathematik reingeschnuppert hat. Da kennt man ja vielleicht so Begriffe wie eine
Gruppe oder so, für die man immer irgendwelche Axiome hat. Da müssen immer
irgendwelche Rechenregeln gelten oder sowas. Aber für Grafen hat man überhaupt keine Axiome.
Man hat einfach nur diese Definition. Es ist einfach eine Menge von Ecken und
diese Kanten dazwischen. Und die Grafentheorie, die begann mit Euler im
18. Jahrhundert in Königsberg, was heute Kaliningrad heißt. Und dieses Kaliningrad,
das hatte damals sieben Brücken in dem Stadtzentrum. Da gabelt sich nämlich ein
Fluss und genau in der Gabelung liegt noch eine Insel. Also gibt es da vier
Landmassen. Eine Nordlandmasse, eine Südlandmasse, eine Ostlandmasse und eben
noch diese Insel. Und die sieben Brücken verlaufen irgendwie so zum Beispiel zwei
gehen vom Nordufer zur Insel und eine geht vom Nordufer zum Ostufer und so
weiter. Und das ergibt dann irgendwie so eine Konfiguration. Und an jedem der
großen Landstücken kommen genau drei Brücken an und an der Insel kommen fünf
Brücken an. Und ein Bild davon tue ich euch auch in die Kapitelmarke hier oder
ihr könnt es in den Shownotes finden. Und die Frage war jetzt, also da gab es
dann so eine Art Wettbewerb, so eine Art Pubcrawl, ob man einen Spaziergang machen kann.
Der geht los beim Pub. Also erstmal betrinkt man sich ordentlich und dann
prallt man rum, dass man über jede der Brücken genau einmal gehen kann und dann
wieder zum Pub zurückkommen kann. Also das war diese Aufgabe. Der Königsberger
Spaziergang bestand darin, irgendwo loszumarschieren, jede Brücke genau
einmal zu passieren und wieder am Anfang zurückzukommen. Und Leonhard Euler
bewies 1736 ungefähr oder genau wie belastbar die Zahl ist, weiß ich jetzt
nicht, aber jedenfalls im ersten Hälfte des 18. Jahrhunderts, dass so ein Weg
nicht möglich ist. Und das sieht man so an als den Anfang der Grafentheorie, weil
er da, um dieses Problem zu lösen, erkannte, dass es auf allerlei Dinge
nicht ankommt in diesem Problem. Es kommt nicht darauf an, wo Königsberg liegt.
Es kommt auch nicht darauf an, wie Königsberg heißt. Es kommt auch nicht
darauf an, wie groß die Insel ist. Es kommt nicht darauf an, wie die Brücken
gebaut sind. Es kommt nur auf die Anordnung der Brücken und der Landmassen
zueinander an. Es kommt auch nicht darauf an, ob diese Karte jetzt vielleicht
gedreht ist. Es geht nur um die Information, die in dem Grafen steckt, der
als Ecken die Landmassen hat und als Kanten eben die Brücken. Und er benutzt
eine ganz einfache Methode. Wenn ich jetzt meinen Spaziergang mir mal denke,
angenommen, ich hätte so einen Spaziergang gemacht, dann komme ich ja
unterwegs auf allerlei Landmassen vorbei. Ich spaziere, spaziere, spaziere und bei
jeder Landmasse, wo ich unterwegs vorbeikomme, komme ich durch irgendeine
Brücke auf diese Landmasse und dann verlasse ich die Landmasse wieder über
eine weitere Brücke, weil die erste Brücke kann ich ja nicht noch mal nehmen,
denn ich benutze ja jede Brücke nur einmal. Eventuell komme ich im Verlauf
meines Spaziergangs bei der gleichen Landmasse noch mal vorbei, aber auch in
diesem Fall gilt, dass ich sie über eine Brücke betrete und über eine andere
Brücke wieder verlasse, es sei denn, es ist die letzte Landmasse in meinem
Spaziergang, zu der ich ankommen will. Und daraus kann ich jetzt direkt ableiten,
dass alle Landmassen, die nicht die erste oder die letzte bei meinem Spaziergang
sind, eine gerade Anzahl von Brücken besitzen müssen. Und sofort bekomme ich
eine sogenannte notwendige Bedingung. Wenn ich meinen Königsberger Spaziergang
mache, muss jede Landmasse, die ich in der Mitte, die nicht am Anfang oder am
Ende meines Weges liegt, muss genau eine gerade Anzahl von Brücken haben. Und
damit ist die ganze Sache in dem wirklichen Königsberg von 1730 schon
beendet. Denn dort haben wir drei Landstücken mit genau drei Brücken und
eins mit fünf. Dort gibt es also überhaupt keine Landmasse, die eine
gerade Anzahl an Brücken hat. Insofern sieht man sofort, dass dieser Weg dort
nicht möglich ist. Und das wurde sogar noch ausgebaut. Also Euler hat die
komplette Lösung vorgeschlagen, die zwei Probleme, die beiden verwandten Probleme,
löst. Nämlich diesen Spaziergang so zu machen, dass man an der gleichen Bar
wieder ankommt. Das nennt man einen Eulerschen Kreis. Oder einfach nur
irgendwie durch die Stadt spaziert, so dass man jede Brücke genau einmal
benutzt. Und beide sind unmöglich. Und diese Einsicht Eulers begründete die
Grafentheorie. Und das ist auch wissenschaftsgeschichtlich bedeutend,
weil die Mathematik sich an dieser Stelle etwas wegentwickelt von einem
Postulat von Aristoteles, der nämlich mal postuliert hat, dass die Mathematik die
Wissenschaft des Zählens ist. Die Wissenschaft der Anzahl und allem, was
aus Zahlen entsteht. Und hier haben wir jetzt genau das Weglassen von Zahlen.
Eben nur die, wie wir jetzt sagen, topologische Information spielt eine
Rolle. Die Länge der Brücken und so weiter spielt keine Rolle mehr. Es spielt
nur die genaue Anordnung der Brücken eine Rolle. Und das war eben eine große
Einsicht, die Euler hier gelang und ist deswegen wissenschaftsgeschichtlich
bedeutend. Und damit der Anfang vielleicht auch des Gebiets der Topologie, dass das
noch auf schwierigere geometrische Anordnungen erweitert, dieses Prinzip, dass
man metrische Information, Abstandsinformation, genaue Lageinformation
aus der Geometrie entfernt und nur über Information redet, die unter kleinen
Verformungen gleich bleibt. So kann man sich hier bei den Brücken
vorstellen, wenn die Landmassen sich etwas verformen würden, wäre das Problem,
solange die Brücken intakt bleiben, wäre das Problem immer das gleiche. Und damit
entsteht also Grafentheorie als eine mathematische Theorie, die nur diese eine
Definition zugrunde liegen hat. Man hat die Ecken und Kanten dazwischen und man
fragt sich jetzt vielleicht, was man über so eine einfache Struktur überhaupt
beweisen kann. Es gibt ja gar keine Axiome, womit soll man also arbeiten? Und
da können wir an der Stelle mal David Hilbert zitieren, der 1900 auf dem
Internationalen Kongress der Mathematiker, als er auch die Hilbert-
Probleme besprach, in seiner Vorrede sagte, dass es, solange es Probleme gibt
in einem mathematischen Gebiet, dieses mathematische Gebiet am Leben ist. Es
lebt also von den Problemen und von den Mathematikerinnen, die sich mit diesen
Problemen beschäftigen und sie lösen und daraus neue Probleme erschaffen.
Also schauen wir uns mal vielleicht ein paar klassische Probleme der
Grafentheorie an. Das eine haben wir jetzt schon nach Euler benannt. Das ist
eigentlich nur die Abstraktion von Eulers Königsberger Spaziergangsproblem
auf beliebige Grafen. Also ein Weg in einem Grafen ist vielleicht die erste
Definition der Grafentheorie, ist so eine Ansammlung von Kanten, so dass die erste
Kante und die zweite Kante genau eine Ecke gemeinsam haben und die zweite und
die dritte Kante haben eine Ecke gemeinsam, so dass man die Kanten in der
Reihenfolge ablaufen kann und dabei immer an einer Ecke von einer Kante auf
die nächste Kante wechselt. Also eine ganz natürliche Definition, das was man
sowieso einen Weg nennen würde und was auch in Königsberg auf dem Königsberggrafen
ein Weg ist. Und ein Eulerweg ist jetzt ein Weg in einem Grafen, der jede Kante
genau einmal benutzt. Und ein Kreis in einem Grafen ist ein Weg, der wieder zum
Anfang zurückkommt. Und ein Eulerkreis ist dementsprechend natürlich ein Eulerweg,
der auch ein Kreis ist, also ein Spaziergang in Königsberg oder auf
irgendeinem Grafen, der jede Kante genau einmal benutzt und wieder zum
Anfangspunkt zurückkommt. Und Euler hat dann halt schon im 18. Jahrhundert alle
Fragen dazu beantwortet. Und er nutzte dazu, nächste Definition, den Grad einer
Ecke. Der Grad einer Ecke ist die Anzahl von Kanten, die dort ankommen
beziehungsweise abgehen. Und wir hatten ja schon diskutiert, dass es darauf
ankommt, ob gerade von Ecken, ungerade oder gerade sind. Also hier haben wir jetzt den
ungerade und gerade gerade. Und damit es einen Eulerschen Kreis geben kann, muss
zum Beispiel jeder Grad in dem Grafen gerade sein, weil man an jedem Landmasse,
an jeder Ecke, an der man ankommt, auch wieder weggehen muss. Und deswegen
muss sie eine gerade Anzahl von Nachbarn haben, wie man sagt. Die Nachbarn sind die
anderen Ecken, die über eine Kante mit einer Ecke verbunden sind. Und damit wird
dieses Problem als gelöst angesehen. Und das ist auch, denke ich, einsichtig. Also
warum ist Eulers Problem mit dieser komischen Charakterisierung, mit der
Anzahl von Kanten, die eingehen und ausgehen, gelöst? Naja, die eine Sache zu
schauen, ob jede Ecke eine gerade Anzahl von Nachbar-Ecken hat oder eine gerade
Anzahl von Kanten, die bei ihr ankommen hat, ist etwas ganz Einfaches. Das kann
man durch einfaches Abzählen lösen. Während das Aufsuchen dieser Eulerschen
Kreise eben ein kombinatorisch schwieriges Problem ist, wo man sich
erst mal hinsetzen würde und herumprobieren. Und so hat man ein
schwieriges Problem, also eine Suche auf irgendwelchen Wegen in dem Grafen durch
ein einfaches Problem, ein einfaches Abzählproblem ersetzt. Und in der
Mathematik hat man oft dieses Ersetzen von einem schwierigen Problem durch ein
anderes schwieriges Problem. Das kann auch schon eine mathematische Einsicht
sein. Aber hier ist noch eine viel bessere Einsicht, dass man ein schwieriges
Problem durch ein einfaches Problem ersetzt. Und das würde man dann eine
Lösung nennen. Also ein schwieriges Problem durch ein schwieriges Problem zu
ersetzen, das nennt man eine Charakterisierung. Und ein schwieriges Problem durch ein
einfaches Problem zu ersetzen, das nennt man eine Lösung. Also dieses Problem mit
den Eulerschen Kreisen ist gelöst. Aber man kann das Problem ganz wenig
abändern und schon hat man wieder ein schwieriges Problem.
Man könnte zum Beispiel Hamilton-Kreise suchen und da ändert man die
Fragestellung. Man will jede Ecke genau einmal besuchen.
Also man will auf dem Grafen rumlaufen, man sucht wieder einen Weg oder einen
Kreis, der jede Ecke genau einmal besucht. In Königsberg zum Beispiel ist es ganz
einfach. Da müsste man nur jede Landmasse einmal besuchen oder eine Bar auf jeder
der Landmassen. Und das ist einfach. Man läuft einfach von Norden auf die Insel
nach Süden und dann nach Osten und hat jede Landmasse besucht. Also hierbei
benutzt man jetzt nicht mehr alle Brücken, sondern man will nur jede
Landmasse einmal besuchen. Wo ich das jetzt so sage, fällt mir noch etwas auf,
das ich nicht erwähnt habe. Natürlich muss es überhaupt Wege geben für
Eulersche oder Hamiltonsche Kreise. Wenn man jetzt einen Grafen hat, wo es einen
Bereich gibt, der überhaupt nicht mit einem anderen Bereich des Grafen
verbunden ist, so wie stelle man sich vor, man legt einfach zweimal so eine
U-Bahn-Karte von London nebeneinander, dann gibt es keine Bahn, die von der einen
Kopie von London zu der anderen Kopie von London fährt, weil ich einfach nur zwei
Karten nebeneinander gelegen habe und die nicht verbunden sind.
Das nennt man dann einen nicht verbundenen Grafen. Und alles, was ich heute erzähle,
handelt über verbundene Grafen, in denen man also von jeder Ecke zu jeder
anderen Ecke irgendwie entlang der Kanten überhaupt kommen kann.
Okay, aber das nur für die Leute, die sich vielleicht etwas darüber gewundert
haben. Also diese Hamilton-Kreise wollen also jede Ecke genau einmal
besuchen. Zum Beispiel könnte man das auf dem Ikosaeder spielen.
Man könnte also so einen platonischen Körper nehmen, sagen wir mal so ein
Ikosaeder, und dann fängt man an irgendeiner Ecke an und man will jetzt
jede Ecke des Ikosaeders besuchen und bewegt sich nur entlang der Kanten und
das geht. Ja, das kann man schaffen. Und das wurde sogar mal als Rätselspiel
verkauft. Ich schaue mal, ob ich da ein gemeinfreies Bild finde oder euch einen
Link in die Shownotes-Tour. Das konnte man so kaufen als Spiel, bei dem man so
seinen Weg markieren sollte auf dem Ikosaeder. Und das kann man natürlich
auch für andere platonische Körper fragen. Und man kann sich überlegen, dass
das auf jedem platonischen Körper geht. Können wir ja mal anfangen mit so einem
Tetraeder uns das vorzustellen. Naja, ich löse das jetzt nicht. Ich will euch den
Spaß nicht verderben, das selbst auszuprobieren. Und der Ikosaeder ist dann
der schwerste, der Endgegner sozusagen. Aber fang mal mit dem Tetraeder an.
Da ist es ganz einfach. Also man nimmt einen Tetraeder und will entlang jeder
Ecke einmal besuchen, indem man entlang der Kanten läuft.
Daher kommen übrigens auch diese Begriffe Ecken und Kanten. Denn eine
weitere Quelle von interessanten Graphen sind die Graphen von Polyedern. Zum
Beispiel solchen platonischen Körpern oder anderen Polyedern, die Ecken haben
und Kanten, die manche der Ecken verbinden. Und daher auch diese
Terminologie. Und als ich mich nach diesem Ikosaeder-Spiel mal informiert
habe, da habe ich ein interessantes Journal gefunden. Da gibt es das Journal
of Game and Puzzle Design. Das ist so ein kleines Journal. Das hat leider nur sechs
Ausgaben jemals produziert. So in den 2015, 16, 17er Jahren irgendwie. Und das
PDF von allen Ausgaben zusammen sollte 25 Dollar kosten. Das habe ich mir jetzt
noch nicht gekauft. Aber vielleicht wünsche ich mir das mal zu meinem
Geburtstag oder so. Ganz interessantes Journal. Das verlinke ich euch mal.
Naja, jedenfalls ist es bei diesen Hamilton-Kreisen ganz anders als bei den
Euler-Kreisen. Denn ein Mathematiker oder Computerwissenschaftler namens Karp hat
in den 70er Jahren des 20. Jahrhunderts gezeigt, dass es NP schwer ist, zu
bestimmen, ob ein gegebener Graph einen solchen Hamilton-Kreis hat.
Das bedeutet, der Algorithmus, der einfach alle Kreise durchgeht und schaut, bei
jedem erfüllt er die Bedingung, dass er jede Ecke einmal besucht oder tut er es
nicht, der ist zwar ziemlich ineffizient, aber das ist schon ein bester Algorithmus.
Also es gibt kein signifikant für große Graphen besseren Algorithmus, als
einfach alle Kreise auszuprobieren. Insbesondere kann es keine einfach zu
berechnende Formel geben. Denn wenn es so eine Formel geben würde, naja, zählt hier
das ab, zählt das ab, zählt zusammen und guckt, ob es gerade oder ungerade ist, dann
wäre das ja ein viel einfacher Algorithmus. Und das ist also schlechte
Nachrichten für diese Hamilton-Kreise. Also haben wir jetzt in der Graphen-Theorie
ein begründendes Problem, was ganz einfach ist. Euler hat die
Graphen-Theorie erfunden und gleich das begründende Problem gelöst und damit
die Graphen-Theorie begründet. Und wenn wir das Problem leicht abändern, also wie
so dual Ecken durch Kanten ersetzen und Kanten durch Ecken, dann kommen wir auf
das Problem der Hamilton-Kreise, dass NP schwer ist und dass man als Spiel
vermarkten kann. Ja, und so ist es. Und das ist die klassische Graphen-Theorie.
Und es gibt viele angewandte Probleme aus der Graphen-Theorie. Natürlich will man
in konkreten Graphen eine beste Route finden, einen kürzesten Weg finden oder
vielleicht einen Graphen malen. Und das ist eben das, womit sich die
Graphen-Theorie heutzutage beschäftigt. Und jetzt habe ich hier schon wieder ein
ganz schönes Weilchen geredet, deswegen höre ich jetzt mal lieber auf. Aber ich
plane noch eine weitere Folge zur Graphen-Theorie, in der ich mal versuche,
so ein bisschen einen Einblick zu geben in modernere Aspekte der Graphen-Theorie.
Also was kann man denn heutzutage machen? Wohin hat sich das entwickelt in den
Zeiten seit Euler? Aber dazu muss ich noch ein bisschen arbeiten. Das kommt dann
später in diesem Kanal. Also bis dahin wünsche ich euch eine gute Zeit. Bis bald.
Macht's gut!
Vielen Dank für diese tolle Folge. Sie war richtig spannend anzuhören (obwohl mir eigentlich fast alle genannten Topics schon bekannt sind), weil man sich wunderbar nebenher die Graphen vorstellen konnte. Gerne mehr zu Graphen, zB fällt mir spontan ein der Satz von Kuratowski oder selbst-komplementäre Graphen
Wie immer super interessant! Vielleicht hätte man auch über die Verbindung zw Graphen und Matrizen reden können. Wie die beiden Repräsentationen verschiedene Zugänge zum selben Thema erlauben.