Die Mathe-Redaktion - 20.11.2017 21:55 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-11-20 21:29 bb
Matheformeln mit MathML
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 932 Gäste und 33 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Der große Bruder des Harborth-Graphen
Freigegeben von matroid am So. 17. Juli 2016 17:57:58
Verfasst von Slash -   464 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Der große Bruder des Harborth-Graphen

In diesem Artikel stelle ich einen neuen 4-regulären Streichholzgraphen mit 108 Kanten vor. Dieser Graph - siehe rechts - wurde von StefanVogel, haribo und mir als Team im Verlauf unseres Streichholzgraphen-Threads hier auf dem Matheplaneten entdeckt und auch erstmals präsentiert. Er ist nach dem sehr ähnlich aussehenden Harborth-Graphen mit 104 Kanten das neue zweitkleinste bekannte Beispiel eines 4-regulären Streichholzgraphen, und löst damit den erst kürzlich hier präsentierten Graphen mit 114 Kanten ab. Wie sich der neue Graph in wenigen Schritten aus dem Harborth-Graphen konstruieren lässt, und dass beide Graphen wirklich existieren, soll hier gezeigt werden.

Inhalt

1. Reguläre Streichholzgraphen
2. Starrheit und Flexibilität
3. Die Existenz des Harborth-Graphen
4. Die Konstruktion des neuen Graphen
5. Die Historie des neuen Graphen
6. Anmerkungen
7. Bibliographie

Die Abschnitte 1 und 2 habe ich aus meinem ersten Artikel über Streichholzgraphen übernommen. Wer diesen schon kennt kann sie überspringen.
1. Reguläre Streichholzgraphen

Als Streichholzgraphen bezeichnet man planare Graphen, deren Kanten Einheitslänge besitzen und die sich nicht überschneiden. Regulär ist ein solcher Graph genau dann, wenn an jeden seiner Knoten gleich viele Kanten grenzen. Der Name Streichholzgraph rührt von dem Umstand her, dass man solche Graphen auch mit gleichlangen Streichhölzern auf einer flachen Oberfläche nachbilden kann. Eine besondere Herausforderung bei allen Arten von Streichholzgraphen ist stets, den kleinstmöglichen zu finden, der mit einer minimalen Anzahl an Kanten auskommt. Das folgende Bild zeigt die bis heute kleinsten bekannten n-regulären Streichholzgraphen für n = 1 bis 4.


Für alle n ≥ 5 existieren keine endlichen n-regulären Streichholzgraphen, wobei ein Beweis für den Fall n = 5 erstmals 2011 (Sascha Kurz, Rom Pinchasi[3]) offiziell veröffentlicht wurde. Die Geschichte dieses Beweises ist allerdings etwas unübersichtlich und beginnt bereits 1982 bei Aart Blokhuis (siehe Anmerkungen). Für n = 5 und n = 6 existieren aber unendliche n-reguläre Streichholzgraphen mit einer unbegrenzten Anzahl an Knoten und Kanten. Der kleinste bekannte 4-reguläre Streichholzgraph mit 52 Knoten und 104 Kanten wurde 1986 von Heiko Harborth vorgestellt und auch nach ihm benannt. Ob es noch mindestens einen kleineren 4-regulären Streichholzgraphen als den Harborth-Graphen gibt, ist nach wie vor ein offenes Problem. Doch selbst ein anderer Graph mit 104 Kanten wäre schon eine kleine Sensation. Dass ein 4-regulärer Streichholzgraph mindestens 20 Kanten besitzen muss, zeigten Kurz und Pinchasi in einem 2014 veröffentlichten Artikel.

Leider fristen Streichholzgraphen in der Fachwelt bis heute ein eher stiefmütterliches Dasein. Das liegt wohl zum Teil darin begründet, dass die Thematik einerseits fast schon trivialer Natur ist, aber andererseits sich ihre mathematische Behandlung so extrem schwierig gestaltet. Es gibt in der mathematischen Landschaft wohl nicht viele vergleichbare Aufgabenstellungen, die selbst schon Kinder im Grundschulalter vollständig verstehen und auch praktisch behandeln können. Für mich macht aber gerade diese Ambivalenz den Reiz der Streichholzgraphen aus. Es würde mich freuen, wenn dieser Artikel dazu beiträgt auch andere für diese interessante und spannende Sache zu begeistern. Denn in Welt der Streichholzgraphen gibt es noch viel Neues zu entdecken.


2. Starrheit und Flexibilität

