Matroids Matheplanet Forum Index
Moderiert von Cousinchen
Matroids Matheplanet Forum Index » Spiel & Spaß » Pflasterungen mit L-förmigen Steinen
Seite 1   [1 2]   2 Seiten
Autor
Universität/Hochschule Pflasterungen mit L-förmigen Steinen
viertel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen
  Themenstart: 2016-02-02

[Dieser Thread wurde abgespalten von [diesem Thread] von viertel] Ein 3×12 Streifen kann mit 9 Steinen ja nicht gelegt werden. Aber eine 3-fach vergößerte Version des L schon: http://matheplanet.com/matheplanet/nuke/html/uploads/9/1781_Anzahl_der_Pflasterungen_mit_L-foermigen_Steinen_209955.png Ebenso ist eine 5-fache Vergrößerung möglich: http://matheplanet.com/matheplanet/nuke/html/uploads/9/1781_Anzahl_der_Pflasterungen_mit_L-foermigen_Steinen_B_209955.png Hier kann man die Frage stellen, ob auch eine Zerlegung möglich ist, die mit 3 Farben auskommt. Zu Zeichnen des ersten Bildes habe ich übrigens eine etwas andere Definition für den Grundbaustein benutzt: \sourceon Stein(X, Y, LX, LY) \sourceoff Dabei ist X,Y die Position des Ecksteines, und LX,LY die Länge des Steines in X,Y-Richtung (auch negative Werte möglich). Damit sind dann sogar Winkel mit beliebiger Schenkellänge möglich.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.1, eingetragen 2016-02-02

\quoteon(2016-02-02 03:06 - viertel in Beitrag No. 7) Hier kann man die Frage stellen, ob auch eine Zerlegung möglich ist, die mit 3 Farben auskommt. \quoteoff Ich habe diese gefunden. Hat aber auch eine halbe Stunde gedauert. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_slashloesung.png Auffällig ist hier, dass man die Lösung in ein großes Rechteck und ein gequetschtes L teilen kann. Diese beiden Strukturen finden sich dann im kleinen 2 bzw. 5 mal wieder. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_Slash_L_ung_2.png


   Profil
Martin_Infinite
Senior Letzter Besuch: im letzten Monat
Dabei seit: 15.12.2002
Mitteilungen: 39133
Wohnort: Münster
  Beitrag No.2, eingetragen 2016-02-02

Schön. In diesem Thread geht es um $n \times 3$-Pflasterungen. 1/4: Einwand erledigt, da vom ursprünglichen Thread abgespalten wurde.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.3, eingetragen 2016-02-02

http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_LLLs.png dreifarben bestehend aus 2 ähnlichen bereichen, die blauen liegen gleich in beiden bereichen, die anderen L´s sind auch lagegleich aber jeweils in der farbigkeit rot-gelb vertauscht der übergang kann gelb oder rot sein, auch 4 andere L´s könnte man blau wählen gibt also vermutlich recht viele verschiedene dreifarbige varianten gruss haribo


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.4, eingetragen 2016-02-02

http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_LL.png 3-fach und 5-fach im selben bild


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.5, eingetragen 2016-02-02

Schöne Lösung haribo! Und da sage nochmal einer, L sei nur irgend so ein langweiliger Buchstabe. Ich denke, ich werde jetzt erstmal 'ne Runde Tetris spielen. ;-)


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.6, eingetragen 2016-02-03

http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_LLLL.png na dann entwickeln wir doch ein spiel, slash haribo


   Profil
Zetavonzwei
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
  Beitrag No.7, eingetragen 2016-02-03

Hallo, ob das wohl auch unbegrenzt fraktal möglich ist? Sprich ein großes L, das aus kleineren L besteht, die wiederum aus kleineren L bestehen..., sodass keine zwei "kleinsten" benachbarten L die gleiche Farbe haben und das ganze mit drei Farben. Ich mach mich mal ans Basteln. Viele Grüße Zvz


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.8, eingetragen 2016-02-03

einser,zweier,vierer und achter L´s sind wohl mit drei farben herstellbar auch wenn derzeit ohne festes schema http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_LLLLL.png


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.9, eingetragen 2016-02-06

