Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1280, vom Themenstarter, eingetragen 2018-06-09
2018-06-09 21:32 - StefanVogel in Beitrag No. 1279 schreibt:
Über 50 Graphen von #1143 bis #1183 als Versuche für minimale Knotenzahl, die ich mit folgender Gleichung aus Beitrag No.622
unter die Lupe nehmen will. Als Beweglichkeit verwende ich die Anzahl der einstellbaren Winkel eines eingebenen Graphen. Knotengradabweichung bezeichnet, um wieviel Knotengrade insgesamt der Graph von einem 4-regulären Graph abweicht. Beispielsweise wenn ein Graph 2 Knoten mit Grad 2 enthält, ist die Knotengradabweichung -4, bei einem Knoten von Grad 6 ist die Abweichung 2. Einsetzkanten war die Anzahl derjenigen Kanten, die beim Einsetzen passen müssen, weil durch den Graph ein bestimmter Abstand vorgegeben ist. Wenn beispielsweise ein Punkt P3 über zwei Kanten mit P1 und P2 verbunden werden soll, dann kann sich P3 nach der Länge der beiden Kanten ausrichten. Das sind keine Einsetzkanten. Wenn vorgegebe Punkte P4 und P5 durch eine Kante verbunden werden sollen, dann muss die Kantenlänge genau zum Abstand passen. Das meine ich mit Einsetzkanten. Es ist auch am schwierigsten, Einsetzkanten in einem Graph zu bestimmen, weil sie bei raffinierten Eingabemethoden mit Kopieren von Teilgraphen nicht so leicht ersichtlich sind. Eine gute Methode, solche Einsetzkanten zu bestimmen, ist Button "neue Eingabe, Rahmen zuerst", weil dort darauf geachtet wird, soche Einsetzkanten herauszufinden. Beispielsweise erhalte ich aus Graph #1155-1 nach Button "neue Eingabe, Rahmen zuerst"
das sind 2 Knoten von Grad 2, also Knotengradabweichung -4, 5 bewegliche Winkel, 6 Einsetzkanten (als A18=...aufgelistet). 6 = 1/2 * -4 + 5 + 3 stimmt. Es fällt nun auf, obwohl nur 5 bewegliche Winkel sind, mit denen nur 5 Einsetzkanten eingestellt werden können (je Winkel eine Kante), dass die 6-te Einsetzkante auch die Länge 1 hat. Das führe ich darauf zurück, dass bei zwei symmetrischen Teilgraphen eine Kante mehr passend gemacht werden kann. Von dieser Sorte sind nun eine ganze Reihe Graphen #1155-1, #1155-3, #1155-5, #1158-1, #1159-1, #1159-3, #1159-4, #1160, #1174-4, #1179-3, #1180-2 und auch die verschiedenen Doppelkites haben 2 Knoten vom Grad 2, eine Einsetzkante mehr als bewegliche Winkel und diese passt wegen zwei symmetrischer Teilgraphen.
Bei den 4-regulären Graphen sind das nach dieser Berechnung 3 Einsetzkanten mehr als bewegliche Winkel, Einsetzkanten = 1/2*0 + Beweglichkeit + 3. Als Beispiel der Graph #1152 nach Button "neue Eingabe, Rahmen zuerst"
5 bewegliche Winkel und 8 Einsetzkanten, das sind wie berechnet 3 Einsetzkanten mehr als bewegliche Winkel. Auch hier stimmt eine der drei überzähligen Einsetzkanten, was ich auch wieder darauf zurückführe, dass der Graph aus zwei symmetrischen Teilgraphen besteht und in einer ganzen Reihe von Graphen ist das genauso: #1152, #1158-2, #1159-2, #1162-1 bis 4, #1163, #1165, #1166-1 bis 3, #1172-1, #1172-2, ##1174-1, #1174-3, #1178, #1179-1, #1179-2, #1180-1, #1182, #1183. Etliche Graphen wo das nicht so ist, lassen sich dann verbessern, indem die Eingabe so gestaltet wird, dass die Symmetrie berücksichtigt wird, #1143, #1145, #1157, #1154-4, #1173-1 bis 3, #1174-2.
Was nutzt das ganze, wenn alle 3 überzähligen Einsetzkanten passen sollen? Dann muss man es eben mit einem Graph versuchen, der vier symmetrische Teilgraphen enthält und die 3 überzähligen Einsetzkanten müssen sich symmetrisch über dem Graph verteilen und die dazu symmetrische vierte Kante ist dann einstellbar. Ich denke, nach diesen über 50 vergeblichen Versuchen haben wir eine solche Lösung verdient
Ich habe den Viertelgraph doppelt gespiegelt und dann zwei Knoten auf Abstand 0 gebracht. Diese wurden aber als vier 2er Knoten erkannt. Dann habe ich die neue Knotenreduktionsfunktion benutzt.
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1288, vom Themenstarter, eingetragen 2018-06-10
@ Stefan
Noch eine Idee für eine neue Funktion: "Kanten ausblenden". Es werden nur die Knoten angezeigt, vielleicht als kleine Punkte, also größer als ein Pixel. "Punkte aus/an" sollte aber davon unabhängig funktionieren.
----------------- Bound to be disappointing so why wait?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1289, vom Themenstarter, eingetragen 2018-06-11
Fällt dir dazu was ein, haribo? Das Färben mit den Einheitskreisen klappt perfekt. Der ganze Graph ist total symmetrisch. Aber diese 6 gelben Knoten tanzen aus der Reihe.
----------------- Bound to be disappointing so why wait?
StefanVogel
Senior Dabei seit: 26.11.2005 Mitteilungen: 3757
Herkunft: Raun
Beitrag No.1290, eingetragen 2018-06-11
Bei Button "Punkte aus/an" passt dann aber die Beschriftung nicht mehr und "Punktfarbe" darüber auch nicht. Ich habe diesen Button aufgeteilt in die drei "Kanten", "Punkte", "alles". Die Punktgröße kannst du in der Programmzeile c.setAttribute("r",2); einstellen bis eine passende Größe gefunden ist. Die Programmfehler lassen sich wie immer nicht mehr blicken, da müssen wir abwarten. Streichholzgraph-981.htm
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1293, vom Themenstarter, eingetragen 2018-06-11
Das waren aber nur einige wirre MoSp mit Stefans neuer Funktion generiert. Das Punktebild hat nichts mit den anderen Graphen zu tun. Aber eine gewisse Knotendichte mit MoSp zu schaffen ist wohl nötig.
----------------- Bound to be disappointing so why wait?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1294, eingetragen 2018-06-11
in #1268 hatte ich versucht zu zeigen dass (und warum) mehrere MoSp keinen vorteil erwarten lassen, IMO hat die MoSp lediglich ihren sinn beim übergang von drei auf vierfarbigkeit
insofern verwende jeden beliebigen beweglichen graphen um dichte dichten zu erstellen
als einfachstes also nen viereck... beweglich dargestellt, danach einige mal um irgend welche punkte gespiegelt... dicht auf engem raum
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1297, eingetragen 2018-06-11
nächster schritt? abdeckung erhöhen...94,6% is besser
da alle kreise regelmässig im abstand 2 auf lücke liegen wären die farben innerhalb der überschneidungsflächen ganz wahlfrei wählbar
ansonsten versuche ich dir eine vorlage zu liefern damit du einen graphen suchen kannst der immer "IMMER" einen punkt in den zwischenflächen hat, dann bräuchte man entweder 6 farben, oder es gibt eine bessere kachelung...
also frage: ein wie enges regelmässiges raster hat immer einen treffer in einer der lücken, egal wie man es paralell verschiebt oder rotiert?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1298, eingetragen 2018-06-11
#1289, evtl bekommt mman ein besseres ergebnis mit unsymetrischer mitte
aber ich brächte eine sauberere vorlage, hier erkenne ich nahezu nichts mehr
jedenfals beginne ich inzwischen mit nicht überdeckten einheitskreisen(wie rechts oben dargestellt), und schiebe erst einzelne flächen richtung mitte (--->)wenn einzelne knoten in den zwickeln stecken, hier die mit kreuz markierten... alles nochmals am graphen von vor einigen tagen dargestellt
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1300, vom Themenstarter, eingetragen 2018-06-12
2018-06-11 13:29 - haribo in Beitrag No. 1294 schreibt:
in #1268 hatte ich versucht zu zeigen dass (und warum) mehrere MoSp keinen vorteil erwarten lassen, IMO hat die MoSp lediglich ihren sinn beim übergang von drei auf vierfarbigkeit
insofern verwende jeden beliebigen beweglichen graphen um dichte dichten zu erstellen
als einfachstes also nen viereck... beweglich dargestellt, danach einige mal um irgend welche punkte gespiegelt... dicht auf engem raum
Geht es nicht darum möglichst viele Knoten mit Einheitsabstand miteinander zu verbinden? Und dafür sind Dreiecke am besten geeignet. Und die MoSp ist ja nichts anderes.
----------------- Bound to be disappointing so why wait?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1301, eingetragen 2018-06-12
geschafft, ich habe deine punkte alle in ihrer alten farbigkeit belassen, als vierfarb-colorierung gelten die hintergrundfarben, kein punkt ist undefiniert
als ausgangscolorierung habe ich überschneidungsfreie anordnung gewählt die rote fläche doch wieder zentral angeordnet, und weil bei der zentralen geometrie viele punkte auf den farb-kanten lagen habe ich den gesamten hintergrund erstmal um 3 grad gegen den uhrzeiger gedreht, danach händisch etliche farbflächen verschoben um die lückenpunkte einzufangen
letzteres ist aufwendig, denn man muss beim farbflächen verschieben doch immer wieder einflusskreise R=1,5 beachten/kontrolieren bzw einzelne punkte mit R=1 kreisen versehen, und dann gibt es innerhalb der farbflächen gelegentlich noch zwei gegenüberliegende beide auf dem rand... ungefähr wie ~beim gelben strich
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1304, eingetragen 2018-06-12
ich versuch mal beispielsweise anhand der 3-farb abdeckung und den moserspindeln(MoSp) bzw erweiterter beweglicher moserspindeln(MoMoSp) etwas darzustellen was wir derzeit suchen, denn einfach möglichst viele linien scheint mir nicht das perfekte ziel zum suchen zu sein
im ersten bild ist eine gleichmässige dreifarbabdeckung 68% angelegt, es handelt sich um kreise mit R=0,5 und immer abstand 1 zum nächsten gleichfarbigen, also regelmässig sechs farbflächen um jede andere herum, die anordnung ist also sicher,
solange ein graph mit allen punkten innerhalb der farbflächen läge wäre dieser graph in seinen punkten dreifarbig-colorierbar
versucht man eine MoSp oder auch eine erweiterte also bewegliche MoMoSp drüberzu legen dann gelingt es einem aber nie das alle punkte auf farbflächen liegen, immer ist eine punkt der MoSp ausserhalb einer farbfläche, egal wie man die MoSp dreht oder verschiebt oder auch egal wie man die MoMoSp verzieht!!
dass muss so sein wegen der vierfarbigkeit, ist aber trotzdem sehr faszinierend denn man kann nicht nur die MoSp beliebig drehen und verschieben sondern auch jeweils ganze farbfelder verschieben, also hier beispielsweise alle schwarzen und weissen parallel verschoben ohne dass sie sich mit anderen farbflächen überschnitten haben, (die abdeckung ist immer noch 68%) immer noch gelingt es einem nicht ne MoSp anzuordnen, immerhin auch jetzt findet man schnell positionen die fast alle punkte, bis auf einen, auf den farbfläche plazieren
als weitere möglichkeit kann man sogar einzelne farbflächengruppen rotieren (hier im dritten bild die schwarzen), rotiert um oben bei der MoMoSp den fehlen den punkt einzufangen... Tja da rutscht dann ein anderer heraus, gleichzeitig sinkt natürlich die abdeckung unter 68%, aber darum geht es gerade nicht, diese farbanordnung wäre trotzdem endlos in alle richtungen erweiterbar, und solange man alle schwarzen flächen rotiert bleibt die anordnung auch sicher da ja die schwarzen flächen in sich sicher sind
schätze wir müssen diesen mechanismuss des rausrutschens aus den farbflächen, mindestens jeweils eines punktes, beim drehen und wenden des MoSp oder der farbflächen irgendwie noch besser begreifen, sozusagen einen vierfarb-beweis für die MoSp formulieren nur anhand der farbflächen???
was macht die MoSp zur vierfarbigkeit?, sie hat ja nun nicht besonders eng liegende punkte, wiso liegt trotzdem immer einer daneben, dazu fehlt eine erklärung... wie kann man das auf die fünffarbigkeit erweitern???
letztendlich suchen wir also etwas entsprechendes für die vierfarb-abdeckung oder für die fünffarb-abdeckung, einen graphen der immer einen punkt in den freien zwickeln hat... ob er dazu unbedingt möglichst viele linien haben muss oder eben sonstwie super-mosern-muss sei doch weiterhin offengelassen
oder aber wir suchen eine sechsfarb-abdeckung die sicher ist und 100% abdeckt.... so es sie denn gibt
so viel für heute, ich verabschiede mich mal für einige urlaubswochen...
haribo
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1306, vom Themenstarter, eingetragen 2018-06-13
Also der Inkreisradius eines gleichseitigen Einheitsdreiecks, \(r=\frac{1}{2\sqrt{3}}\), spielt wohl eine ganz große Rolle, da in den bisherigen Konstruktionen viele Knoten diesen Abstand voneinander haben.
----------------- Bound to be disappointing so why wait?
\ Es gilt abs(P1-P4)=sqrt(3)=1/2\.sqrt(12), abs(P4-P8)=1/2, \sphericalangle\ (P4,P8,P1)=90°, somit abs(P1-P8)=1/2\.sqrt(11). Daraus folgt für \psi=\sphericalangle\ (P8,P1,P4) = \sphericalangle\ (orange,grün)
cos(\psi)=sqrt(11)/sqrt(12) sin(\psi)=1/sqrt(12)
und dann \sphericalangle\ (P6,P1,P2)=\sphericalangle\ (P5,P1,P4)=2\.\psi, \sphericalangle\ (P3,P4,P5)=60°-\psi.
GAP
W60:=[[1/2,-1/2*Sqrt(3)],[1/2*Sqrt(3),1/2]];
Wbl:=[[1/4,-1/4*Sqrt(15)],[1/4*Sqrt(15),1/4]]*W60^-1; #acos(1/4)_Graph
cos16p778:=Sqrt(11)/Sqrt(12); #Moser-Spindel
sin16p778:=1/Sqrt(12);
W16p778:=[[cos16p778,-sin16p778],[sin16p778,cos16p778]];
P:=[];
P[1]:=[0,0];
P[2]:=[1,0];
P[3]:=P[1]+W60*(P[2]-P[1]);;
P[4]:=P[3]+W60*(P[2]-P[3]);;
P[6]:=P[1]+W16p778^2*(P[2]-P[1]);;
P[7]:=P[1]+W60*(P[6]-P[1]);;
P[5]:=P[7]+W60*(P[6]-P[7]);;
Kante:=[ [1,2], [1,3], [2,3], [3,4], [2,4], [5,6],[5,7],[4,5], [1,6], [1,7], [6,7], ];;
Size(Kante);
for K in Kante do Print(" ",(P[K[1]]-P[K[2]])^2); od;
GAP-Logfile
gap> for K in Kante do Print(" ",(P[K[1]]-P[K[2]])^2); od;
1 1 1 1 1 1 1 1 1 1 1
gap>
verwendet und dort mit etwas Bastelei die Punktkoordinaten und Kanten herausgelesen. Nach Zusammenfassen aller Knoten im Abstand maximal 0.01 erhalte ich als Ergebnis des GAP-Programms, alle Kanten sind exakt 1 bis auf zwei Kanten von Punkt (10,698;12,983) zu (9,697;13,560) und von (12,612;12,405) zu (12,612;13,560). Diese beiden Kanten haben eine Länge exakt 1/3 mal Wurzel 3, scheinen also keine beabsichtigten Kanten mit Länge fast 1 zu sein.
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1308, vom Themenstarter, eingetragen 2018-06-16
In Bezug auf die beiden vorherigen Beiträge. Hier mein Versuch die Existenz eines Graphen mit chromatischer Zahl 5 zu zeigen. Dreiecksparkettierung mit 4-farb-Verteilung, dargestellt durch die Knoten und Kreise mit r=0,5. Die orangenen Kreise haben \(r=\frac{1}{\sqrt{12}}\) und sitzen auf den Knoten und in den Dreiecken, haben also wie die Kreise mit r=0,5 genau 6 Berührpunkte untereinander. Der schwarze Knoten sitzt genau im Mittelpunkt eines orangenen Kreises der außerhalb der Farbflächen liegt. Sein Einheitskreis (r=1) verläuft genau durch alle 4 Farbbereiche und schneidet die orangenen Kreise. Auf den Schnittpunkten müssten nun die Knoten des Graphen liegen. Und genau dies lässt sich mit einer MoSp-Konstruktion erreichen wie de Grey gezeigt hat. Die MoSp im Bild dient nur als Beispiel. Der 6-Eckgraph allein ist natürlich 3-färbbar.
----------------- Bound to be disappointing so why wait?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1309, eingetragen 2018-06-17
Ah ha
Dein MoSp hat einen lila Punkt in d lilafläche ziemlich am Rand. Liegt der näher am lila farblächenrand als der schwarze? Also reichen 6 od 12 andere lila Punkte , alle jeweils gleichartig hergestellt, also zentral um den lila farbflächenmittelpkt angeordnet, um die lila farbfläche so zu fixieren dass man die lila Fläche nicht mehr benutzen/verschieben kann um den schwarzen einzufangen?
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1310, vom Themenstarter, eingetragen 2018-06-17
Die MoSp bzw. ihre farbigen Knoten haben dort eigentlich gar nichts zu sagen. Ich hätte sie auch weglassen können. Mir ging es darum zu zeigen, dass wenn wir einen Graphen wie #1302 nehmen, den du gefärbt hast, es nichts gibt, was gegen einen 5-färbbaren Graphen spricht, da die Knoten von MoSp bzw. allg. Dreiecken auf den orangenen Kreisen bzw. deren Schnittpunkte liegen können/müssen. Jeder weitere Knoten in dem Graphen hätte auch einen orangenen Kreis. Wie genau jetzt die kleinste Konstruktion eines solchen Graphen aussieht - keine Ahnung. Die Schnittpunkte der orangenen Kreise müssten eben genau auf dem blauen EH-Kreis liegen, dessen Mittelpunkt natürlich auch nicht zwingend der Inkreismittelpunkt eines Dreiecks sein muss wie in der Zeichnung. In dem letzten Graphen #1302 liegen alle Knoten auf orangenen Kreisen und deren Schittpunkten.
----------------- Bound to be disappointing so why wait?
haribo
Senior Dabei seit: 25.10.2012 Mitteilungen: 2664
Beitrag No.1311, eingetragen 2018-07-01
moin, wenn dein 5-farb cromatischer ansatz richtig ist dann:
gilt er auch für jede ecke des pinken dreiecks, jede ecke davon kann weder grün/blau/lila/rot sein
da die drei ecken untereinander im dreieck mit kantenlänge 1 liegen, keine davon eine der ersten vier farben haben kann, braucht es also zwingend drei verschiedene neue farben, fünf-sechs-sieben
damit wäre hiermit die behauptung für zwingende siebenfarbigkeit postuliert!!
haribo
Slash
Aktiv Dabei seit: 23.03.2005 Mitteilungen: 8189
Herkunft: Cuxhaven-Sahlenburg
Beitrag No.1315, vom Themenstarter, eingetragen 2018-07-17
2018-07-17 09:09 - haribo in Beitrag No. 1314 schreibt:
kann man irgendwie die artikel lesen? mehr als das inhaltsverzeichniss gelingt mir bisher nicht
haribo
Bei mir geht nach Klicken auf den Link direkt das ganze PDF auf. Sonst einfach mal die arXiv Seite aufrufen und von dort dann das PDF.
2018-07-18 04:35 - haribo in Beitrag No. 1316 schreibt:
ok geht,
und der artikel von Geombinatorics?
Das ist genau dieser Artikel. 😄
Figure 2.
Left, a 3-coloring of de Grey’s graph V31
Right, a 4-coloring of V 151
being V31 ⊕ V 31
verstehst du diesen aufbau in figure2 nachvollziehbar? kopiierter bei V31-31 den ersteren graphen an jeden äusseren punkt und löscht dann alle die weiter als 1 von der mitte entfernt sind? oder rotiert er dabei noch irgend etwas???