Mathematik: 4-reguläre planare Einheits-Dreieck-Graphen
Released by matroid on Mo. 18. November 2019 21:17:18 [Statistics]
Written by Slash - 510 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Wie man 4-reguläre planare Graphen nur aus kongruenten gleichseitigen Dreiecken konstruiert

Lassen sich kongruente gleichseitige Dreiecke in der Ebene ohne Überschneidungen derart aneinanderlegen, dass sich immer genau zwei Ecken berühren ohne dabei größere Dreiecke zu bilden? Und wenn ja, wie viele Dreiecke benötigt man mindestens dafür?
Eine Aufgabe, die mit entsprechendem Material, etwa kleine Dreiecke aus Pappe, sogar Kinder verstehen und angehen können, deren Lösung aber ganz schön raffiniert ist.


Mit Dreiecken aus Pappe scheint die Aufgabe klar. Ein Graphentheoretiker möchte jedoch auch den Spezialfall ausschließen bei dem Ecken genau auf Kanten liegen, denn nur so ist der Graph planar. Er sucht daher nach einem Existenzbeweis bzw. der minimalsten Knotenzahl eines 4-regulären planaren Einheitsdistanz-Graphen, dessen Knoten keine 180 Grad Winkel zwischen zwei Kanten besitzen. Ein planarer Einheitsdistanz-Graph wird auch Streichholzgraph genannt. Die Fragestellung geht zurück auf eine Arbeit von Heiko Harborth aus dem Jahr 1991 [1] und war seitdem ein offenes Problem. Lässt man auch größere Dreiecke bzw. 180 Grad Winkel an den Knoten zu, finden sich schnell zwei Lösungen mit je 42 Einheits-Dreiecken (Abb. 1). Das Dreieck \((A, B, C)\) zeigt eines der größeren Dreiecke.
Abbildung 1. Jeder Graph besitzt 42 Einheits-Dreiecke und ist aus sechs Kopien desselben
Teilgraphen (grau) aufgebaut. Jeder Teilgraph enthält zwei größere Dreiecke (violett).
Die Graphen in Abbildung 1 sind beide starr, können also nicht verformt werden wie z.B. eine Raute. Ob es noch weitere Lösungen mit 42 Einheits-Dreiecken oder sogar einer geringeren Anzahl gibt, ist nicht bekannt. Es ist zwar sehr unwahrscheinlich, doch einen Beweis dafür gibt es bislang nicht. Harborth zeigte in seiner Arbeit auch, dass mindestens 3800 Einheits-Dreiecke nötig sind, wenn man erlaubt, dass Ecken auch auf Kanten liegen dürfen. Er konstruierte dazu den starren Teilgraphen \(G_1\), der aus 38 Einheits-Dreiecken besteht und spiegelsymmetrisch zur Geraden \(BE\) ist (Abb. 2). 100 Kopien dieses Teilgraphen lassen sich zu einem 4-regulären Ring-Graphen verbinden (Abb. 3). Dieser Ring ist, wie auch \(G_1\) selbst, nicht-planar und starr. Beweise der Existenz und Nicht-Planarität von \(G_1\) und des Ring-Graphen finden sich hier [1].
Abbildung 2. Der nicht-planare starre Teilgraph \(G_1\). Der Abstand \(\overline{GH}\) ist zu gering, um die vier Rauten als solche erkennen zu können. Es ist \(\overline{GH}\approx 0,0017\) und \(\gamma\approx 119,90^\circ\) (vgl. Abb. 5). Die oberen und unteren Knoten der Rauten liegen genau auf den Dreieckskanten.
Abbildung 3. Detail des starren nicht-planaren 4-regulären Ring-Graphen aus 3800 Einheits-Dreiecken. Eine Vektorgrafik des ganzen Graphen findet sich hier.

Die Lösung: einfach, aber genial