es erscheint mir weiterhin nicht sooo kompliziert dreifarben einzuhalten, manche bereiche funktionieren sogar zweifarbig, obwohl es ja bei manchen anordnungen nicht funktioniert mit der dreifarbigkeit, beispielsweise bei viertels zweitem bild im startbeitrag... warum? gruss haribo http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_LLLLLL.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.10, eingetragen 2016-02-06

\quoteon(2016-02-06 19:47 - haribo in Beitrag No. 9) ..., beispielsweise bei viertels zweitem bild im startbeitrag... warum? \quoteoff Das ist graphentheoretisch (Färbbarkeit) begründet. Der Graph enthält "mindestens" einen minimalen 4-färbbaren Untergraphen. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_5.png Jedes L darf für eine 3-färbbarkeit nur von einer geraden Anzahl L's umgeben sein bzw. angrenzen, denn Ecke an Ecke zählt ja nicht. Ein zweiter minimaler 4-färbbarer Untergraph liegt direkt links daneben, mit dem grünen L in der Mitte. Deshalb wird dieses Bild immer mindestens zwei L in einer vierten Farbe benötigen - ganz egal wie man umfärbt. (Ich bin aber nicht zu 100% sicher, ob diese Begründung als Beweis ausreicht. Also für diese "2 L" Behauptung.)


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.11, eingetragen 2016-02-06

Hallo, -- mfg matph


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.12, eingetragen 2016-02-06

Das macht sich sogar als Pop-Art an der Wand gut. :-)


   Profil
Martin_Infinite
Senior Letzter Besuch: im letzten Monat
Dabei seit: 15.12.2002
Mitteilungen: 39133
Wohnort: Münster
  Beitrag No.13, eingetragen 2016-02-06

Mit den Stichworten • L-Tetromino • Rep-Tiling findet man sicherlich noch mehr solcher Bilder in Büchern und mit google.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.14, eingetragen 2016-02-06

Hier mal eine 3D Version. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_3d_L.jpg


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.15, eingetragen 2016-02-06

\quoteon(2016-02-06 20:56 - Slash in Beitrag No. 10) Jedes L darf für eine 3-färbbarkeit nur von einer geraden Anzahl L's umgeben sein bzw. angrenzen, denn Ecke an Ecke zählt ja nicht. \quoteoff http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L5.png nicht das ich sicher bin das man diese fläche rundherum durchgehend schliessen könnte, aber es sind 5 angrenzende L´s und dazu noch "nur eine farbe" durch die eckensituation ergibt sich also offenbar noch irgend eine andere regel ? gruss haribo [Die Antwort wurde nach Beitrag No.13 begonnen.]


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.16, eingetragen 2016-02-06

Korrekter Einwand - es ist ungenau formuliert. Diese Ecksituation ist wie eine einzige Fläche. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_3_b.png Richtiger wäre wohl: Jedes L darf für eine 3-färbbarkeit nur von einer geraden Anzahl > 2 L's umgeben sein, die per Kante aneinandergrenzen. Bei einer Ecksituation zählt man je 1 zur Anzahl dazu. Das wäre dann hier 5+5=10. Dies funktioniert aber nicht bei L's die am Rand liegen.


   Profil
matph
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2006
Mitteilungen: 5506
Wohnort: A
  Beitrag No.17, eingetragen 2016-02-07

Hallo, Habe noch 2 weitere Bilder erstellt :-)
-- mfg matph



   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.18, eingetragen 2016-02-07

neun ist auch ungerade es muss irgendwie anders formuliert sein... http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L5b.PNG [Die Antwort wurde nach Beitrag No.16 begonnen.] sehr schön matph!


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.19, eingetragen 2016-02-07

Naja, ganz sicher ist diese Formulierung: Jedes L darf nur so von anderen L's komplett umgeben sein, dass aus den Flächen dieser L's (5 bis 13) kein zwingend 4-färbbarer (Unter)graph entsteht. Hier mal eine Min-Max-Version aus 5 und 13 Flächen bzw. L's: http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_4_12.png Der graue Rahmen verdeutlicht die umgebenden Flächen.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.20, eingetragen 2016-02-07