Was die mathematische Behandlung von Streichholzgraphen so schwierig macht, ist ihre mögliche Beweglichkeit bzw. Verformbarkeit. Man unterscheidet in der geometrischen Graphentheorie zwischen starren und flexiblen Graphen. Dazu betrachten wir im Folgenden nur Graphen mit Knotengraden > 1. Ist ein Graph starr, so können seine Kanten nicht gegeneinander bewegt werden ohne ihre Länge zu ändern oder sie von einem Knoten zu lösen. Ist ein Graph flexibel, so können seine Kanten und Knoten gegeneinander bewegt werden ohne die Kantenlängen oder Knotengrade zu verändern. Es gilt daher: Ist ein planarer Einheitsdistanz-Graph verformbar, so ist er flexibel, ansonsten ist er starr.

Das einfachste Beispiel eines starren Streichholzgraphen ist 2-regulär, besitzt drei Knoten und Kanten und hat die Form eines gleichseitigen Dreiecks. Das einfachste Beispiel eines flexiblen Streichholzgraphen ist ebenfalls 2-regulär, besitzt vier Knoten und Kanten und hat die Form eines Quadrats bzw. einer Raute.



Auch wenn die Beweglichkeit eines flexiblen Streichholzgraphen flächenmäßig begrenzt ist, so sind doch innerhalb dieser Grenzen die Möglichkeiten unendlich groß und es existieren unendlich viele Form-Variationen von ihm.

Dass auch der Harborth-Graph starr ist, folgt sofort aus einfachen geometrischen Überlgungen zur Beweglichkeit eines seiner Viertel-Teilgraphen. 2006 ermittelte Eberhard H.-A. Gerbracht erstmalig mit Hilfe eines Computeralgebrasystems die Minimalpolynome für die Koordinaten der Ecken des Harborth-Graphen. Die reellen Nullstellen dieser Minimalpolynome geben dann die jeweiligen Koordinaten der Knoten an. Für den Beweis der Existenz und der Starrheit des Harborth-Graphen ist diese komplizierte Betrachtung mit Polynomen allerdings nicht nötig.


3. Die Existenz des Harborth-Graphen

Wir werden zunächst die Existenz des Harborth-Graphen beweisen, und zwar mit einer einfachen geometrischen Methode. Der Harborth-Graph (Abb. links) besitzt eine zweifache Spiegelsymmetrie. Ein (4,2)-regulärer Teilgraph mit 26 Kanten, dessen Knoten vom Grad 2 auf zwei orthogonalen Geraden liegen, wird an diesen Geraden gespiegelt. Wenn wir nun die Knoten 1 und 2 in je zwei Knoten vom Grad 2 teilen, wird der zuvor starre Graph beweglich und kann stetig verformt werden. Für das Folgende wählen wir die Verformung derart, dass die Strecke zwischen den Knoten 7 und 8 kürzer und die Strecke zwischen den Knoten 3 und 6 länger wird (Abb. rechts). Wir drücken den Graphen quasi zusammen.



Die folgende Sequenz zeigt diesen Verformungsvorgang in fünf Bildern bis zum Zusammenfall der sich annähernden Kanten und Knoten. Man beachte: Die violetten und gelben Linien stellen nur sich verändernde Abstände und keine Kanten des Graphen dar. Es lässt sich gut erkennen, wie die violette Strecke zwischen den Knoten 1a und 1b stetig länger wird, bis sie schließlich zwei Kantenlängen misst und mit der horizontalen Symmetrieachse zusammenfällt. Die gelbe Strecke zwischen den Knoten 1a und 2a liegt zu Anfang auf der vertikalen Symmetrieachse und wird stetig kürzer, bis ihre Länge gleich Null ist und sie mit dem Knoten 4 zusammenfällt.



Wie lässt sich aber so die Existenz des Harborth-Graphen beweisen? Nun, wir können uns diesen Verformungsprozess jetzt rückwärts denken, indem wir den Rautenblock in Abb. 5 stetig auseinander ziehen, so dass wir einen (4,2)-regulären Graphen wie in Abb. 4 erhalten. Wegen der zweifachen Spiegelsymmetrie des Graphen, kann dieser stetig derart verformt werden, dass die Knoten 3, 4, 5, 6, sowie die Knoten 7 und 8 jeweils auf einer der sich rechtwinklig schneidenden Symmetrieachsen liegen, und die Knoten 1a und 1b, 2a und 2b, 1a und 2a, sowie 1b und 2b jeweils paarweise auf parallelen Geraden dazu liegen (Abb. links). Dies beweist, dass es möglich ist den Graphen genau so zu verformen, dass die Knoten 1a und 1b, sowie 2a und 2b jeweils in einem Punkt auf der vertikalen Symmetrieachse zusammenfallen (Abb. rechts). Der blaue Winkel beträgt dann ca. 18,57431690427 Grad. Aus dieser Betrachtung folgt auch sofort die Starrheit des Graphen.




4. Die Konstruktion des neuen Graphen