Um das Problem zu lösen, muss das Rad bzw. der Graph nicht neu erfunden werden. Ein geschickte Modifikation des Teilgraphen \(G_1\) genügt. Durch eine Veränderung der rechten Seite wird der neue Teilgraph \(G_2\) flexibel, und diese Beweglichkeit ist der Schlüssel zur Planarität (Abb. 4). Da diese Idee nicht von mir stammt, darf ich mit Recht behaupten, dass sie ganz schön raffiniert ist - einfach, aber genial. Auch \(G_2\) ist spiegelsymmetrisch zur Geraden \(BE\). In den Zoom-Kästchen sieht man gut, wie sich durch die Modifizierung die oberen und unteren Knoten der Rauten von den Dreieckskanten lösen. Die Rauten sind jedoch weiterhin so schmal, dass der Abstand \(\overline{GH}\) in dieser Auflösung nicht zu erkennen ist. Die Tabelle in Abbildung 5 zeigt eine Übersicht der approximierten Werte der Winkel und Distanzen beider Teilgraphen.
Abbildung 4. Der flexible planare Teilgraph \(G_2\). Hier liegen keine Knoten mehr auf anderen Kanten. Es ist \(\overline{GH}\approx 0,000063\) und \(\gamma\approx 119,996^\circ\) (vgl. Abb. 5).
Satz: Es werden mindestens 6422 Einheits-Dreiecke benötigt, um einen 4-regulären planaren Einheitsdistanz-Graphen zu konstruieren, der keine größeren Dreiecke enthält.
Beweis: Wir arrangieren 38 Einheits-Dreiecke so in der Ebene, dass wir den Teilgraphen \(G_2\) erhalten. Dieser besitzt (wie auch \(G_1\)) nur Knoten der Grade 2 und 4. Die 2-gradigen Knoten liegen dabei exakt auf den Geraden \(g_{1}\) und \(g_{2}\), welche sich rechts von \(E\) schneiden. \(G_2\) ist flexibel und spiegelsymmetrisch zur Geraden \(BE\). Sei \(n\) eine ganze Zahl und \(\frac{360^\circ}{n}\) der Schnittwinkel zwischen \(g_{1}\) und \(g_{2}\). Stellen wir uns jetzt die beiden Geraden als Schienen vor, auf denen die 2-gradigen Knoten mit Ausnahme von \(D\) und \(F\) beweglich gelagert sind. \(D\) und \(F\) werden dabei ganz aus der Schienenführung herausgenommen und können sich frei in alle Richtungen über die Schienen bewegen. Wegen seiner Flexibilität können wir den Teilgraphen \(G_2\) nun geringfügig auf den Schienen hin- und herschieben, wobei sich \(D\) und \(F\) auf und ab bewegen. Bei einer solchen Bewegung bleibt kein Winkel in \(G_2\) konstant. Wird nun einer der Winkel \(\alpha\), \(\beta\), oder \(\gamma\) kontinuierlich ein wenig um seinen Wert aus der Tabelle in Abbildung 5 verändert, dann schneidet die Bahn von \(D\) bzw. \(F\) irgendwann \(g_{2}\) bzw. \(g_{1}\). Diese Schnittpunkte lassen sich nicht genau angeben, doch sie müssen existieren. Während dieser Bewegung muss sichergestellt werden, dass kein Knoten vom Grad 4 eine andere Kante oder eine der Geraden schneidet. Das kleineste \(n\) für das dies möglich ist, ist \(n=169\). Aufgrund der Spiegelsymmetrie von \(G_2\) können wir nun 169 Kopien dieses Teilgraphen so zu einem Ring zusammenfügen, dass die 2-gradigen Knoten \(A\) und \(C\), sowie \(F\) und \(D\) jeweils paarweise zu 4-gradigen Knoten zusammenfallen (Abb. 6). So erhalten wir einen 4-regulären planaren Ring-Graphen aus \(169\cdot38=6422\) Einheits-Dreiecken, der keine größeren Dreiecke besitzt. Dieser Ring-Graph ist starr. Sein Mittelpunkt ist der Schnittpunkt der Geraden \(g_{1}\) und \(g_{2}\).\(\square\)
Abbildung 5. Winkel und Distanzen der Teilgraphen \(G_1\) und \(G_2\).
Abbildung 6. Detail des starren 4-regulären planaren Ring-Graphen aus 6422 Einheits-Dreiecken.
Der Existenzbeweis des Ring-Graphen aus dem Harborth-Teilgraphen \(G_1\) ist sogar etwas einfacher, da er starr ist und sich die Geraden \(g_{1}\) und \(g_{2}\) in einem Winkel von genau 3,6 Grad schneiden. Einen Größenvergleich beider Ring-Graphen kann man sich hier ansehen.
Es existiert auch ein planarer 4-regulärer Einheits-Dreieck-Graph mit 100-facher Rotations- symmetrie. Dieser Ring-Graph besteht aus 9200 Einheits-Dreiecken und wird mit Kopien des Teilgraphen \(G_3\) konstruiert (Abb. 7). Auch \(G_3\) besitzt sehr geringe Abstände zwischen Knoten und Kanten. Ohne Computerunterstützung wäre die Berechnung der Teilgraphen \(G_2\) und \(G_3\) nicht möglich gewesen [3]. Herr Harborth hingegen kam noch mit Papier und Bleistift aus.
Abbildung 7. Der planare Teilgraph \(G_3\). Ein Detailbild des ganzen Graphen findet sich hier.

