Die Mathe-Redaktion - Neues auf einen Blick 13.07.2020 03:15 - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5
Thema eröffnet 2016-02-17 22:35 von Slash		Druckversion
Druckversion		Antworten
Antworten
Seite 17   [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52]   52 Seiten
Autor
Kein bestimmter Bereich Streichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.640, eingetragen 2017-01-07


2016-12-10 08:19 - Slash in Beitrag No. 632 schreibt:
Wäre es nicht besser(?) die Kanten der gleichseitigen Dreiecke des Rahmens immer auf 1 zu lassen? Oder würde das den Sinn/Ablauf des Programms über den Haufen werfen?

Das geht jetzt zu machen mit Streichholzgraph-640.htm Button "neue Eingabe, Rahmen zuerst" . Ich zeichne damit den Rahmen aus gleichseitigen Dreiecken zuerst. Dadurch wird gewährleistet, dass am Schluss keine Kanten des Rahmens als zu justierende Kanten übrigbleiben. Auch die inneren Punkte zeichne ich ebenenweise von außen nach innen wie in #221 beschrieben.

Als Eingabebeispiel habe ich den 4/4 mit 108 Kanten genommen. Mit dem blauen Winkel wird der Teilgraph P1 bis P14 näherungsweise gezeichnet und daraus zweimal gespiegelt der gesamte Graph erzeugt.

fed-Code einblenden

Die vier inneren Kanten sind nicht exakt 1 und sollen justiert werden. Die bisherige Eingabe lässt nur symmetrische Lösungen zu, deshalb jetzt den Button "neue Eingabe, Rahmen zuerst" drücken (anschließender Button "Übernehmen" ist nicht mehr erforderlich). Es entsteht folgender Graph, in dem zuerst der Rahmen vollständig gezeichnet wird, mit entsprechend vielen Winkeln.

fed-Code einblenden

Jetzt wäre das Justieren dran. Da passiert aber nicht viel, weil der Graph schon fast stimmt. Deshalb kann man vorher mit Button "innere Punkte zufällig verschieben" die inneren Punkte noch etwas mehr durcheinanderbringen

fed-Code einblenden

und erst dann mit Button "Feinjustieren(5)" den Graph wieder zurechtziehen.

fed-Code einblenden

Momentan darf der Rahmen nur aus gleichseitigen Dreiecken bestehen und die Kanten des Rahmens sollten möglichst schon nahe 1 sein. Bei Bedarf lässt sich das aber noch erweitern.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.641, eingetragen 2017-01-14


Der Doppelkite gehört auch mit zu den acos(1/4)-Graphen, bei denen das GAP-Programm mit exakten Koordinaten rechen kann:

fed-Code einblenden

fed-Code einblenden
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;
cos10p32:=(79+27*Sqrt(5))/(8*(11+3*Sqrt(5)));
sin10p32:=(7*Sqrt(15)-Sqrt(3))/(8*(11+3*Sqrt(5)));
W10p32:=[[cos10p32,-sin10p32],[sin10p32,cos10p32]];
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[5]:=P[2]-(P[1]-P[2]);
P[6]:=P[3]-(P[1]-P[3]);
P[7]:=P[6]+(W60*Wbl)^-1*(P[3]-P[6]);
P[8]:=P[7]+(W60*W60*Wbl)^-1*(P[6]-P[7]);
P[9]:=P[7]+W60*(P[8]-P[7]);
P[10]:=P[1]+W60*(P[9]-P[1]);
P[11]:=P[8]-(P[7]-P[8]);
P[12]:=P[7]+W60*(P[6]-P[7]);
P[16]:=P[11]+W10p32*(P[8]-P[11]);
P[17]:=P[16]-(P[11]-P[16]);
P[18]:=P[17]+W60*(P[12]-P[17]);
P[19]:=P[18]+(W60*W60*Wbl)^-1*(P[17]-P[18]);
P[20]:=P[18]+W60*(P[19]-P[18]);
P[21]:=P[20]+W60*(P[19]-P[20]);
P[22]:=P[19]-(P[18]-P[19]);
P[13]:=P[20]-(P[18]-P[20]);
P[14]:=P[11]+W60*(P[16]-P[11]);
P[15]:=P[13]+W60*(P[14]-P[13]);
Kante:=[
[1,9],[1,10],[1,2],[1,3],[2,3],[3,4],[2,4],[4,5],[2,5],[3,6],[4,6],[6,7],[7,8],[7,9],[8,9],
[8,10],[9,10],[8,11],[10,11],[11,14],[11,16],[7,12],[6,12],[12,17],[12,18],
[13,20],[13,21],[13,14],[13,15],[14,15],[14,16],[15,16],[15,17],[16,17],
[17,18],[18,19],[18,20],[19,20],[19,21],[20,21],[19,22],[21,22],];
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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.642, eingetragen 2017-01-14


