MP: Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5 (Forum Matroids Matheplanet)

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

Einsetzkanten = 1/2*Knotengradabweichung + Beweglichkeit +3

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

68 Knoten, 136 Kanten.

[Die Antwort wurde nach Beitrag No.1277 begonnen.]

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;