Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1720, vom Themenstarter, eingetragen 2019-02-17
Und wieder mal ein echter WOW-Beitrag von Stefan! 😮
@ Stefan: Stehen wir jetzt kurz vor einem Algortihmus zur Graphenfindung, der sich fast komplett automatisieren lässt? Also Rahmen vorgeben und Lösung suchen lassen?
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1722, vom Themenstarter, eingetragen 2019-02-17
2019-02-17 22:25 - haribo in Beitrag No. 1721 schreibt:
immer wollt ihr dass man es einfach im program anschaut, wer kommt denn mal in berlin vorbei und gibt mir ne schulung?
Also Berlin ist mir jetze etwas weit mit dem Fahrrad, aber 'ne Schulung gibt's gleich hier.
Bei meinen FedGeo Beiträgen einfach auf den Graphen klicken und bei Stefans tikZ Beiträgen erst auf "quote" klicken. Dann im Text den Code zum Graphen
%Eingabe war:
%<Streichholzgraph>
...
%</Streichholzgraph>
%Ende der Eingabe.
kopieren und ins Programm einfügen. Return oder "neu zeichnen" drücken - fertig. 😄
Bei mehreren Graphen, wie in Stefans letztem Beiträg, muss man den Code dann etwas suchen.
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1725, vom Themenstarter, eingetragen 2019-03-04
Lasst uns mal ein paar "open problems and conjectures" sammeln.
Ich hätte da eine Vermutung zur Form: Das kleinstmögliche Beispiel scheint immer eine Punkt- oder Spiegelsymmetrie zu besitzen. Bei den 4-reg. girth 3 der Harborth-Graph, bei den 3-reg. girth 5 der 54er, bei den 3-reg. girth 4 der 20er.
Kann es einen 4-reg. girth 4 geben der nicht unendlich viele Knoten besitzt?
----------------- Bound to be disappointing so why wait?
Neben Button "Punkte" und "Kanten" gibt es jetzt auch einen Button "Flächen". Dieser bestimmt neben der Gesamtfläche auch die Anzahl der Teilflächen, sortiert nach Eckenzahl. Im folgenden Beispiel <a href='' target=_blank>#570-1 bedeutet die Ausgabe "42·3+20·4+2·5+1·6+2·7+1·8+1*24 Drei-, Vier-, Fünfecke…" dass der Graph aus 42 Dreiecken (grau), 20 Vierecken (helleres grün), 2 Fünfecken (rötlich), einem Sechseck (gelb), 2 Siebenecke (hellblau) und 1 Achteck (dunkleres grün) enthält und das letzte "1*24" bezeichnet immer die Umrandung, hier ein 24-Eck.
und Graph #1632: Bei diesem Graph überlappen die gelben 6-Ecke die weiter innen liegenden Flächen ein wenig, da habe ich nachträglich im TikZ-Code ein shift "1.4*..." eingefügt statt vorher "1*...". Das ist also noch nicht perfekt und vielleicht reicht auch schon die jetzige Variante, um die eine oder andere Teilfläche besser zu sehen, wenn sie beispielsweise sehr schmal ist. Ist alles nur ein Versuch.
Ganz zusammendrücken auf Punktabstand 0 zählt als Überschneidung und da funktioniert Button "Flächen" nicht richtig. Das ursprünglich gelbe Sechseck wird auf eine Linie zusammengedrückt, wo man die Anzahl der Ecken nicht mehr erkennen kann, die Darstellung mit den getrennten Teilflächen kann auch nicht alles wiedergeben.
Ich habe dazu in der TikZ-Ausgabe vom Streichholzprogramm je einen Eckpunkt jeder Fläche neu beschriftet und dann zusätzliche shift-Koordinaten eingefügt und solange probiert bis keine Überlagerungen mehr waren.
Das Soll in der jetzigen Programmversion war Zählen der n-Ecke, um schnell zu sehen, dass der Graph keine Drei- oder Vierecke enthält. Zählen der Dreiecke war ja schon länger drin, doch die dafür verwendete Methode (welche drei Kanten bilden ein Dreieck) war nicht so gut auf Vierecke oder mehr übertragbar. Bei der aktuellen Variante verwende ich die Methode wie bei Gesamtfläche bestimmen (am Rand einer Fläche entlangtasten), da ist die Eckenzahl egal und ich kann alle Flächen zählen. Anschließend die Flächen nach Eckenzahl färben und etwas auseinanderliegend zeichen ist nicht mehr viel Aufwand beziehungsweis habe ich nicht viel Aufwand gemacht. Ob das so in Ordnung ist, kommt auf den Anwendungszweck an. Ich habe an einigen Graphen gemerkt, dass es ganz ohne Überlagerungen gar nicht gehen kann, also so, dass die Flächen noch wie in der Ausgangslage ineinandergreifen. Als Alternative sind im Streichholzprogramm die Teilflächen transparent überlagert, so dass man die gesamte Kontur erkennen kann (in der Bildschirmkopie sieht man nur ganz wenig davon). Um schnell mal einen Blick darauf zu werfen, wenn man nicht mehr weiß, wie sehr schmale Teilflächen verlaufen, dafür habe ich das schon verwendet. In der TikZ-Ausgabe die Teilflächen zurechtrücken oder ganz neu anordnen habe ich auch schon gemacht.
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1733, vom Themenstarter, eingetragen 2019-03-17
Ich habe sofort an tolle Puzzle gedacht. Vielleicht lassen sich auch immer zwei Kanten der Teile so aneinanderfügen, dass man eine faltbare Graphen-Schlange bekommt. Das 4/11-Puzzle sieht bestimmt als Wandgemälde schick aus.
----------------- Bound to be disappointing so why wait?
StefanVogel
Senior Dabei seit: 26.11.2005 Mitteilungen: 3748
Herkunft: Raun
Beitrag No.1734, eingetragen 2019-03-23
2019-03-16 21:40 - Slash in Beitrag No. 1729 schreibt:
Hier gibt es Überlagerungen der Flächen. Ist das in Ordnung oder sollte das nicht sein? Oder müssen die Flächen nur weiter auseinandergedrückt werden?
Nach Button "Flächen" und Anklicken einer der Flächen erzeugt jetzt Button ".dxf" nicht mehr den Graph aus Linienelementen LINE sondern aus Polygonelementen LWPOLYLINE. Für den einfachen Graph #1718-4
und in einem zufällig gewählten dxf-Viewer ging das auch anzuschauen. Nur einen passenden dxf-Editor zum Verschieben der Dreiecke habe ich nicht gefunden. Vielleicht funktioniert es mit deinem Programm, oder es muss noch etwas geändert werden.
StefanVogel
Senior Dabei seit: 26.11.2005 Mitteilungen: 3748
Herkunft: Raun
Beitrag No.1736, eingetragen 2019-03-23
Ich habe Inkscape jetzt installiert, doch warum LWPOLYLINE nicht geht finde ich auf Anhieb auch nicht. Inkscape versteht aber .svg-Dateien. Versuche mal Graph Button "#1705" auswählen, dann Button "Flächen", dann eine Fläche anklicken, dann Button "SVG" und den darunter angezeigten Dateiinhalt als .svg-Datei in Inkscape laden. Dann muss man sich noch durch paar unsichtbare Ebenen hindurchklicken (muss ich bei Button "Flächen" noch entfernen) und kann dann die Polygone einzeln verschieben.
StefanVogel
Senior Dabei seit: 26.11.2005 Mitteilungen: 3748
Herkunft: Raun
Beitrag No.1738, eingetragen 2019-03-24
Nächster Versuch: Streichholzgraph-1554.htm, dann Graph Button "#1705", dann Button "Flächen", dann eine Teilfläche anklicken, dann ganz unten Button ".dxf" und den Dateiinhalt in Inkscape laden. Dann sind in meinem installierten Inkscape die Teilflächen sichtbar und verschiebbar.
Nach jeder Zeile LWPOLYLINE folgt jetzt ein Zusatz
und am Dateianfang und -ende sind noch jede Menge Einstellungen dabei. Da habe ich nicht weiter probiert, was man davon weglassen kann. Ich habe in Inkscape ein einzelnes Polygon gezeichnet, als .dxf gespeichert und dann setze ich an der Stelle "LWPOLYLINE...AcDbPolyline..." die Teilflächen des Streichholzgraphen ein.
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2658
Beitrag No.1739, eingetragen 2019-03-24
moin, könnt ihr wieder etwas mehr drauf achten in den beiträgen anzugeben welcher graph gerade zu nem irrgarten explodiert wird? in 1712 hatte ich ja irgendwie eine idee verfolgt um abstrakt neues zu begreifen... daran kann ich evtl weiterarbeiten, aber nur wenn ich die herleitung etwas verfolgen kann
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1740, vom Themenstarter, eingetragen 2019-04-18
Ich bin zurzeit viel mit Parkettierungen beschäftigt, daher war es hier etwas ruhig.
Vielleicht sollten wir mal den Beweis des Harborth-Graphen als kleinsten mit doppelter Spiegelsymmetrie in Angriff nehmen. Also erstmal die möglichen Viertel-Teilgraphen mit weniger als 13 Kanten sammeln und dann die Beweglichkeit disskutieren. Wir hatten ja schon mal die möglichen Symmetrieübergänge besprochen mit halben Kanten etc.
Frohe Ostern!
----------------- Bound to be disappointing so why wait?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2658
Beitrag No.1741, eingetragen 2019-04-28
moin slash,
wiso 13? ich zähle beim harbort im viertel immer noch 26
auch bleibt mir die suche im "doppelt symetrischen" als ansatz viel zu engstirnig
wir waren da schonmal offener/allgemeiner indem wir 360/2n als tortenwinkel betrachteten... aber selbst dass ergäbe ja immer nur mehrfache gespiegelte-symetrien, bei n=2 dann eben auch der engstirnige harbort spezialfall "doppelt symetrisch"
was wir jetzt wirklich bräuchten wären echt offenen ansätze und davon diejenigen welche wir mal endlich mit hoher anzahl automatisch generieren können, also nen übergang von freien zufällen im java-takt welche dann an unser "streichholz-zurechtrück-program" übergeben werden... grriiins
kann ja nicht sein das unser m/n monster 4/11 wirklich der weisheit kleinste minimalität darstellt, selbst 4/10 oder 4/9 sind viel zu spontan mit primitivsten mitteln generiert worden als dass sie ewig halten könnten
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1742, vom Themenstarter, eingetragen 2019-04-29
Warum ich die 26 durch 2 geteilt habe, kann ich dir auch nicht sagen. 😁
Ich dachte mir, dass <= 26 Kanten im Viertelgraphen eine gute Übung wären, die uns die Schwierigkeiten eines Beweises ausloten lässt. Ansonsten war Stefan ja schon kurz davor mit seinem Program bei den 3ern girth 5 eine Suche zu automatisieren.
Eine Strategie hin zu einem automatischen Such-Algorithmus könnte vielleicht sein, dass wir uns von klein nach groß hocharbeiten. Bis 10 Kanten sind z.B. alle möglichen Streichholz-Teilgraphen bekannt. So könnten wir das dann überprüfen.
Für die 4-regulären wäre es wohl sinnvoll von außen nach innen zu arbeiten, so wie wir es oft getan haben, also Rahmen zuerst. Ring aus gleichseitigen Dreiecken und dann ... das ist die große Frage. Meine minimalen 4er mit 2-3 leicht falschen Kanten sind hier gute Anschaungsobjekte, da sie einen Eindruck davon vermitteln, was möglich sein könnte.
Eine weitere Strategie wäre es bei den 4ern von einer Dreiecksparkettierung auszugehen, also den komplett zusammengefalteten Graphen mit 3er, 4er und 6er Knoten. Und diese dann versuchen so auseinandezuziehen, dass nur 4er Knoten übrigbleiben. Stichwort: Epsilon-Graphen.
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1743, vom Themenstarter, eingetragen 2019-05-26
Fast ein 112er. Schon mal dagewesen - keine Ahnung?
56 Knoten, 56×Grad 4, 0 Überschneidungen
112 Kanten, minimal 0.99999999999996680433, maximal 1.10774187247689637204
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1744, vom Themenstarter, eingetragen 2019-05-27
Fast 124er (der erste!). Kaum zu glauben, dass der nicht will.
62 Knoten, 62×Grad 4, 0 Überschneidungen
124 Kanten, minimal 0.99999999999997346567, maximal 1.03320923741677850316
einzustellende Kanten, Abstände und Winkel:
|P11-P28|=1.00000000000000066613
|P23-P28|=1.00000000000000066613
|P31-P62|=0.99999999999997346567
|P25-P62|=1.03320923741677850316
nicht passende Kanten:
|P25-P62|=1.03320923741677850316
|P56-P32|=1.03320923741677783703
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1750, vom Themenstarter, eingetragen 2019-06-02
Mal eine neue Idee. (Im Prinzip ist es ein aufgebrochener Harborth-Rahmen.) Alle Kanten 1, aber zwei 2er Knoten.
58 Knoten, 2×Grad 2, 56×Grad 4, 0 Überschneidungen
114 Kanten, minimal 0.99999999999999755751, maximal 1.00000000000000310862
----------------- Bound to be disappointing so why wait?
Leider präsentiert er unseren 108er Team-Graphen nur unter meinem Namen, obwohl es in unseren Artikeln ja korrekt steht - "On July 3, 2016 the authors discovered ...".
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8183
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1755, vom Themenstarter, eingetragen 2019-06-02
2019-06-02 20:29 - haribo in Beitrag No. 1754 schreibt:
23 aufrufe in zwei jahren.... nicht janz einfach zum zuhören
aber haben wir ihm eigendlich mein dutzend tetraeder raumgebilde mal gezeigt? (letzte darstellung im film)
Tja, Streichhölzer kennen alle, Streichholzgraphen kaum jemand. ☹️
Deinen 12er hatte ich ihm und Prof. Servatius Ende September 2017 gemailt. Ich denke aber, dass seine Folien laufend aktualisiert werden. Vielleicht findet ja mal ein Vortrag an einer deutschen Uni statt.
Deinen und Stefans nur Dreieck-Ring kennt er ja inzwischen auch. Mal sehen, vielleicht sind wir ja in der nächsten Geombinatorics wieder mit dabei.
----------------- Bound to be disappointing so why wait?
Diese animate-Elemente mitsamt href-Attribut werden, wenn nicht aus früheren Graphen kopiert, von Button "mehr" (für weitere bewegliche Winkel) erzeugt, mit javascript setAttributeNS("http://www.w3.org/1999/xlink","href","#blauerWinkel"), und später beim Erzeugen der Animation mit getAttribute("xlink:href") ausgelesen. Deshalb funktioniert im obigen Graph nur die Animation zum ersten Winkel und die zum zweiten Winkel nicht. Das habe ich in der neuesten Version Streichholzgraph-1554.htm korrigiert, da verwende ich getAttributeNS("http://www.w3.org/1999/xlink","href") und zusätzlich auch noch setAttributeNS("http://www.w3.org/1999/xlink","xlink:href","#blauerWinkel").