2016-03-30 10:16 - haribo in Beitrag No. 149 schreibt:
hier zwei ergebnisse unserer urlaubs untersuchnung betreffs des harborth graphen mit java:

der harborth graph kann sich dabei neben seiner originalversion in zwei weitere stabile formen ziehen, welche aber nicht mehr "4 regular" sind da sie auch 3er und 6er knoten haben, aber nach unserer einschätzung streichholzgraphen sind d.h. die summe aller verbindungslängen näherte sich bis auf 8 komma stellen der ganzen zahl der verbindungen







grus haribo

hallo stefan

ich habe den eindruck das die exaktheit deines programmes sich verbessert hat im laufe des letzten jahres

und drum würde ich gerne nochmal diese beiden verzogenen harborths aus #149 überprüfen, bei denen ich immer noch nicht die exakten einslängen testen kann, bzw nicht entscheiden kann ob die punkte a2/d2 bzw b2/c2 wirklich übereinander rutschen oder noch einen abstand behalten

fals du also zeit dazu findest... das wäre sehr schön
haribo

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.643, eingetragen 2017-01-15


Hallo haribo,
die Punkte a2/d2 müssen zusammenfallen, wenn sie auf der gleichen Seite der Strecke x1-x2 liegen und von diesen den gleichen Abstand 1 haben sollen. Ein 4/4 ist damit ausgeschlossen. Doch mich interessiert auch, was das aktuelle Streichholzprogramm als Ergebnis liefert. Die erste größere Hürde ist momentan, wie ich die Koordinaten der Punkte eingeben kann. Bisher habe ich ja die Graphen so gezeichnet, dass ich die Vorlage als Aufbauvorschrift genommen und von Anfang an Kanten der Länge 1 aneinandergefügt habe und nicht die Originallängen aus der Vorlage. Wenn die Vorlage in Wirklichkeit gar nicht funktioniert, kommt es am Ende zu großen Abweichungen vom Original. Das macht nicht unbedingt einen überzeugenden Eindruck. In der Richtung will ich noch etwas verbessern. Ich stelle mir das so vor, dass man die Grafik als Hintergrundbild in das Programm lädt und dann mit Mausklick und Drag&Drop die benötigten Punkte P1, P2, P3... plaziert und korrigiert. Anschließend die Punkte mit einer Kante verbinden, das geht jetzt schon. Als Notbehelf habe ich den ersten Graph so gut es ging nach Augenschein eingegeben. Ich hoffe, dass ich die wesentlichen Merkmale ausreichend gut hinbekommen habe, beispielsweise sollte c8 unterhalb von Strecke x5-c6 liegen und d2 links von Strecke x1-x2.

fed-Code einblenden

Nach Button "neue Eingabe, Rahmen zuerst" und "Feinjustieren(5)" entsteht dieser Graph

fed-Code einblenden