http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L_5b.png hi slash, das untere blaue L hat bei der anordnung gar kein einzeln verfügbares "eckfeld", und ne ungerade anzahl nachbarn, das ist also zwingend 4-farbig wie du es in #10 begründet hast, hätte er eins (oder mehrere)freie "eckfelder" dann wäre es egal ob er ne gerade oder ungerade anzahl weiterer felder in der berührungs-umgebung hat, es könnte immer eine dreifarben lösung geben (siehe mittelskizze) umfärben ohne lageänderung im rechten bild zeigt: das 2. linke blaue L ist nicht lagefest, es könnte auch ein anderes L blau sein, also kann auch nicht die direkte umgebung eines L´s alleine die vierfarbigkeit definieren... es scheint noch einen ganz anderen ansatz zu brauchen um die zwingende 4-färberei eines ganzen bereiches zu begründen es wäre eine frage ob man den 4-färbbaren bereich auf eine beschränkte anzahl L´s eingrenzen kann??? also in welchem bereich der blaue irgendwo sein muss


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.21, eingetragen 2016-02-08

\quoteon(2016-02-07 23:48 - haribo in Beitrag No. 20) umfärben ohne lageänderung im rechten bild zeigt: das 2. linke blaue L ist nicht lagefest, es könnte auch ein anderes L blau sein, \quoteoff Das ist ja klar. Habe nie etwas anderes behauptet.(siehe #10) \quoteon also kann auch nicht die direkte umgebung eines L´s alleine die vierfarbigkeit definieren... \quoteoff Doch, aber nur wie zuvor in #19 beschrieben, wenn ein L Mittelstein eines zwingend 4-färbbaren Untergraphen ist. Man muss aber zwischen "zwingender Färbbarkeit" und "Umfärben" unterscheiden. Noch einmal anders: "Eine endliche Fläche, die lückenlos mit L-Steinen (bestehend aus 4 Quadraten) parkettiert ist, ist genau dann mindestens 3-färbbar, wenn jedes L mit seinen direkt angrenzenden Nachbarn* keinen zwingend 4-färbbaren Untergraphen bildet." Eine zwingende 4-Färbbarkeit ist z.B. immer genau dann gegeben, wenn der Mittelstein jeden Nachbarn per Kante berührt, jeder Nachbar seine zwei Nachbarn per Kante berührt, und die Anzahl der Nachbarn ungerade ist. *die angrenzenden L's müssen einen lückenlosen Rahmen von mindestens einem Quadrat bilden. Wenn auch nur "ein zwingend 4-färbbarer Untergraph" enthalten ist, dann kann nicht so umgefärbt werden, dass der ganze Graph nur drei Farben benötigt. Selbst wenn die Fäche noch so groß ist. Ein Umfärben ist aber immer möglich(endlich oft). Eine Farbreduzierung aber nicht. Nehmen wir nochmal den Teilbereich aus Viertels Startbeitrag. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_zwingend.png Davon ausgehend kann man jetzt die Ebene(egal wie groß) lückenlos mit L's parkettieren und auch umfärben - aber dieser Teilbereich wird immer 4 Farben benötigen. Es gibt auch nur endlich viele Möglichkeiten(Teilgraphen), wie ein L von anderen L's (mindestens 4, höchstens 12, siehe #19) umgeben sein kann. Die könnte man auch alle auflisten. Ist aber wohl nicht nötig. Ich habe allein für die kleinste 4er Version 15 Möglichkeiten gefunden, Drehungen, Spiegelungen und Farbtausch ausgenommen. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_4er_15b.png Gruß, S-L-ash


   Profil
viertel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 04.03.2003
Mitteilungen: 27784
Wohnort: Hessen
  Beitrag No.22, vom Themenstarter, eingetragen 2016-02-08

Da wäre noch die Frage zu stellen, ob die direkte Nachbarschaft (Umschließung) notwendig ist, oder ob es auch Fernwirkungen gibt, so daß auch nicht direkt benachbarte Steine eine 4-Färbung erzwingen. Anders ausgedrückt: lokal 3-färbbar, aber irgendwo gibt es einen/mehrere Stein/e, so daß 4 Farben notwendig werden. Ist das möglich (ich weiß es nicht)? Vielleicht muß man dazu wirklich mal alle möglichen Umschließungen eines Steins auflisten. An den Fuß des roten Steins kann der grüne auf 10 Arten (ein Stein hat 10 Kantensegmente der Länge 1) angelegt werden (Nr.5 lebt zwar, ist aber natürlich sinnlos): http://matheplanet.com/matheplanet/nuke/html/uploads/9/1781_Pflasterungen_mit_L-foermigen_Steinen_216136_ANI.gif An jede dieser Konstellationen sind nun weitere Steine anzulegen, die zumindest den roten an einer Kante berühren. Damit baut sich dann der ganze Baum der möglichen Umschließungen auf. Ich habe jetzt aber nicht den Nerv, das durchzuziehen


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.23, eingetragen 2016-02-08

Ich hätte nicht gedacht, dass es so kompliziert wird. Vielleicht muss uns aber auch nur mal ein Graphentheoretiker auf die Finger klopfen. :-)


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.24, eingetragen 2016-02-08

