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:
Einleitung
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.
 
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]