Der Abstand der Punkte P26 und P28 beträgt 0,00000000000000... das sieht ganz nach Übereinstimmung aus. Außerdem wird innen der Abstand P49-P50 größer als 2, so dass P46 nicht mehr passend gezeichnet werden kann.

Ich habe dann noch zehnmal die vier Buttons "zurück" "zurück"  "innere Punkte zufällig verschieben" "Feinjustieren(5)" gedrückt, doch ein wesentlich anderes Ergebnis ist nicht dabei entstanden.

Den zweiten Graph rechne ich mit einer neuen Programmversion, wo ich die Koordinaten der Punkte hoffentlich besser eingeben kann.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.644, vom Themenstarter, eingetragen 2017-01-16


Gibt es eigentlich noch andere alte Graphen die "rechnerisch" auf der Kippe standen?


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.645, eingetragen 2017-01-21


Beim #315-2 ist noch nicht klar, ob eine Überschneidung auftritt oder nicht. Wegen anschließender neuer Rekorde war das aber nicht mehr aktuell gewesen.

Wie vorgehabt kann ich mit Streichholzgraph-645.htm Graphen genauer nach einer Zeichenvorlage eingeben. Dabei war zu sehen, dass in

2017-01-14 08:14 - haribo in Beitrag No. 642 schreibt:
2016-03-30 10:16 - haribo in Beitrag No. 149 schreibt:





