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 905 Gäste und 33 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Ein 4-regulärer Streichholzgraph mit 114 Kanten
Freigegeben von matroid am Mo. 09. Mai 2016 16:12:38
Verfasst von Slash -   855 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Ein 4-regulärer Streichholzgraph mit 114 Kanten

In diesem Artikel stelle ich (m)einen 4-regulären Streichholzgraphen mit 114 Kanten vor. Dieser Graph - siehe rechts - wurde von mir am 15. April 2016 entdeckt und erstmals hier auf dem Matheplaneten präsentiert. Er ist nach dem Harborth-Graphen mit 104 Kanten das nun zweitkleinste bekannte Beispiel eines 4-regulären Streichholzgraphen und unterbietet seinen Vorgänger - der diesen Rekord immerhin 30 Jahre hielt - um 6 Kanten. Zwischen beiden Graphen existieren ein paar interessante geometrische Zusammenhänge. Im Prinzip muss der alte Graph nur leicht verformt, in Teilgraphen zerlegt, etwas bearbeitet und neu zusammengesetzt werden. Wie und warum das funktioniert, zeige ich im Artikel.

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 sie von einem Knoten zu lösen. Ist ein Graph flexibel, so können Kanten und Knoten gegeneinander bewegt werden ohne seine Knotengrade zu verändern bzw. den Graphen zu zerstören. 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, wurde erstmalig 2006 durch Eberhard H.-A. Gerbracht gezeigt. Durch die von Gerbracht mit Hilfe eines Computeralgebrasystems ermittelten Minimalpolynome für die Koordinaten der Ecken des Harborth-Graphen ist die Existenz des Graphen dann auch (fast) vollständig mathematisch nachgewiesen. Es bleibt eigentlich nur noch der strikte Nachweis, dass jedes der Minimalpolynome auch eine reelle Nullstelle besitzt, die dann die jeweiligen Koordinaten ergeben.


3. Die Konstruktion des neuen Graphen

Der ehemalige zweitkleinste 4-reguläre Streichholzgraph mit 60 Knoten und 120 Kanten kommt recht unspektakulär daher. Er besteht aus 12 identischen Teilgraphen und besitzt eine Rotationssymmetrie vom Grad 12.


Auch wenn man es diesem Graphen nicht sofort ansieht - er ist flexibel und kann stetig verformt werden. Diese Flexibilität liegt in seinen Teilgraphen begründet, die ebenfalls flexibel sind.



Der Teilgraph besteht aus 7 Knoten und 10 Kanten. Der er nur Knoten vom Grad 2 und 4 besitzt, bezeichnet man ihn auch als (4,2)-regulären Graphen. Während der untere Teil aus drei gleichseitigen Dreiecken starr ist, ist der obere Teil, das Quadrat, flexibel. Der Teilgraph selbst ist also eine Kombination aus den beiden einfachsten Beispielen für starre und flexible Streichholzgraphen.

Machen wir uns jetzt an die Konstruktion des neuen Graphen. Zunächst spiegeln wir den Teilgraphen an der grünen Gerade durch die Knoten P1 und P2. Danach verformen wir die beiden Quadrate zu Rauten, indem wir den Knoten P2 nach unten und rechts bewegen. Und zwar so, dass die rote Strecke zwischen den Knoten P3 und P4 genau 2 Kantenlängen misst. Der blaue Winkel zwischen der Spiegelgerade und der waagerechten Kante an P1 beträgt im linken Bild genau 75 Grad, im rechten Bild sind es ungefähr 67,76 Grad.


Nun lassen sich je genau sechs von diesen gespiegelten doppelten Teilgraphen wieder zu einem großen 4-regulären Streichholzgraphen zusammenfügen.

Das linke Bild zeigt die beiden so erzeugten Graphen im direkten Vergleich. Man kann gut erkennen, wie der rote Graph verformt wurde. Nur noch der starre Teil des untersten Teilgraphen aus 5 Knoten und 7 Kanten hat hier in beiden Graphen dieselbe Position. Im rechten Bild sehen wir nur den verformten Graphen, der jetzt logischer Weise nur noch eine 6-fache Rotationssymmetrie besitzt. Alle Kanten, die waagerecht erscheinen, sind auch wirklich waagerecht. Der Graph lässt sich natürlich noch viel extremer verformen, doch wir brauchen ihn für unsere Zwecke in genau dieser Form.



