Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Die raffinierte Lösung

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.
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 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]