der Winkel c7-c6-c8 mit ca. 144° zu klein ist. Das Viereck x8-d9-x7-c9 ist ein Drachenviereck, deshalb liegen auch die Punkte d7,d8 und c7,c8 symmetrisch zur Diagonalen x8-x7 und die Abstände d7-d8 und c7-c8 müssen gleich lang sein. Deshalb müsste Winkel c7-c6-c8 genauso groß wie Winkel d7-d6-d8 sein, auch wenn einer der Winkel nach Innen geklappt ist. Letzterer ist aber ca. 169° (lässt sich in der neuen Programmversion im Input-Feld Winkel(1,2,3)=..." einstellen und ablesen). Sobald man den Winkel c7-c6-c8 entsprechend vergrößert, lässt sich der Rest des Graphen nicht mehr zeichnen. Entsprechendes gilt auch für den zweiten Graph

2017-01-14 08:14 - haribo in Beitrag No. 642 schreibt:
2016-03-30 10:16 - haribo in Beitrag No. 149 schreibt:





da müsste ebenfalls Winkel c7-c6-c8 genauso groß wie Winkel d7-d6-d8 sein. In der Zeichnung sind über 15° Differenz, so dass auch dieser Graph nicht exakt gezeichnet werden kann.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.646, eingetragen 2017-01-21


hallo stefan

sehr herzlichen dank für deine bemühungen

die drachenvierecke sind eine sehr gute argumentation

aber meine zeichnungen kann man offensichtlich so nicht als messvorlage nehmen

es ist ja lange her, unser program damals hat eine farbunterscheidung gemacht, schwarze linien sind sehr genau eins lang grüne noch nicht

und in den bildern sind ja noch jede menge grüne striche, selbst in den gitterträgerbereichen, welche sich ja schnell als dreiecks-gitter stabilisieren werden

insofern sorry für die bilder in viel zu frühem stabilisierungs-stadium,

meiner erinnerung nach stabilisierte es sich bis alle linien schwarz wurden, aber dabei verändern sich die winkel ggfls noch

leider habe ich keine besseren/exakteren bilder abgespeichert(oder finde sie jedenfals derzeit nicht)

um es in deinem program eingeben zu können muss man wohl immer noch wissen ob ein winkel nach innen oder aussen gedrückt ist, oder? das spielte bei unserem program keine rolle da wir ja jede linie als feder angesehen haben die entweder zieht oder drückt...

im oberen bild die linie b8-x5-c8 ist eine der linien die evtl. auch in die andere richtung geknickt sein könnte

ebenso evtl d7-d8-d6...

(dass symetrische untere bild würde ich derzeit selber nicht weiter untersuchen, das hätten wir längst gefunden wenn es diese lösung geben würde)

grus haribo





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.647, eingetragen 2017-01-22


Selbst wenn ein Winkel immer nur nach einer Seite gedrückt ist, kann man mit dem Streichholzprogramm Lösungen übersehen. Als Beispiel folgende Konstellation

fed-Code einblenden

Daraus soll der 4/4 mit 108 Kanten gemacht werden und dazu muss man den blauen Winkel in P1 so variieren, dass Punkt P53 mit P54 zusammenfällt. Dafür gibt es aber zwei Lösungen, eine bei 20.133° und eine bei 18.881°. Nur eine dieser Lösungen führt zum 4/4 mit 108. Wenn man beI der automatischen Suche zuffällig bei der anderen Lösung landet, welche sich nicht zum fertigen Graph fortsetzen lässt, übersieht man die gesuchte Lösung. Ohne Zutun von Außen kann man mit dem Streichholzprogramm nicht feststellen, dass es keine Lösung gibt.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.648, eingetragen 2017-01-24


zetaX hat in einem anderen zusammenhang auf etwas interessantes hingewiesen:
LinkGesucht: Eulerscher planarer Graph

"Das Dual eines eulerschen planaren Graphen ist bipartit, d.h. die Flächen können so mit den Farben Schwarz und Weiß angemalt werden, dass benachbarte Flächen verschiedene Farben haben. O.B.d.A. sei die Außenfläche weiß."

das gilt also sicher für alle 4-regulär und dann wohl auch für alle 4/n-regulär (wenn n gerade ist)

daraus kann man wohl einiges an informationen ableiten, verhältnisse von inneren und äusseren kanten beispielsweise,

evtl könnte man damit denkbare kleinere 4/4er ausschliessen?
das wäre gut in hinblick auf den geträumten beweis ob harborth´s 104er zu unterbieten sein kann oder nicht

als beispiel hier mal die zweifarbigkeit des 108ers:


haribo

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.649, vom Themenstarter, eingetragen 2017-01-24


2017-01-24 14:30 - haribo in Beitrag No. 648 schreibt:
das gilt also sicher für alle 4-regulär und dann wohl auch für alle 4/n-regulär (wenn n gerade ist)

Ja, das sehe ich auch so.

2017-01-24 14:30 - haribo in Beitrag No. 648 schreibt:
daraus kann man wohl einiges an informationen ableiten, verhältnisse von inneren und äusseren kanten beispielsweise,

evtl könnte man damit denkbare kleinere 4/4er ausschliessen?
das wäre gut in hinblick auf den geträumten beweis ob harborth´s 104er zu unterbieten sein kann oder nicht

Das sehe ich nicht so bzw. nocht nicht.


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.650, eingetragen 2017-01-24


eine aussage kann ich herleiten
erscheint ziemlich trivial aber immerhin

"jeder 4/4er muss dreieckige flächen enthalten":

es gilt der eulersche flächensatz.
knoten+gebiete-hölzer=2

ein 4/4er hat immer doppelt so viel hölzer wie knoten, also

knoten=hölzer/2

drum steht die anzahl der gebiete auch fest

gebiete=2+knoten
gebiete=2+hölzer-hölzer/2
gebiete=2+hölzer/2

zieht man das aussengebiet ab verbleiben
innengebiete=1+hölzer/2

das verhältnis hölzer pro innegebiet beträgt daraus folgend <2
(der harborth hat 104/53=1,96...)

da mit einem oder zwei hölzern kein eigenes gebiet abgetrennt werden kann, für gebiete die grösser als dreiecke sind aber >2 hölzer pro innengebiet erforderlich sind (ein endloses schachbrett käme auf genau 2) muss der graph also dreiecke enthalten

haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.651, eingetragen 2017-01-25


evtl könnte man noch ermitteln wie viele dreiecksflächen es mindestens geben muss bei 102..100..98..hölzern ?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.652, eingetragen 2017-02-02


na die wichtigkeit der Bipartit eigenschaft des graphen-duals bzw 2-färbbarkeit des graphen diskutieren wir besser hier?

ich denke, jede mathematische aussage zu streichholzgraphen sollte erwähnt werden

also 2-färbbarkeit ist mindestens so wichtig wie, dass 4/4er in einer durchgehenden linie gezeichnet werden können, oder das sie aus einer geraden anzahl hölzer bestehen

ob man jetzt weiss oder nicht ob darüberhinausgehende weitere aussagen daraus abgeleitet werden können spielt doch beim sammeln aller informationen keine rolle

haribo

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.653, vom Themenstarter, eingetragen 2017-02-02


Ja, #652 stimme ich zu. Hier ist der richtige Ort dafür. 😄


Hier noch zwei Artikel, die man als PDF im Netz findet und die nicht bei Wikipedia verlinkt sind.

Konstruktion und Eigenschaften ganzzahliger Punktmengen (Kurz)

Plane four-regular graphs with vertex-to-vertex unit triangles (Harborth)


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3613
Aus: Raun
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.654, eingetragen 2017-02-04


2017-01-21 15:48 - haribo in Beitrag No. 646 schreibt:
um es in deinem program eingeben zu können muss man wohl immer noch wissen ob ein winkel nach innen oder aussen gedrückt ist, oder? das spielte bei unserem program keine rolle da wir ja jede linie als feder angesehen haben die entweder zieht oder drückt...

im oberen bild die linie b8-x5-c8 ist eine der linien die evtl. auch in die andere richtung geknickt sein könnte

ebenso evtl d7-d8-d6...
2017-01-22 07:56 - StefanVogel in Beitrag No. 647 schreibt:
Selbst wenn ein Winkel immer nur nach einer Seite gedrückt ist, kann man mit dem Streichholzprogramm Lösungen übersehen.

Button "Feinjustieren" war ursprünglich dafür gedacht und so benannt, in vorliegenden Lösungen wie Lego oder Heftstreifen noch paar Kommastellen Genauigkeit mehr herauszuholen. Da konnte ich davon ausgehen, dass die Winkelkonstellationen im wesentlichen schon stimmen.

Auch wenn es sehr oft gelingt, einen Graph über größere Entfernungen zurechtzuziehen, wegen der genannten Gründe ist Button "Feinjustieren" für das Ausschließen weiter entferner Lösungen nicht geeignet. Man kann es versuchen, hat aber letztendlich keine Gewißheit, dass man keine Lösung übersehen hat.

Dafür müsste eher ein neuer Button "grob Vorjustieren" her, welcher entsprechend der genannten Hinweise systematisch alle möglichen Winkeleinstellungen durchmustert und dabei - eventuell auch mehrere - Lösungsvorschläge mit halbwegs passenden Kanten liefert. Ich versuche nochmal am #645-1 zu testen, wie sowas aussehen könnte und will damit auch nochmal versuchen, dich von der Unlösbarkeit des #645-1 zu überzeugen.

Für das Durchmustern verschiedener Winkeleinstellungen erscheint eine Eingabe mit möglichst wenig beweglichen Winkeln günstiger. Natürlich ohne Verwendung von Symmetriebedingungen und ähnliche Tricks, die eine allgemeinere Lösungssuche wieder verhindern würden.

Ich habe eine Eingabe mit nur einem zu verändernden blauen Winkel verwedet. Der Aufbau des Graphen erfolgt in der Reihenfolge der Punktnummerierung. Von P1 bis P12 gibt es nichts zu variieren und ich habe die in P6 zusammenfallenden Punkte bereits als nur einen Punkt eingegeben. P13 ist der mit blauen Winkel einstellbare Punkt. Anschließend kann P14 nur nach einer Seite gezeichnet werden, auf der anderen Seite wird die Entfernung zu P3 zu groß. Jedoch kann P15 nach beiden Seiten gezeichnet werden, den zweiten Punkt bezeichne ich als P99, das ergibt die erste Fallunterscheidung. Der blaue Winkel geht nur zwischen 0° und 72° zu variieren, sonst wird P14-P3 zu groß. Weiter geht es eindeutig mit P17 bis P27. P28 geht wieder nach zwei Seiten zu zeichnen, die Variante nach außen führt zum #645-2, welcher nicht weiter untersucht werden sollte, also P28 nach innen. Dann P29 bis P33 eindeutig. P34 geht nur nach oben zu zeichnen, unterhalb gibt es Überschneidung für jeden möglichen blauen Winkel. Dann eindeutig P35 bis P40. P41 geht nach beiden Seiten zu zeichnen, das ergibt die zweite Fallunterscheidung und ich gebe zu, dass ich diese zusätzliche Variante bisher nicht beachtet habe. Aber erstmal weiter mit P41 nach oben und dann eindeutig P42 bis P46. P47 könnte man auch überschneidungsfrei nach innen zeichnen, doch gibt es dann keine Fortsetzung. Von P43 aus ist schon das Ziel P1 in Sicht, der Abstand P43-P1 muss exakt 2 sein.

fed-Code einblenden

Abstand P43-P1 muss ich jetzt mit dem blauen Winkel auf Länge 2 einstellen und zwar schrittweise alle möglichen Winkeleinstellungen durchmustern, damit auch mehrere Lösungsmöglichkeiten erkannt werden. Ich gebe das auszugsweise so wieder:

fed-Code einblenden

Nach Betrachtung des ganzen Bewegungsablaufes von 72° bis 0° in 1°-Schritten scheint es wirklich nur eine Möglichkeit P43-P1 gleich 2 zu geben, die aber nicht weiter zum fertigen Graphen vervollständigt werden kann. Auch die zweite Fallunterscheidung P41 nach unten, da ersetze ich nur Eingabe N(41,36,34) durch N(41,34,36),

fed-Code einblenden

hat nur eine Möglichkeit für P43-P1 gleich 2 und das kann auch nicht fertig gezeichnet werden. #645-1 geht nicht exakt zu zeichnen.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.655, eingetragen 2017-02-04


hallo stefan
du kannst inzwischen wirklich sehr sehr schöne graphiken erstellen,

mein java-programier-freund war just gerade kurz zu besuch... aber ohne rechner... er schaut die nächsten tage nochmal die beiden graphen an evtl findet er dann unseren rechenfehler(?), also wiso unsere gesamtsumme aller längen sich einer ganzen zahl annäherte obwohl die ergebnisse nach deinen versuchen unmöglich stimmen können... irgendwie muss sich dieser wiederspruch ja auflösen lassen

auch er hat seit langen nichts mehr weiterentwickelt, muss sich also wieder erst etwas hineindenken...

immerhin wusste er spontan das meine erinnerung mich trog in #646
"es ist ja lange her, unser program damals hat eine farbunterscheidung gemacht, schwarze linien sind sehr genau eins lang grüne noch nicht"

es war genau andersherum, die grünen linien sind exakter als die schwarzen, die dreiecke hatten sich schon besser stabilisiert als der rest, von den entscheidenden winkeln rechts und links des drachenvierecks sind aber jeweils noch drei schwarz, der bereich war beim bilderabspeichern also sicherlich noch in bewegung



haribo



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.656, eingetragen 2017-02-04


jede erkenntniss führt zu neuen fragen

das nachdenken über die 2-färbbarkeit der felder eines 4-gerade graphen führt zu der frage wie es eigendlich mit der färbbarkeit der 4-ungerade graphen bestellt ist

sind die immer 3-färbbar?

fals ja, wie viele/wenige flächen benötigen die 3. farbe?

und nach kurzem nachdenken darüber kam die nächste frage, ist es möglich die ungeraden knoten, welche sich bei uns bisher immer im inneren der graphen befinden richtung rand wandern zu lassen? möglicherweise sogar auf dem rand anzuordnen?

hier ein erster versuch eines 4-5er mit nach aussen wandernden 5er knoten, noch befinden sie sich im inneren

bei diesem graphen würde es reichen das feld mit dem text in 3. farbe zu färben, der rest wäre dann wieder 2-färbbar

kann dass(ein einzelnes 3.-farb-feld) auch funktionieren wenn es einem gelingt den 5er knoten (oder sogar beide?) auf den rand zu legen?
haribo


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.657, vom Themenstarter, eingetragen 2017-02-04


Hier ein 4/5 bei dem 50% der 5er-Knoten außen liegen.



Geht vielleicht noch minimaler mit großen Kites.

Das alle n-Knoten mit n > 4 außen liegen ist wohl nur für n = 6; 8; 10 möglich.


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.658, eingetragen 2017-02-04


hab einen gefunden

lässt sich auch mit einer einzigen (x) drittfarb fläche 3-farbig färben



kann man auch noch weiter zusammenklappen die beiden doppelender, es gibt also noch diverse varianten

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.659, vom Themenstarter, eingetragen 2017-02-04


Super haribo!

Habe gerade auch einen gefunden, aber nicht so schön einfach wie deiner.

Man kann ihn so färben, dass die Außenfläche eine dritte Farbe benötigt.




-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.660, eingetragen 2017-02-04


ach jetzt ist mir noch einer eingefallen.... grins


und das unerwartete daran ist, der ist sogar 2-färbbar !


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.661, eingetragen 2017-02-04


det kann eigentlich gar nicht sein

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.662, vom Themenstarter, eingetragen 2017-02-04


Jetzt bin ich aber platt bzw. planar! 😁


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.663, eingetragen 2017-02-04


na die verbindungslinie hätte dann von beiden seiten die aussengebietsfarbe... das geht wohl nicht

bedeutet dass dann der ist gar nicht färbbar? das wäre jedenfals auch unerwartet

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.664, vom Themenstarter, eingetragen 2017-02-04


2017-02-04 22:30 - haribo in Beitrag No. 663 schreibt:
na die verbindungslinie hätte dann von beiden seiten die aussengebietsfarbe... das geht wohl nicht

bedeutet dass dann der ist gar nicht färbbar? das wäre jedenfals auch unerwartet

Tja, seltsam. Hier muss mal ein Graphentheoretiker argumentieren.


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.665, eingetragen 2017-02-04


wirklich?  wenn ich nur die flächen fülle also nur zwei farben benutze dann verschwinden doch die linien, bzw entstehen als abgrenzung nur im farbsprung zwischen den beiden farben

eine linie mit der gleichen farbe von beiden seiten hat aber keinen farbwechsel/farbsprung

insofern kann ich diesen graph, nach zweifärbung, nicht von zwei lose nebeneinander liegenden harborths unterscheiden ???



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.666, vom Themenstarter, eingetragen 2017-02-04


Hast recht, hatte den Beitrag schon editiert. 😄


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.667, vom Themenstarter, eingetragen 2017-02-04


Es geht in der Graphentheorie bei der Färbbarkeit planarer Graphen ja um die Färbung der Knoten. Jeder Harborth ist für sich 3-färbbar. Wenn man beide Graphen gleich färbt und die Verbindungskante bei einem der beiden Graphen einen Knoten weitersetzt funktioniert die 3-Färbbarkeit. Oder man tauscht beim zweiten Graphen die Farben.





-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.668, eingetragen 2017-02-04


na, es ging mir seit #668
LinkStreichholzgraphen 4-regulär und 4/n-regulär (n>4) und 2/5

um die färbbarkeit des duals des graphen, also um die flächeneinfärbung, als teil der bipartit eigenschaften

und dabei um die frage wann es 3-färbbare flächen sind und wann 2-färbbare

ich frag mal zetaX ob er uns helfen mag
von dem kam ja die idee

haribo

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.669, vom Themenstarter, eingetragen 2017-02-04


Lösen kann man das Flächenfärbungsproblem mit einer weiteren Verbindungskante. Aber dieser spezielle Fall mit einer Kante muss natürlich geklärt werden.




-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.670, vom Themenstarter, eingetragen 2017-02-05


Aus Langeweile hier ein 4/9 und 4/10 mit Außenknoten.




-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.671, vom Themenstarter, eingetragen 2017-02-05


Hier mein Versuch einen 4/7 mit 7er-Außenknoten und nur einer Verbindungskante zu zeichnen. Die rote Kante ist aber immer länger als 1.




-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.672, vom Themenstarter, eingetragen 2017-02-05


Drei 4/7 mit 7er-Außenknoten.


Geht natürlich auch mit Harborths.




-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.673, vom Themenstarter, eingetragen 2017-02-05


2017-02-04 22:38 - haribo in Beitrag No. 665 schreibt:
wirklich?  wenn ich nur die flächen fülle also nur zwei farben benutze dann verschwinden doch die linien, bzw entstehen als abgrenzung nur im farbsprung zwischen den beiden farben

eine linie mit der gleichen farbe von beiden seiten hat aber keinen farbwechsel/farbsprung

insofern kann ich diesen graph, nach zweifärbung, nicht von zwei lose nebeneinander liegenden harborths unterscheiden ???



Mittlerweile glaube ich, dass diese Verbindungskante gar nicht als Grenze zählt, der Graph also wirklich 2-färbbar und ein Sonderfall ist.


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.674, eingetragen 2017-02-05


sonderfall? reduzieren wir mal die frage auf diesen 2/3


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.675, eingetragen 2017-02-05




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.676, vom Themenstarter, eingetragen 2017-02-05


Ich denke, es ist einfach eine Definitionssache was hier mit Färbbarkeit gemeint ist. Letztendlich unterliegen alle diese Graphen den geltenden Beweisen zur Färbbarkeit. Eine einzige Kante mit zwei Knoten ist zwingend 3-färbbar.

Die Färbbarkeit die du meinst (soweit ich dich verstanden habe) ist ja immer auf die "normale" Knotenfärbbarkeit zu übertragen, indem man in jede Fläche einen Knoten setzt und daraus einen Graph bildet. Und dafür gibt es ganz strenge graphentheoretische Gesetze.

Bei den zwei verbundenen Harborths oder dem letzten Graphen wird wohl graphentheoretisch etwas durcheinander geworfen. Aber warten wir mal auf eine dritte Meinung. 😄

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


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.677, eingetragen 2017-02-05



wer schafft den 4/11er mit einer verbindungskante ???????????????





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.678, eingetragen 2017-02-05


was ist ein dualgraph?

ich dachte bisher eine fläche wird zu einem knoten und ein knoten zu einer fläche

also wäre der dualgraph eines 2-flächenfärbbaren graphen dann einer der 2-farbig knotenfärbbar sein muss, oder?

dann besteht die frage evtl darin: "zu welchem knoten wird die aussenfläche???"
haribo

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7981
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.679, vom Themenstarter, eingetragen 2017-02-05


Also wenn ich mein Graphentheoriebuch zur Färbbarkeit richtig verstanden habe, dann ist sowohl der Doppelharborth aus #660 und der aus #674 und aus #677 2-färbbar, wobei ich die Graphenbilder als Landkarte interpretiere. Eine einzige endliche Kante kann eine unendliche Fläche nicht teilen.

Was die Begrifflichkeiten angeht, das muss man sorgfältig prüfen, also die Definitionen und so weiter. Aber von der reinen Flächenfärbbarkeit sind die obigen Graphen und alle ähnlichen Fälle 2-färbbar.


-----------------
Bound to be disappointing so why wait?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 17Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]