ich würde sagen das es in diesem bereich von viertels anordnung keine direkten umgebungszwänge gibt, d.h. wenn ich unten mit stein 1 und 2 anfange dann ist stein 3 zwingend in einer dritten farbe zu wählen, bei dem 4. stein kann ich wieder wählen und je nach wahl führt es entweder beim 5, oder eben beim 11. stein dann zwingend zur vierten farbe, beide varianten sind hier dargestellt [z steht für zwingend] möglicherweise kann man durch andere wahl der färbe reihenfolge auch noch andere steine als zwingend blau (also vierte farbe) färben, es gibt aber sicher keine lösung alleine mit drei farben also weder der 5. noch der 11, stein mit seiner direkten umgebung ist zwingend vierfarbig, aber das gesammte feld ist insgesammt nicht dreifarbig einzufärben also ist hier eine "fernwirkung" gegeben http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L_5c.png


   Profil
Zetavonzwei
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.03.2012
Mitteilungen: 634
Wohnort: Bamberg, Deutschland
  Beitrag No.25, eingetragen 2016-02-08

Hallo, das Dreifärbbarkeitsproblem ist ja bekanntermaßen (i.A.) NP-vollständig, daher verwundert es nicht, dass es etwas komplizierter wird. Jedenfalls kann ich immerhin ein (nahezu triviales) Teilresultat liefern: a) Wenn der Vergrößerungsfaktor durch 4 teilbar ist, kann man mit der von matph in #11 angedeuteten Methode einen zweifärbbaren Graphen erreichen. (Das liegt an der Regelmäßigkeit, bzw. daran, das $4\times 4$-Blöcke entsprechend gefärbt werden können) b) Für $4^n$-Blöcke ist diese Anordnung zusätzlich $n$-fach fraktal. Möglicherweise gibt es ja eine Methode, Dreifärbbarkeit beim Schritt von $n$ auf $n+4$ aufrechtzuerhalten... Viele Grüße Zvz


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.26, eingetragen 2016-02-08

zu #24 und der Fernwirkung Wird müssen unbedingt unterscheiden zwischen einer beliebig großen Fläche, die es zu parkettieren gibt, und einer L-förmigen Fläche von bestimmter Größe. Ich beziehe mich bisher nur auf beliebig großen Flächen. Bei L-Flächen, die nur 5 Quadrate breit sind, wird es immer eine Fernwirkung geben können, bedingt durch die nahen Ränder. In Viertels Bild gibt es zwei zwingend 4-färbbare Untergraphen. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_zweifach.png Meine Theorie war(#10), dass es deshalb 2 L in vierter Farbe geben muss. Eine "Fernwirkung ohne mindestens einen zwingend 4-färbbaren Untergraphen" wird es wohl nicht geben. Wenn doch, dann müsste sie ja nur durch die zu parkettierende FLäche bedingt sein. Vielleicht findet jemand für eine L-Fläche solch eine "Fernwirkung". Aber ich glaube nicht daran.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.27, eingetragen 2016-02-08

Eine L-Fläche(5er Breite) mit nur einem zwingend 4-färbbaren Untergraphen ist mit nur einem L in vierter Farbe möglich. Die Parkettierungen sind hier natürlich andere als bei Viertel. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_5er_1_1.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.28, eingetragen 2016-02-09