Ausgangspunkt ist der Harborth-Graph (Abb. 1). Wir drehen nun die blauen Kanten paarweise aufeinander zu, bis diese sich in einem Punkt treffen und mit den schwarzen Kanten eine sehr schmale Raute bilden (Abb. 2). Als nächstes drehen wir die roten Kanten so, bis diese jeweils parallel zu ihren benachbarten blauen Kanten ausgerichtet sind (Abb. 3). Im letzten Schritt fügen wir die vier neuen grünen Kanten zwischen die blauen und roten Kanten ein, sodass sich vier große Rauten bilden.



Der so entstandene (4,2)-reguläre Graph (Abb. 3 und 4) besitzt immer noch eine doppelte Spiegelsymmetrie. Um die Existenz des neuen 4-regulären Streichholzgraphen mit 108 Kanten (Abb. 5) zu beweisen, können wir daher dieselbe Methode anwenden, die wir zuvor beim Harborth-Graphen benutzt haben. Auch hier liegen die vier Knoten vom Grad 2 jeweils paarweise auf einer parallelen Gerade zu den sich rechtwinklig schneidenden Symmetrieachsen. Der einzige Unterschied besteht darin, dass die Knoten vom Grad 2 hier jeweils paarweise auf der horizontalen Symmetrieachse zusammenfallen. Der blaue Winkel misst dann ca. 20,13345437742 Grad. Genau wie der Harborth-Graph ist auch dieser Graph starr.





Zum Abschluss der neue 4-reguläre Streichholzgraph mit 108 Kanten im Großformat.





5. Die Historie des neuen Graphen

Der neue Streichholzgraph besitzt wirklich eine sehr spezielle Entstehungs- und Entdeckungsgeschichte, die im entsprechenden Thread auch jeder für sich selbst nachvollziehen und beurteilen kann. Wir sind uns auf jeden Fall einig darüber, diesen Graphen gemeinsam entdeckt zu haben.

Genau genommen beginnt die Geschichte des Graphen mit meinem Start des Threads am 17. Februar 2016, an dem sich haribo sofort mit großem Interesse beteiligte. Am 22. Februar schwenkte der Thread zu 4/n-regulären Streichholzgraphen um. Am 13. März kam dann StefanVogel dazu und half uns bei Prüfung und Berechnung der Geometrien neuer Graphen mit seiner selbst geschriebenen Software (siehe Anmerkungen). Am 30. März hat haribo zusammen mit einem Freund zum ersten Mal versucht den Harborth-Graphen zu modifizieren. Inzwischen hatten wir schon einige neue Minimalitätsrekorde zu den 4/n-regulären Streichholzgraphen aufgestellt. Am 21. April postete ich einige neue Ideen zu modifizierten Harborth-Graphen, die von Stefan überprüft wurden. Darauf aufbauend stellte Stefan am 24. April zum ersten Mal hier eine eigene Idee vor, die auch zum ersten Mal den neuen Graphen zeigt. Da Stefan den Graphen aber als nicht möglich getestet hatte, kümmerte sich keiner von uns weiter darum. Die Idee zu diesem Graphen geriet in Vergessenheit.

Am 27. Juni passierte dann etwas sehr Kurioses. Ich poste hier um ca. 5:30 Uhr morgens zwei vermeintlich neue Ideen für modifizierte Harborth-Graphen. Da die Ideen aber relativ einfach sind, bin ich den gesamten Thread noch einmal durchgegangen, um zu sehen, ob wir sie nicht doch schon einmal hatten. Nachdem ich Stefans früheren Beitrag gesehen hatte, habe ich meinen Beitrag gleich wieder gelöscht. Zum Glück war aber auch haribo gerade online und hatte meinen kurzen neuen Post mit den Graphen gesehen. Da auch er Stefans alten Beitrag nicht mehr im Gedächtnis hatte, hat er meinen vermeintlich neuen Graphen geprüft und im Gegensatz zu Stefan für möglich gehalten. Einige Tage und Beiträge später, am 3. Juli, waren wir drei uns dann absolut sicher, dass dieser neue Graph wirklich existiert, und Stefan in seinem ersten Test ein Fehler unterlaufen war. Man sieht, hätte auch nur ein Glied in dieser Kausalitätskette gefehlt - der neue Graph wäre wohl bis heute unentdeckt geblieben. Ende gut - Graph gut.

Viele Grüße, Slash


6. Anmerkungen

Wie man die Beweglichkeit eines Streichholzgraphen bestimmen kann, beschreibt Stefan in seinem Matheplanet Artikel "Beweglichkeit eines Streichholzgraphen bestimmen".

Die aktuell kleinsten bekannten Beispiele (4,n)-regulärer Streichholzgraphen gibt es auf dieser Seite von Erich Friedman[1] zu sehen.

