Analyse von linklosen Graphen auf Donut-Oberflächen

Graphen sind wie Punkte, die durch Linien verbunden sind. Man kann sie sich wie Zeichnungen aus Punkten und Pfaden vorstellen. Einige dieser Zeichnungen können sich drehen und wenden, ohne sich zu verheddern, und heissen linklos. Stell dir vor, du willst diese Graphen auf einer donuts-förmigen Fläche zeichnen. Es scheint einfach, aber da gibt's einen Twist (Wortspiel beabsichtigt). Wenn der Graph sich beim Zeichnen auf dem Donut verheddert, wird er zu einem verlinkten Graphen. Diese Studie dreht sich darum herauszufinden, welche Graphen ohne Verheddern auf einem Donut gezeichnet werden können, besonders wenn die Graphen nicht miteinander verlinkt sind.

#Hintergrund: Graphen und ihre Typen

Um zu verstehen, was hier abgeht, müssen wir ein paar grundlegende Begriffe klären.

• Planare Graphen: Das sind Graphen, die auf einer flachen Fläche gezeichnet werden können, ohne dass sich die Linien kreuzen. Stell dir vor, du malst mit Buntstiften auf Papier.

• Toroidale Graphen: Das sind Graphen, die auf einer donuts-förmigen Fläche gezeichnet werden können, ohne dass sich die Linien kreuzen. Es ist, als würdest du versuchen, dein Kunstwerk mit Buntstiften auf einem aufblasbaren Poolspielzeug zu zeichnen.

• Linklose Graphen: Stell dir zwei Linien vor, die sich umeinander wickeln können, ohne einen Knoten zu bilden. So sieht linkslos aus. Das ist wichtig, weil wir wollen, dass unsere Graph-Zeichnungen sich nicht verheddern.

In der Welt der Graphen gibt es einige, die natürlicherweise komplexer sind, während andere einfach gestrickt sind. Wenn ein Graph auf einem Donut gezeichnet werden kann, ohne dass sich Linien kreuzen, nennt man ihn toroidal. Wenn er auf diesem Donut gezeichnet werden kann, ohne dass sich Linien ineinander verheddern, ist er linklos oder nicht intrinsisch verlinkt (kurz nIL).

#Die grosse Frage

Die Frage, die wir beantworten wollen, ist: Wenn wir einen Graphen haben, der auf einem Donut gezeichnet werden kann und auch linklos ist, können wir garantieren, dass wir ihn ohne Verheddern auf einer standardmässigen Donutform zeichnen können?

Bisher wissen wir, dass für kleinere Graphen (mit bis zu 9 Punkten), wenn sie auf dem Donut gezeichnet werden können und Verheddern vermeiden, können wir sicher sagen, dass sie auch auf einer standardmässigen Donutform gezeichnet werden können. Aber was ist mit grösseren Graphen?

#Links auf dem Donut

Lass uns einen Moment über Links reden. Links sind wie diese nervigen Momente, wenn zwei Leute versuchen, sich in einem Flur zu überholen und dann miteinander verheddert sind.

• Linkzahl: Es gibt eine Möglichkeit, zu messen, wie verheddert zwei Wege sind. Wir können zählen, wie sich diese Wege überkreuzen. Wenn sie sich auf bestimmte Weise kreuzen und drehen, vergeben wir ihnen Werte. Am Ende des Tages, wenn der Gesamtwert nicht Null ist, sind sie verheddert.

#Erforschung von Graph-Familien

Wir können Graphen nach gemeinsamen Merkmalen gruppieren, ähnlich wie eine Freundesgruppe mit ähnlichen Hobbys.

• Minor-Closed Families: Das sind Gruppen von Graphen, die ihre Natur nicht ändern, wenn du einige ihrer Teile entfernst oder verkleinerst. Wenn du Teil dieses Clubs bist, kannst du nicht Teil eines anderen Clubs sein, der bestimmte Mitglieder nicht erlaubt.

Wir haben zwei Hauptclubs in unserer Studie: den Club der toroidalen Graphen und den Club der linklosen Graphen. Alle linklosen Graphen sind also auch toroidale Graphen, aber nicht alle toroidalen Graphen sind linklos. Stell dir vor, du bist ein Katzenmensch; alle Katzenmenschen lieben Haustiere, aber nicht alle Haustierliebhaber bevorzugen Katzen.

#MaxnIL Graphen und ihre Bedeutung

Manchmal finden wir spezielle Graphen, die ganz oben in der Rangfolge stehen. Diese nennt man MaxnIL-Graphen. Sie sind linklos und können keine zusätzlichen Kanten haben, ohne verlinkt zu werden. Sie sind wie die Chefs in der linklosen Graphen-Gemeinschaft.