So, Fernwirkungsproblem teilweise gelöst. :-) Ich habe Viertels Bild (1) im unteren Teil neu parkettiert (2), so dass kein zwingend 4-färbbarer Untergraph mehr enthalten ist. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_zwangviertel.png Jetzt sieht man: 1 und 2 erzwingt 3, 1 und 3 erzwingt 4, 3 und 4 erzwingt 5, 3 und 5 erzwingt 6, 5 und 6 erzwingt 7, 4 und 7 erzwingt 10, 7 und 10 erzwingt 9, 6 und 7 erzwingt 8, und 7,8,9 erzwingen den blauen Stein in vierter Farbe. Die Fernwirkung hat also nichts mit dem(oder beiden) zwingend 4-färbbaren Untergraphen im unteren Teil zu tun. Da lag ich falsch. Vielmehr entpuppt sich eine darüberliegende Struktur aus 9 L-Steinen als größerer zwingend 4-färbbarer Untergraph. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_zwangneu.png Eine Erklärung dafür liefert die Theorie der Färbbarkeit planarer Graphen. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_planar_zahlen.png Beweis: Der äußere Kreis besteht aus den sieben Knoten 3 bis 9. Wegen der ungeraden Anzahl wird für mindestens einen dieser Knoten eine dritte Farbe benötigt. Knoten 1 grenzt immer an mindestens zwei Knoten verschiedener Farbe und benötigt deshalb selbst eine dritte Farbe. Dasselbe gilt für Knoten 2. Weil Knoten 1 und 2 verbunden sind, können beide nicht gleich gefärbt sein. Die Knoten 2 bis 7 können abwechselnd gefärbt sein, und dazu die Knoten 1 und 9 "oder" 1 und 8 in einer dritten Farbe. Weil Knoten 8 und 9 verbunden sind, können beide nicht gleich gefärbt sein. Also wird für einen dieser Knoten eine vierte Farbe benötigt. Zusatz: Es kann so umgefärbt werden, dass jeder der neun Knoten der einzige in vierter Farbe ist. Neue Fragen: Wie groß können diese zwingend 4-färbbaren Untergraphen werden? Voraussetzung ist: Minimalität und nur ein Stein in 4ter Farbe. Beliebig groß oder gibt es nur, bedingt durch die Form der L-Steine, endlich viele? Von den einfachsten zwingend 4-färbbaren mit einem Mittelstein in vierter Farbe gibt es nur drei Arten, nämlich mit 5, 7 und 9 umschließenden Steinen, wie z.B. in #10. Natürlich in unterschiedlichen Varianten.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.29, eingetragen 2016-02-09

\quoteon(2016-02-09 02:17 - Slash in Beitrag No. 28) Neue Fragen: Wie groß können diese zwingend 4-färbbaren Untergraphen werden? Voraussetzung ist: Minimalität und nur ein Stein in 4ter Farbe. Beliebig groß oder gibt es nur, bedingt durch die Form der L-Steine, endlich viele? \quoteoff hallo slash, da hat es dich ja gepackt.... sehr schön! ich vermute die zwingend 4-färbbaren untergraphen mit 1 einzigen 4.farbe können nicht sehr viel grösser werden, ich denke man muss den inneren bereich des untergraphen untersuchen: man kann die 4.farbe immer aus dem randbereich des untergraphen nach innen verdrängen A: ich grenze einen deiner untergraphen mit "u" aussen ab, und definiere einen inneren randbereich, der sich dadurch kennzeichnet das jede darinnenliegende farbfläche "u" noch berühren muss. nach innen grenze ich den randbereich also mit "r1" ab B: man könnte jetzt einen parkett-ring aussen um "u" herumlegen und diesen mit der 4. farbe (hier grün) einfärben. es muss jetzt eine einfärbung geben die dieses gesamt parkett mit 4 farben abbildet (4 farben reichen ja für jede 2D parkettierung aus). es muss also hier umgefärbt werden da hier noch unten links ein grünes L unerlaubt an den rand angrenzt C: da der rand die 4. farbe hat kann sie im übergangsbereich nicht nochmal vorkommen... also kann der zwischenbereich zwischen "u" und "r1" immer dreifarbig bleiben http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_4-farbe.png wir haben jetzt bisher 2 verschiedene vierfarb untergraphen gehabt, einmal war nur ein einziges feld innerhalb von "r1" und bei diesem grösseren jetzt sind es zwei felder, also wäre als nächstes ein dreifeldriges zu suchen.... etwas anderes: mit obiger ABC argumentation kann man auch zeigen das die 4. farbe bei gar keiner geometrie im randbereich vorkommen muss, und ich vermute das man damit zeigen kann das jedes beliebige parkett mit einem schmalen übergangsbereich "s1" von einem feld auf ein zweifarbiges schachbrett abgelegt werden kann, und sogar unabhängig der ausrichtung zu #26 insofern muss man doch eben nicht unterscheiden ob ein teilfeld klein ist oder unendlich, da man ja jedes kleine wie ein unendliches schachbrett ausdehnen könnte http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_4farbschach.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.30, eingetragen 2016-02-10