Andere Formen neben Ringen

Eine schwierige und noch offene Frage ist, ob 4-reguläre planare Graphen aus Einheits-Dreiecken ohne größere Dreiecke auch noch in anderen Formen außer Ringen existieren können. Für nicht-planare Exemplare wurde bereits eine Antwort gefunden. In \(G_1\) liegen die Knoten auf der Geraden \(BE\) alle spiegelsymmetrisch zu \(g_3\), der Mittelsenkrechten zu \(BE\). Sein nun \(G_4\) der Graph, den wir erhalten, wenn wir alle Knoten die in \(G_1\) zwischen \(BE\) und \(g_2\) liegen an \(g_3\) spiegeln, wodurch \(g_1\) und \(g_2\) parallel werden (Abb. 8). \(G_5\) sei der Graph, den wir erhalten, wenn wir \(G_4\) an \(BE\) spiegeln.
Abbildung 8. Der starre nicht-planare Teilgraph \(G_4\). Die Geraden \(g_1\) und \(g_2\) sind parallel.
Die beiden neuen Teilgraphen \(G_4\) und \(G_5\) können wir jetzt als eine Art Adapter benutzen, um mit \(G_1\) konstruierte Kreiselemente in wechselnder Richtung aneinanderzusetzen. Dadurch werden unendlich viele andere Formen neben Ringen möglich (Abb. 9). Das kann man sich ungefähr so vorstellen, als wenn man eine ebene geschlossene Strecke für eine Modelleisenbahn auslegt und nur Links- und Rechtskurven als Schienenelemente zur Verfügung hat.
Abbildung 9. Zwei nicht-planare Beispiele anderer Formen neben Ringen.

Quellenangaben, weitere Informationen und Danksagungen