Der neue Graph lässt sich auch in vier Viertel-Teilgraphen einteilen, die sich jeweils auf die gegenüberliegende Seite spiegeln lassen (Abb. a). Wir nehmen uns jetzt einen Viertel-Teilgraph heraus (Abb. b), und ziehen eine senkrechte Gerade durch den Knoten P5 und den Kantenmittelpunkt P6 (Abb. c). Nun löschen wir die neuneinhalb blauen Kanten und drehen die beiden roten Kanten an die senkrechte Gerade, auf der sie sich in Punkt P7 treffen (Abb. d). Die beiden Kanten zwischen den Knoten P8, P2 sowie P2, P7 besitzen exakt gleiche Winkel. Dasselbe gilt für die Kanten zwischen den Knoten P10, P9 und P9, P7. Die Kante zwischen den Knoten P11, P10 ist genau waagerecht bzw. parallel zur Kante zwischen den Knoten P1, P5. Der waagerechte Abstand des Knoten P2 zur senkrechten Gerade beträgt genau eine viertel Kantenlänge. Im nächsten Schritt spiegeln wir diese Figur an der senkrechten Gerade und erhalten einen neuen Teilgraphen aus 22 Knoten und 41 Kanten, den ich Triplet-Kite genannt habe (Abb. e).



Der Triplet-Kite ist ein starrer Graph. Für die Starrheit ist der Knoten P7 verantwortlich. Dieser Graph besitzt eine ganz wunderbare geometrische Eigenschaft. Verbindet man nämlich die Kantenmittelpunkte P12 und P15, und konstruiert mit dieser Strecke ein gleichseitiges Dreieck, dann verlaufen die beiden Strecken P12, P16 und P15, P16 jeweils genau durch den Kantenmittelpunkt P13 bzw. P14 (Abb. f). Daraus folgt, dass sich drei Triplet-Kites so kombinieren lassen, dass ihre äußeren Dreiecke jeweils paarweise genau übereinander liegen, was uns schließlich zu unserem neuen minimalen 4-regulären Streichholzgraphen mit 114 Kanten führt (Abb. g).



Der neue Graph besitzt noch eine weitere wunderbare geometrische Eigenschaft. Die drei mittleren Knoten besitzen nämlich zueinander genau eine Kantenlänge Abstand, so dass man mit einer bzw. drei zusätzlichen Kanten auch einen (4,5)-regulären bzw. (4,6)-regulären Streichholzgraphen konstruieren kann. Solche Graphen dürfen neben Knoten vom Grad 4 auch Knoten vom Grad 5 bzw. 6 besitzen. Mit ihren 115 bzw. 117 Kanten sind diese beiden Streichholzgraphen die zurzeit kleinsten bekannten Beispiele ihrer Art. Diese und weitere aktuelle Minimalitäts-Rekorde für (4,n)-reguläre Streichholzgraphen finden sich in diesem Artikel und auf dieser Website.



Die beiden oberen Bilder zeigen den neuen roten Graphen im direkten Vergleich zu seinen 120-kantigen Vorgängern. Links mit der ursprünglichen und rechts mit der verformten Version. Die schwarzen Punkte kennzeichnen dabei Knoten, welche in beiden überlagerten Graphen identisch sind. Das untere linke Bild soll noch einmal die wunderschöne 3er-Symmetrie des neuen Graphen hervorheben, während ihn das rechte Bild mit zusätzlichen bunten Kanten zeigt. Diese grenzen entweder an die ursprünglichen Knoten oder an Kantenmittelpunkte.



Das letzte Bild ist dem neuen Graphen in seiner reinsten Form gewidmet.



Auch wenn es etwas kitschig klingt - ich empfinde für diesen Graphen wahre Liebe.

Viele Grüße, Slash


4. Anmerkungen

Mein erster Weg hin zum neuen 4-regulären Streichholzgraphen mit 114 Kanten war etwas umständlicher und experimenteller als der hier im Artikel gezeigte Weg.

Für reguläre Graphen die nur Knoten der Grade m und n besitzen existiert keine einheitliche Schreibweise. Neben der hier verwendeten Schreibweise (m,n)-regulär findet man auch noch die Schreibweise m/n-regulär.

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.

Ich bedanke mich herzlich bei haribo für unseren kreativen Austausch innerhalb und außerhalb des Forums, sowie bei StefanVogel für seine umfangreichen Graphenprüfungen im entsprechenden Thread[4] und fürs Probelesen dieses Artikels.