Hi haribo, habe noch nicht alles aus deinem letzten Beitrag verstanden bzw. verarbeitet. Ich glaube einen größeren zwingend 4-färbbaren Untergraphen aus 13 Steinen gefunden zu haben. Dabei sind 2 Mittelsteine von 11 weiteren umgeben. Er ist nicht weiter reduzierbar. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_2er_13_neu_b.png Im Vergleich mit dem anderen Graphen zeichnet sich eine Regel ab. Für einen minimalen nicht weiter reduzierbaren zwingend 4-färbbaren L-Graphen mit 2 Mittel-Knoten muss jeder der beiden Mittel-Knoten mit einer geraden Anzahl der äußeren Kreis-Knoten verbunden sein. Die Anzahl der Knoten des äußeren Kreises muss dabei ungerade sein. Nur "ein einziger" Kreis-Knoten darf mit "beiden" Mittel-Knoten verbunden sein. Nach diesem Rezept lassen sich nun planare Graphendiagramme konstruieren, dessen Umsetzung mit L-Steinen man dann ausprobieren muss. Da ein L-Stein ja nur 9 Kontaktflächen für Quadrate besitzt ist das Problem wohl überschaubar.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.31, eingetragen 2016-02-10

dann geht auch dieser 16 steinige graph ?? er hat aber immer noch nur 2 innenliegende L´s wichtig scheint zu sein das die eckfelder (mit x makiert)jeweils die farbe einer der beiden nebenliegenden kantenfelder haben... http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L16-2.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.32, eingetragen 2016-02-10

Nein, der Graph ist nicht minimal, also reduzierbar. Es steckt schon einer mit einem Mittelstein (blau) und 9 Umschließenden drin. Die oberen 6 Steine sind also überflüssig für eine 4-Färbbarkeit. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_L_graph9.jpg Auch das grüne L kann Mittelstein mit 9 Umschließenden sein. Alle Umschließenden L's berühren sich per Kante und auch den Mittelstein. Es sind also zwei "verschmolzene" einfache minimale 9er Graphen. Hier mal die drei möglichen Arten nicht reduzierbarer minimaler 4-färbbarer L-Graphen mit einem Mittelstein, von denen es jeweils noch viele Variationen gibt. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_3_5_9_b.png


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.33, eingetragen 2016-02-10

bei diesem 15-2 könnte jeder einzelne alleine aus der notwendigen 4. farbe bestehen, das ist dann doch wohl nicht reduzierbar (?) http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L15-2.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.34, eingetragen 2016-02-10

Sehr gut, haribo! Ich denke, der ist in Ordnung. Ja, wenn jeder Stein in vierter Farbe gefärbt werden kann bzw. wenn drei Farben ausreichen bei Wegnehmen eines Steines, dann ist er nicht reduzierbar. Er erfüllt auch die Regel: Für einen minimalen nicht weiter reduzierbaren zwingend 4-färbbaren L-Graphen mit 2 Mittel-Knoten muss jeder der beiden Mittel-Knoten mit einer geraden Anzahl der äußeren Kreis-Knoten verbunden sein. Die Anzahl der Knoten des äußeren Kreises muss dabei ungerade sein. Nur ein einziger Kreis-Knoten darf mit beiden Mittel-Knoten verbunden sein. Jetzt haben wir die Mittel-2er mit 7, 11 und 13 Umschließenden. Kann es einen mit 3 Mittel-Steinen geben? Ich glaube nicht. Aber wer weiß?


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.35, eingetragen 2016-02-11