[1] Heiko Harborth, Plane four-regular graphs with vertex-to-vertex unit triangles, Discrete Mathematics 97 (1991), 219-222. (PDF) [2] Mike Winkler, Peter Dinkelacker, Stefan Vogel, 4-Regular Planar Unit Triangle Graphs without Additional Triangles, Geombinatorics Quarterly, Volume XXIX, Issue 2, October 2019, pp. 72-77. (PDF) [3] Stefan Vogel, Matchstick Graphs Calculator (MGC), a software for the construction and calculation of unit distance graphs and matchstick graphs, (2016–2019). (MGC) • Dies ist ein weiterer Artikel in dem Lösungen zu offenen Problemen aus der Graphentheorie präsentiert werden, die sich aus der gemeinsamen Arbeit von haribo, StefanVogel und mir in unserem Streichholzgraphen-Thread ergeben haben. Dieser Artikel orientiert sich am Original in englischer Sprache, welches im Oktober 2019 bei Geombinatorics Quarterly erschienen ist. Die original Version ist als PDF verfügbar [2]. • haribo ist der eigentliche Star dieses Artikels, denn er war es, der die entscheidende Idee zur Konstruktion solcher Graphen hatte (hier). Wie man im Thread nachlesen kann, hatte ich schon nicht mehr an eine Lösung geglaubt. Die Ideen zu den Teilgraphen in den Abbildungen 4, 7 und 8, wie auch die Idee zur Konstruktion der Nicht-Ringe mit dem Harborth-Teilgraphen, stammen alle von haribo. StefanVogel war wie immer durch seine Berechnungen der Graphen beteiligt und ganz besonders am Finden der kleinsten Lösung. Die tolle Beweis-Idee mit den Schienen stammt auch von ihm. Wer es ganz genau wissen will, der kann unseren Thread durchgehen, der ja eine Chronologie unserer Arbeit darstellt. • Fairer Weise muss man darauf hinweisen, dass die minimale Lösung so geringe Abstände zwischen Knoten und Kanten besitzt (vgl. Abb. 5), dass eine Konstruktion aus kleinen Papp-Dreiecken kaum umzusetzen wäre. Die große Anzahl der Dreiecke ist natürlich eine weitere Hürde für den Hobby-Bastler. • Der erste Graph mit den in der Aufgabenstellung geforderten Eigenschaften wurde am 19.09.2018 konstruiert (hier). Er besteht aus 63072 Dreiecken und hat die Symmetrie eines regelmäßigen 292-Ecks. Ein wahres Monstrum. Seine Größe wurde allerdings willkürlich gewählt, da es hier erstmal nur um einen Existenzbeweis ging. • Ich bedanke mich bei unserem ehemaligen Mitglied cis für seine Unterstützung bei der Umsetzung der Grafiken mit TikZ/PGFplots. (siehe auch hier) Die Bilder in diesem Artikel sind allerdings PNG's dieser Grafiken. • Und - last but definitely not least - bedanke ich mich bei haribo und StefanVogel für die angenehme Zusammenarbeit im Thread, die hoffentlich noch viele Früchte tragen wird. Viele Grüße, Slash

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfpdf-Datei zum Artikel öffnen, 273 KB, vom 08.11.2019 12:22:59, bisher 273 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 510
 
Aufrufstatistik des Artikels
Insgesamt 89 externe Seitenaufrufe zwischen 2019.11 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://google.com2224.7%24.7 %
https://www.ecosia.org33.4%3.4 %
https://google.de4752.8%52.8 %
http://www.mikematics.de1213.5%13.5 %
https://www.bing.com33.4%3.4 %
https://duckduckgo.com22.2%2.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 80 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (26x)https://google.de
2020-2021 (21x)https://google.de/
2020-2021 (11x)https://google.com/
202103-03 (10x)https://google.com/search?client=firefox-b-m
2020-2021 (7x)http://www.mikematics.de/
2019-2021 (5x)http://www.mikematics.de/matheplanet-articles/

[Top of page]

"Mathematik: 4-reguläre planare Einheits-Dreieck-Graphen" | 2 Comments
The authors of the comments are responsible for the content.

Re: 4-reguläre planare Einheits-Dreieck-Graphen
von: Goswin am: Do. 21. November 2019 10:47:11
\(\begingroup\)Folgender Satz in der Einleitung war zumindest für mich völlig unverständlich, und ich konnte nur nach Lesen des Artikels mühsam herausfinden, was er bedeutet: "Lassen sich kongruente gleichseitige Dreiecke in der Ebene ohne Überschneidungen derart aneinanderlegen, dass sich immer genau zwei Ecken berühren ohne dabei größere Dreiecke zu bilden?" Gemeint ist anscheinend: "Lassen sich kongruente gleichseitige Dreiecke in der Ebene ohne Überschneidungen derart aneinanderlegen, dass jedes der Dreiecke an jeder seiner Ecken und nur dort genau eines der anderen Dreiecke berührt, ohne dass die Kanten mehrerer Dreiecke dabei größere Dreiecke bilden?" Aber so ganz sicher bin ich mir immer noch nicht.\(\endgroup\)
 

Re: 4-reguläre planare Einheits-Dreieck-Graphen
von: Slash am: Do. 21. November 2019 15:21:23
\(\begingroup\)Hallo Goswin, genauso ist es gemeint. 😄 Gruß, Slash\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]