Der Grossteil unserer Studie konzentriert sich auf diese MaxnIL-Graphen, denn wenn wir herausfinden können, wie man sie linkslos auf einem Donut zeichnet, können wir auch rückwärts prüfen, ob das für alle anderen Graphen gilt.

#Toroidale Obstruktionen

Bei der Erforschung der Welt der toroidalen Graphen finden wir einige, die nicht in die linklose Beschreibung passen. Diese heissen toroidale Obstruktionen, und sie sind wie die unglücklichen Partyeinladungen, die den Spass verderben.

Bisher haben wir einige toroidale Obstruktionen entdeckt, die sich nicht linkslos ohne Verdrehung zeichnen lassen. Die kleinste hat 8 Punkte und ist die erste, die wir aus dem linklosen Club ausschliessen müssen.

#Finden von MTN-Graphen

Um die grosse Frage zu beantworten, müssen wir herausfinden, welche Graphen linklos auf einem Donut ohne Verheddern gezeichnet werden können. Wir fangen mit kleineren Graphen an und arbeiten uns hoch.

Für die kleineren Graphen (wie die mit 6 oder 7 Punkten) können wir sicher sagen, dass sie linklos sind. Je höher wir klettern, desto komplexer wird die Herausforderung, besonders wenn wir auf Graphen der Ordnung 9 stossen.

#Die Suche nach Linklosigkeit

Wenn wir tiefer in Graphen der Ordnung 9 eintauchen, nutzen wir verschiedene Techniken und Beobachtungen. Wir haben bereits eine Vorstellung davon, dass bestimmte Graphen nicht verlinkbar sind.

Durch eine Reihe cleverer Schlussfolgerungen können wir feststellen, dass von den zwanzig MaxnIL-Graphen der Ordnung 9 nur vier nicht ohne Verheddern auf dem Donut gezeichnet werden können. Diese vier Problemchen machen unser Leben interessanter, aber auch unsere Forschung komplizierter.

#Werkzeuge des Handels

Während dieser Reise verwenden wir verschiedene Algorithmen, um den Überblick darüber zu behalten, mit welchen Graphen wir es zu tun haben. Durch die Anwendung dieser Algorithmen können wir Bedingungen umreissen, die bestimmen, ob ein Graph linkslos gezeichnet werden kann oder nicht.

Ein hilfreicher Algorithmus hilft uns, linklose Graphen anhand ihrer Pfadkreuzungen zu identifizieren. Das ist entscheidend, weil es uns erspart, jeden Graph per Hand zu zeichnen. Schliesslich hat nicht jeder die Zeit dafür!

#Nachweis der Linklosigkeit

Jetzt, wo wir ein solides Verständnis der Graphen haben, mit denen wir arbeiten, ist es an der Zeit zu beweisen, dass ein Graph linklos ist. Wir verwenden unsere frühere Definition von Steigungen und Kreuzungen und können einen kleinen Test aufstellen. Wenn die Liste, die unser Algorithmus zurückgibt, keine Konflikte oder Verwirrungen zeigt, können wir mit Zuversicht sagen, dass der Graph linklos ist.

#Die Ergebnisse

Nach unzähligen Stunden des Zeichnens, Prüfens und Testens haben wir eine vollständige Sammlung von MTN-Graphen für die Ordnungen von 6 bis 9 zusammengestellt. Die Ergebnisse zeigen, dass all diese Graphen ohne Verheddern auf einem Donut gezeichnet werden können, also feiert ordentlich!

#Zukünftige Richtungen

Nachdem wir die kleineren Graphen angepackt haben, wollen wir jetzt sehen, ob wir diese Arbeit auf grössere Graphen ausdehnen können. Wir glauben, dass es eine gute Chance gibt, dass alle toroidalen, nIL-Graphen linkslos auf einem Donut gezeichnet werden können.

Wir haben bedeutende Fortschritte gemacht, aber die Zukunft wird viel Arbeit erfordern. Das Verständnis der verbotenen Minor für diese Grapharten könnte uns letztendlich zu stärkeren Schlussfolgerungen über ihr linkloses Verhalten führen.

#Fazit

Zusammenfassend können wir sagen, dass wir einen spannenden Ausflug in die Welt der Graphen auf Donuts gemacht haben und entdeckt haben, wie diese mathematischen Formen ohne Verheddern existieren können. Mit unseren Erkenntnissen haben wir jetzt ein besseres Verständnis dafür, wie diese Graphen auf einer toroidalen Fläche funktionieren, und während es noch mehr zu entdecken gibt, sind wir froh, eine Sache bewiesen zu haben: Nicht alle Graphen wollen sich verheddern, und das ist eine Erleichterung.