So, vielleicht gibt es doch einen mit 3 Mittelsteinen? Testet mal. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L_3er_13_neu.png


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.36, eingetragen 2016-02-11

Rechts außen die beiden (grün+gelb)kann man jeweils weglassen und braucht immer noch 4 Farben, evtl geht's wenn da noch ein dritter angeordnet wird einfacher erschein´s mir wenn man erstmal versucht den dritten kern zwischen die beiden anderen zu setzen, also alle drei in einer linie... fals das gelingt kann man u.U. endlos lange kern-linien anordnen...


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.37, eingetragen 2016-02-11

Du hast recht, die kann man beide weglassen. Dann ist es doch nur einer mit 2 Mittel-Steinen und 9 Umschließenden. Der fehlte aber noch. http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L2-9.png Wie wäre es, wenn wir eine Kurznotation für einen "minimalen nicht weiter reduzierbaren zwingend 4-färbbaren L-Stein-Graphen mit x Mittel-L-Steinen und y umschließenden L-Steinen" einführen? Vielleicht: Lx-y Jetzt kennen wir schon L1-5, L1-7, L1-9 und L2-7, L2-9, L2-11, L2-13. Alle erfüllen die Regel aus #34.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3424
  Beitrag No.38, eingetragen 2016-02-11

\quoteon(2016-02-11 13:22 - Slash in Beitrag No. 37) Wie wäre es, wenn wir eine Kurznotation für einen "minimalen nicht weiter reduzierbaren zwingend 4-färbbaren L-Stein-Graphen mit x Mittel-L-Steinen und y umschließenden L-Steinen" einführen? Vielleicht: Lx-y Alle erfüllen die Regel aus #34. \quoteoff Oder: Lx-y mit x=gesamt steinanzahl; y=kerne det war meine letzte notation... die regeln aus #34 sind noch nicht perfekt, jedenfals für 3 kerne: die haben hier ne ungerade anzahl verbindungen zum ring (deine haben das doch auch???), wir könnten diese regel veralgemeinern mit: "die kürzeste kette um einen kern muss eine ungerade anzahl steine umfassen" das passt bisher, meines wissens, für alle varianten mit 1;2;3 kernen ist diese lineare L12-3 anordnung ok für drei kerne ? fals ja, kann man sie jeweils in zweierschritten erweitern bis der platz um die kerne nicht mehr ausreicht L14-3 L16-3 usw wie in dem rechten beispiel skizziert http://www.matheplanet.com/matheplanet/nuke/html/uploads/9/35059_L12-3.png


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8686
Wohnort: Sahlenburg (Cuxhaven)
  Beitrag No.39, eingetragen 2016-02-11

Gut, nehmen wir deine Notation. Die Regel aus #34 galt nur den Graphen mit 2 Mittelknoten. Denn da ist die Kantenanzahl der Mittelknoten immer gerade, nur die Außenzahl ist insgesamt ungerade. Das Wort "Alle" war ungenau von mir und bezog sich nur auf die ungerade Anzahl der äußeren Knoten. Wie auch immer - eine allgemeine Regel werden wir bestimmt noch finden. Dein L12-3 scheint in Ordnung zu sein. Gut gemacht! Das mit den unendlichen Ketten scheint dann auch zu funktionieren. Wahnsinn! Nach Kettenbrief, Kettenmolekül, jetzt der Kettengraph. :-D L22-6 http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L22-6_kette.png L42-12 http://www.matheplanet.de/matheplanet/nuke/html/uploads/9/8038_graph_L42-12.png Dies ist bestimmt einer der buntesten Threads auf dem MP. So viele schöne Bildchen. :-)


   Profil
-->> Fortsetzung auf der nächsten Seite -->>
Seite 1Gehe zur Seite: 1 | 2  

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-2022 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]