5. 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, Beitrag No.179, vom Themenstarter, eingetragen 2016-04-15 04:23.

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

6. Universitäts-Links der im Text genannten Mathematiker, Aart Blokhuis, Erich Friedman, 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].


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfpdf-Datei zum Artikel öffnen, 437 KB, vom 10.05.2016 22:28:17, bisher 204 Downloads


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
Ein 4-regulärer Streichholzgraph mit 114 Kanten [von Slash]  
In diesem Artikel stelle ich (m)einen 4-regulären Streichholzgraphen mit 114 Kanten vor. Dieser Graph - siehe rechts - wurde von mir am 15 April 2016 entdeckt und erstmals hier auf dem Matheplaneten präsentiert. Er ist nach dem Harborth-Graphen mit 104
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 855
 
Aufrufstatistik des Artikels
Insgesamt 55 externe Besuche in 2017.11 [Anzeigen]
DomainAnzahlProz
http://google.de47.3%7.3 %
http://matheplanet.de11.8%1.8 %
http://mikewinkler.co.nf2443.6%43.6 %
http://matheplanet.com11.8%1.8 %
http://images.google.de2138.2%38.2 %
http://oeis.org11.8%1.8 %
http://www.mikewinkler.co.nf23.6%3.6 %
http://r.duckduckgo.com11.8%1.8 %

Häufige Aufrufer in früheren Monaten
Insgesamt 41 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201606-08 (21x)http://images.google.de/url?sa=t&rct=j&q=
2016-2017 (12x)http://mikewinkler.co.nf/index.php/artikel.html
2016-2017 (8x)http://mikewinkler.co.nf/index.php/streichholzgraphen.html

[Seitenanfang]

" Mathematik: Ein 4-regulärer Streichholzgraph mit 114 Kanten" | 3 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Ein 4-regulärer Streichholzgraph mit 114 Kanten
von Hans-Juergen am Di. 10. Mai 2016 09:24:48


Hallo Slash,

danke für den interessanten Artikel. Ich freu' mich mit Dir über Deine Entdeckung und ihre sehr gut verständliche, lehrreiche Begründung.

Mit herzlichem Gruß
Hans-Jürgen


 [Bearbeiten]

Re: Ein 4-regulärer Streichholzgraph mit 114 Kanten
von nosapa am Mi. 11. Mai 2016 18:15:35


Hallo Slash,

Ein schöner Artikel. Es erinnert mich an Kristalle.

Viel Erfolg.

nosapa

 [Bearbeiten]

Re: Ein 4-regulärer Streichholzgraph mit 114 Kanten
von Slash am Mo. 04. Juli 2016 15:37:44


Kleine Aktualisierung:

Dieser Artikel ist in verkürzter Form in den Mitteilungen der DMV erschienen.
(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.)

Inzwischen haben StefanVogel, haribo und ich einen noch kleineren 4-regulären Streichholzgraphen mit 108 Kanten entdeckt, der sich aus dem Harborth-Graphen konstruieren lässt, wenn man diesen leicht modifiziert und verformt.

Die Entdeckung hat eine längere und etwas komplizierte Historie. Angefangen bei Stefans erster Idee hier, welche er aber als unmöglich verworfen hatte. Dann wurde der gleiche Graph später nochmal hier von mir vorgestellt. Da die Idee zum Graph aber relativ einfach ist, bin ich den gesamten Thread noch einmal druchgegangen, um zu sehen, ob wir ihn nicht doch schon mal hatten. Nachdem ich Stefans früheren Beitrag gesehen hatte, habe ich meinen Beitrag gleich wieder gelöscht. Zum Glück war aber haribo online und hatte meinen kurzen neuen Post mit dem 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 Beiträge und Tage später waren wir drei uns dann absolut sicher, dass dieser Graph wirklich existiert, und Stefan in seinem ersten Test einen Fehler gemacht hatte. Eine tolle Teamarbeit, wie wir drei selbst finden. Und es zeigt auch, wie wichtig in einem Team neben kreativem Austausch, gegenseitiger Wertschätzung und Vertrauen, auch die gegenseitige Kontrolle ist. Ende gut - Graph gut. smile

Hier der Link zum Artikel über den neuen Graphen mit 108 Kanten.

Gruß, Slash

 [Bearbeiten]

 
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]