Die Geschichte des Beweises der Nichtexistenz eines endlichen 5-regulären Streichholzgraphen ist etwas unübersichtlich und reicht von 1982 bis 2011. An dieser stelle möchte ich Sacha Kurz meinen Dank aussprechen, der auf meine Anfrage hin die Historie des Beweises sehr detailliert rekonstruiert hat. Im folgenden gebe ich seine eigene Kurzzusammenfassung an.

 * 1982 Aart Blokhuis; Beweis enthielt kleinere (Tipp-)fehler; Manuskript nie veröffentlicht und zwischenzeitlich länger verloren gegangen -> PDF
 * (<=2008 gefunden, 2009 final durch "Discrete Mathematics" abgelehnt) Sascha Kurz; länglicher, umständlicher Beweis; nie offiziell veröffentlicht -> PDF
 * 2009 Rom Pinchasi: kürzeren Beweis gefunden in Funktion als Referee für obige Einreichung => S. Kurz and R. Pinchasi: Regular matchstick graphs, The American Mathematical Monthly, Vol. 118, Nr. 3 (2011), Pages 264-267 (Wobei mein Beitrag an dem letztendlich veröffentlichten Beweis sehr überschaubar war.)
 * Alle Dateien habe ich unter http://www.wm-archive.uni-bayreuth.de/index.php?id=sk (2011) zur Verfügung gestellt.

Mein weiterer Dank geht an Eberhard H.-A. Gerbracht, der so freundlich war mir die Ergebnisse seiner Arbeit zum Harborth-Graphen[2] verständlich zu erklären und zusammenzufassen.

Alle in diesem Artikel verwendeten Bilder stammen von mir. Die Graphen wurden mit der CAD Software Solid Edge 2D-Drafting ST8 gezeichnet. Ich bedanke mich bei der Firma Siemens PLM Software, die dieses Programm schon seit vielen Jahren immer in der aktuellsten Version gratis zur Verfügung stellt.

Zu guter Letzt bedanke ich mich bei StefanVogel und haribo fürs Probelesen und Absegnen dieses Artikels.

7. Bibliographie

1. Erich Friedman, Problem of the Month (December 2005).

2. Eberhard H.-A. Gerbracht: Minimal Polynomials for the Coordinates of the Harborth Graph, 2006, arXiv:math/0609360[math.CO].

3. Sascha Kurz, Rom Pinchasi: Regular matchstick graphs. In: American Mathematical Monthly. 118, Nr. 3, 2011, S. 264–267. doi:10.4169/amer.math.monthly.118.03.264 und 2014, arXiv:1401.4372[math.CO].

4. Matroids Matheplanet, Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5, Thread im Kombinatorik & Graphentheorie Forum.

5. Siemens PLM Software, Solid Edge 2D-Drafting ST8.

6. Universitäts-Links der im Text genannten Mathematiker, Aart Blokhuis, Eberhard H.-A. Gerbracht, Heiko Harborth, Sascha Kurz, Rom Pinchasi.

7. Eric W. Weisstein, Harborth Graph, Matchstick Graph, in MathWorld.

8. Wikipedia, Geometrische Graphentheorie, Streichholzgraph, Matchstick graph.

9. Mike Winkler, Peter Dinkelacker, Stefan Vogel, New minimal (4,n)-regular matchstick graphs, 2016, arXiv:1604.07134[math.MG].

10. Mike Winkler, Ein neuer 4-regulärer Streichholzgraph, Mitteilungen der Deutschen Mathematiker-Vereinigung (DMV), Band 24, Heft 2, Seiten 74–75, ISSN (Online) 0942-5977, ISSN (Print) 0947-4471, DOI: 10.1515/dmvm-2016-0031, July 2016.


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Der große Bruder des Harborth-Graphen [von Slash]  
In diesem Artikel stelle ich einen neuen 4-regulären Streichholzgraphen mit 108 Kanten vor. Dieser Graph - siehe rechts - wurde von StefanVogel, haribo und mir als Team im Verlauf unseres Streichholzgraphen-Threads hier auf dem Matheplaneten entdeckt und auch ers
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 464
 
Aufrufstatistik des Artikels
Insgesamt 24 externe Besuche in 2017.11 [Anzeigen]
DomainAnzahlProz
http://www.mikewinkler.co.nf520.8%20.8 %
http://matheplanet.com28.3%8.3 %
http://mikewinkler.co.nf1562.5%62.5 %
http://google.de28.3%8.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.11.16 10:29http://www.mikewinkler.co.nf/index.php/matheplanet.html

Häufige Aufrufer in früheren Monaten
Insgesamt 12 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2016-2017 (7x)http://mikewinkler.co.nf/index.php/artikel.html
201607-09 (5x)http://mikewinkler.co.nf/index.php/streichholzgraphen.html

[Seitenanfang]

" Mathematik: Der große Bruder des Harborth-Graphen" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]