Die Mathe-Redaktion - 24.04.2019 20:09 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 440 Gäste und 26 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Vier-Farben-Problem, Revision
Thema eröffnet 2018-03-22 18:39 von
schnodl
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich Vier-Farben-Problem, Revision
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7371
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2018-12-08


2018-12-07 20:08 - schnodl in Beitrag No. 39 schreibt:
Moin allerseits: der vorige Beitrag wurde kurz nach seiner  Veröffentlichung im MP (heute 18:12) (wie schon der vom 10.11.18) abgehakt und das ganz sicher nicht von mir - er ist weder beantwortet noch erledigt ...
Wenn jemand zu diesem eigenartigen, um nicht zu sagen verstörenden  Automatismus (?) einen weiterführenden Tipp hat, ich wäre dankbar.
Mit freundlichen Grüßen
schnodl

Ich denke, dass du das selbst warst - ausversehen - denn das Kästchen ist direkt über dem Submit Button. smile



  Profil  Quote  Link auf diesen Beitrag Link
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1076
Aus: Hoyerswerda
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2018-12-09



Hi schnodl,
2018-12-07 18:12 - schnodl in Beitrag No. 38 schreibt:
2.1. Der Satz beginnt mit der Aussage: „Wenn ich einen Knoten durch einen FPW separiert habe, gibt es eine gültige Färbung, die die beiden nicht-FPW-Farben innerhalb des FPW vertauscht“. (Für gültig steht im Folgenden gleich bedeutend zulässig).
2.1.1. Dem kann ich nicht zu stimmen, weil ein Knoten nicht durch einen konstruierten FPW  separiert wird, sondern durch einen FPW, auf dessen Existenz oder Nicht-Existenz allein nach den her geleiteten Färbe- bzw. Umfärbe-Regeln – speziell der sog. FPW-Logik – geschlossen wird (s. a. Text und meine Beiträge). Deshalb: „Wenn ein separierender FPW existiert …“.

Mit "Wenn ich einen Knoten durch einen FPW separiert habe" habe ich eher gemeint "Wenn ich die Existenz des FPW bewiesen oder angenommen habe", wir sind uns da also einig :)


[...] eine andere, zulässige Farbstruktur entsteht, für deren Umfärbung bzw. Färbung die im Text entwickelten Regeln also erneut (sozusagen ab ovo) anzuwenden sind.

Davon hast du aber bisher nichts geschrieben. Z.B. Beitrag #34 hat bisher den Eindruck erwegt, dass du die Schritte nach und nach durchgehst, und spätestens nach 2.5.2. eine gültige Färbung hast.

Wenn ich dich richtig verstehe, würdest du jetzt 2.5.2. durch folgenden Zusatz ergänzen:
 
"2.5.2. Andernfalls muss vadj* in einem zweiten FPW enthalten sein, so dass beide gleich gefärbten vadj jeweils mit der komplementären F des nicht adjazenten vadj umfärbbar sind." + (von mir) "Falls diese zwei Umfärbungen nicht kompatibel sind, führe nur eine Umfärbung durch, und geh mit der neuen gültigen Färbung zurück zu 2.3."

Mit diesem Zusatz stellt sich aber eine neue Frage: Warum soll es im neuen Anlauf klappen? Vielleicht musst du noch 10 mal zurück zu 2.3 springen, und bist dann wieder bei deiner Anfangsfärbung angekommen? Woher weißt du, dass dieser Prozess endet?


Fazit: Es ist für die Färbbarkeit eines DG ohne Belang, ob ein FPW oder eine andere Farbstruktur durch irgendeine anderweitige Umfärbung bzw. Färbung „zerstört“ bzw. erzeugt wird oder nicht, solange dabei die Zulässigkeit der Färbung des DG erhalten bleibt.
Nur immer wieder zulässige Färbungen zu erzeugen reicht nicht, man muss auch zeigen, dass man irgendwann am Ziel ankommt.

Gruß,
Philipp



  Profil  Quote  Link auf diesen Beitrag Link
schnodl
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.03.2010
Mitteilungen: 49
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2018-12-16


Moin Philipp,
vielen Dank für deinen Beitrag – wieder eine nützliche Herausforderung.
 
Wenn ich dich richtig verstanden habe, ist dein wesentlicher Einwand jetzt, meine Argumentation scheitere daran, dass sie die Existenz von Umfärbe-Endlosschleifen erlaubt. Darauf kann ich nur mit einer entsprechend fokussierten Wiederholung meiner bisherigen Ausführungen antworten.  (Wenn du dies auch nicht explizit bestätigt hast, gehe ich im Folgenden davon aus, dass sich dein voriges Gegenargument, ein FPW könne durch eine anderweitige Umfärbung so ‚zerstört‘ werden, dass eine zulässige Färbung von vKE nicht möglich sei, mit meinem letzten Beitrag erledigt hat.)

1. Wir stimmen darin überein, dass die problematische Konstellation die ist, in der keiner der mit einer der drei einfach vorkommenden Farben (hier F1, F3 und F4) gefärbten vadj durch FPW separiert wird und damit reduzierend umfärbbar ist und damit zwei FPW, hier FPW14 und FPW34, existieren, die die mit F2 gefärbten vadj separieren.
1.1. Angemerkt sei, dass immer vom ungünstigsten Fall auszugehen ist, in dem jeder FPW nur einfach vorhanden ist (wäre ja auch eine Stapelung denkbar).
2. Zur Illustration des Folgenden ->

ÄNDERUNG:
Der folgende Teil meines Beitrag vom 15.12.2018 bezog sich auf die Abbildungen a-e; darin habe ich einige Fehler entdeckt - ebenso wie im Text (5.2.'komplementär' ist falsch). Der Eindeutigkeit halber habe ich den darauf bezogenen Teil des Beitrag gelöscht und werde ihn demnächst mit korrigierten und erweiterten Abbildungen und einer ausführlicheren Begründung meiner Antwort ersetzen.
Bis dann und mit freundlichen Grüßen
schnodl




  Profil  Quote  Link auf diesen Beitrag Link
schnodl
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.03.2010
Mitteilungen: 49
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, vom Themenstarter, eingetragen 2019-03-25


Moin Philipp, hier also die angekündigte Erweiterung meines letzten Beitrags vom 16.12.2018 mit korrigierten Abbildungen (Änderung vom 15.1.2019).
Dein Einwand ist, dass die Unterbrechung eines bestehenden FPW durch Umfärbung über einen querenden FPW zu einer Umfärbe-Endlosschleife führt und damit eine zulässige Färbung von vKE unmöglich wird („ … man muss auch zeigen, dass man irgendwann am Ziel ankommt.“).
Ich behaupte, dass in einem 4-gefärbten DG auch bei querenden und damit einander unterbrechenden Start-FPW ein vKE vom Grad d=5 mit maximal zwei Umfärbe-Manövern (Umfärbung der beiden gleich gefärbten vadj vadjFd) zulässig färbbar ist.

1. Ergänzende Definitionen
1.1. Ein vadj ist zulässig umfärbbar, wenn er von einem FPW separiert wird, so dass  zwei adjazente vadj nicht beide zugleich umfärbbar und nicht umfärbbar sind.
1.1.1. Der Cvadj aus n=5 vadj heißt im Folgenden Cvadj5.
1.1.2. Von einem Cvadj5 gehen wenigstens zwei unterschiedlich gefärbte FPW aus, die einen gemeinsamen vadj enthalten.
1.1.2.1. FPW, die einen gemeinsamen vadj enthalten, heißen im Folgenden verwandte FPW.
1.1.3. Kreuzen sich zwei FPW über einen gemeinsamen Knoten, dann queren sie sich, so dass sich komplementär gefärbte FPW nicht queren.
1.1.4. Zwei mit einer doppelt vorkommenden Fd gefärbte, nicht adjazente vadj werden durch Anfügen von „°“ bzw. „°°“ an Fd gekennzeichnet.
1.1.5. Koexistieren von Cvadj5 ausgehende nicht verwandte FPW, queren diese sich.

1.2. Zur Problemstellung
1.2.1. Die beiden von Cvadj5 ausgehenden, verwandten FPW queren sich wechselseitig und umfassen damit einer oder beide den Cvadj vollständig, indem sie zusammen mit dem jeweils flankierten vadj einen Kreis bilden (s. Abbildungen).
1.2.2.Ein Cvadj umfassender FPW wird durch ein angehängtes u als FPWu gekennzeichnet.
1.2.3. Jeder der beiden querenden FPW passiert den separierenden Bereich SB des jeweils anderen FPW.
1.2.4. Wird der von FPW* separierte vadj umgefärbt, sind im SB von FPW* alle dem separierten vadj über einen dem separierenden FPW komplementär gefärbten Weg verbundene Knoten (im Folgenden ihre Farb-Paar-Kette FPK) so um zu färben, dass DG zulässig gefärbt ist.
1.2.5. Die Umfärbung des separierten vadj und seiner FPK heißt im Folgenden UF-Manöver.
1.2.6. Werden mit dem UF-Manöver ein oder mehrere Knoten des den SB passierenden FPW umgefärbt, wird dieser unterbrochen und damit eliminiert.

1.3. Die beiden von Cvadj5 ausgehenden, jeweils einen vadjFd separierenden Start-FPW FPWa (hier FPW14) und FPWb (hier FPW34) queren sich und sind verwandt, so dass mit der Eliminierung eines der beiden ein neuer FPW  erzeugt wird, der dem eliminierenden FPW verwandt ist.
1.4. Der durch das UF-Manöver neu entstandene FPW heißt FPWN.
1.5. FPWN sind dem eliminierenden FPW entweder über dessen Start-vadj oder über dessen End-vadj verwandt, so dass zwei – einander komplementäre – FPWN möglich sind.
1.5.1. Einer der beiden FPWN ist farbgleich mit dem eliminierten FPW, ohne dessen Verlauf zu nehmen. Dieser FPWN wird durch angehängtes x als FPWNx gekennzeichnet.
1.5.2. Der FPWNx komplementäre FPWN enthält neben einem vadj des eliminierenden FPW einen vadjFd und wird als FPWNy gekennzeichnet.
1.5.3. Die beiden möglichen FPWNy sind dem eliminierenden FPW verwandt und werden durch angehängtes * bzw. ** gekennzeichnet.
1.6. Voraussetzung einer zulässigen Färbung von vKE mit zwei UF-Manövern ist die reduzierende Umfärbung beider vadjFd.
1.6.1. Für eine zulässige Färbung von vKE ist folglich mit dem initialen UF-Manöver der eliminierte Start-FPW, also FPWNx wieder her zustellen.
1.6.1.1. Der wieder hergestellte FPWNx kann FPWu sein aber nicht den SB des eliminierenden Start-FPW queren.
1.6.2. vKE ist nicht zulässig mit zwei UF-Manövern färbbar, wenn das initiale UF-Manöver FPWNy erzeugt.
1.6.2.1. FPWNy kann FPWu sein und den SB des Start-FPW queren.

2. These: In einem 4-gefärbten DG geht von einem Cvadj5 jeweils von zwei möglichen FPWNy nur einer aus, so dass die beiden möglichen FPWNy nicht koexistieren.
2.1. Beweis
2.1.2. Ausgehend vom Cvadj5 enthalten FPWN12° und FPWN32°° keinen gemeinsamen vadj und sind deshalb nicht verwandt, so dass FPWN12° und FPWN32° – ohne zu queren – nicht koexistieren (s. 1.1.5).
2.1.3. Wird in einem DG4F ein FPWNy* mit FPWa und UF-Manöver erzeugt, kann in diesem DG4F nicht auch FPWNy** existieren.  
2.1.4. Die Existenz von FPWNy* bzw. FPWNy** erfordert folglich jeweils eine eigene DG-Struktur, so dass in DG4F und Cvadj5 die Erzeugung des jeweils anderen FPWNy ausgeschlossen ist.
2.1.6. Die beiden unterschiedlichen DG-Strukturen heißen DGSTR-A und DGSTR-B.

3. Erläuterungen (s.a. Abbildung 4 und 5)
3.1. Erste Konstellation: Einer der beiden jeweils einen vadjFd separierenden Start-FPW ist FPWu, so dass sich beide Start-FPW queren und den SB des jeweils anderen passieren. Im ungünstigen Fall eliminiert die Umfärbung des separierten, mit Fd gefärbten vadj samt seiner FPK den jeweils anderen Start-FPW.
3.1.1. Im Folgenden flankieren FPW14 und FPW34 jeweils einen Fd2 (s.a. Abb.), wobei wenigstens einer von beiden FPW FPWu ist und den SB des jeweils anderen passiert (s.a. Abbildungen).
3.1.2. Die DG-Struktur, die mit dem ersten UF-Manöver FPW12 entstehen lässt, heißt DGSTR-A, und die DG-Struktur, die mit dem ersten UF-Manöver FPWF23 entstehen lässt, heißt DGSTR-B.
3.1.2.1. Es hängt ebenfalls von der jeweiligen Struktur des DG ab, ob mit dem ersten UF-Manöver FPWNx oder FPWNy entsteht (s. 3.1.3.2 und 3.1.4.2).  
3.1.3. DG-Struktur ist DGSTR-A (s. Abb.3)
3.1.3.1.  Erster Fall. Start-FPW ist FPW14, so dass vadjFd2 mit F3 umgefärbt und damit der querende Teil von FPW34 durch FPK23 unterbrochen wird.
3.1.3.2.  Die DG-Struktur sei dergestalt, dass mit dem ersten UF-Manöver nicht FPW34x erzeugbar ist. Folglich entsteht FPWN12, da FPWN23 wegen DGSTR-A nicht existieren kann. FPWN12  separiert den außerhalb des SB von FPW14 gelegenen vadjF3*, so dass dieser nicht reduzierend mit F4 umfärbbar ist.
3.1.3.3. Schluss: vKE ist in DGSTR-A nach Start-FPW14 nicht mit zwei UF-Manövern  zulässig färbbar.
3.1.3.4. Zweiter Fall: Start-FPW ist FPW34, so das vadjFd2 mit F1 umgefärbt und damit FPW14 durch FPK12 unterbrochen wird.
3.1.3.5. Bei gleicher DG-Struktur (s.3.1.3.2) ist FPWN12, da FPW34 komplementär, nicht erzeugbar, und FPWN23 kann wegen DGSTR-A nicht existieren, so dass FPW14x entsteht. Damit ist vadjF3 mt F2 bzw. vadjF2 mit F3 reduzierend umfärbbar.
3.1.3.6. Schluss: vKE ist in DGSTR-A mit Start-FPW34 nach zwei UF-Manövern mit F2 bzw. F3 zulässig färbbar.
3.1.4. DG-Struktur ist DGSTR-B (Abb. 4)
3.1.4.1. Erster Fall. Start-FPW ist FPW34, so dass vadjFd2 mit F1 umgefärbt und damit der querende Teil von FPW14 durch FPK12 unterbrochen wird.
3.1.4.2. Die DG-Struktur sei dergestalt, dass mit dem ersten UF-Manöver nicht FPW14X erzeugbar ist, so dass FPWN32 entsteht, da FPWN12 wegen DGSTR-B nicht existieren kann. FPWN32 separiert vadjF1, so dass dieser nicht reduzierend mit F4 umfärbbar ist.
3.1.4.3. Schluss: vKE ist in DGSTR-B mit Start-FPW34 nicht mit zwei UF-Manövern  zulässig färbbar.
3.1.4.4. Zweiter Fall: Start-FPW ist FPW14, so das vadjFd2 mit F3 umgefärbt und damit FPW34 durch FPK23 unterbrochen wird.
3.1.4.5. Bei gleicher DG-Struktur (s. 3.1.4.2) ist FPWN23, da FPW14 komplementär, nicht erzeugbar, und FPWN12 kann in DGSTR-B nicht existieren, so dass FPW34x entsteht. Damit ist vadjF1 mit F2 bzw. vadjF2 mit F1 jeweils reduzierend umfärbbar.
3.1.4.6. Schluss: vKE ist in DGSTR-B mit Start-FPW14 nach zwei UF-Manövern mit F1 bzw. F2 zulässig färbbar.
3.2. Zweite Konstellation: Beide FPW sind FPWu, so dass die nach Umfärbung eines vadjFd entstehenden FPK den jeweils anderen FPWu queren und damit nicht eliminieren. Folglich ist vKE in zwei UF-Schritten zulässig färbbar.

4. Fazit: In einem beliebigen 4-gefärbten DG ist jeder zusätzlich eingefügte vKE vom Grad d=5 auch bei einander querenden Start-FPW mit höchstens zwei UF-Manövern zulässig färbbar.





Abb. 3. DG4F aus n=23 Knoten. Die DG-Struktur ist DGSTR-A (s. Text 3.1.3)
3.1. und 3.2.  Start-FPW14: UF-Manöver erzeugt FPWN12y, so dass vKE nicht zulässig färbbar ist.
3.3. und 3.4.  Start-FPW34: UF-Manöver erzeugt FPWN14x, so dass vKE zulässig färbbar ist.
Umgefärbte Knoten sind grau hinterlegt








Abb. 4. DG4F aus n=25 Knoten. Die DG-Struktur ist DGSTR-B (s.a. Text 3.1.4)
4.1. und 4.2.  Start-FPW34: UF-Manöver erzeugt FPWN23y, so dass vKE nicht zulässig färbbar ist.
4.3. und 4.4.  Start-FPW14: UF-Manöver erzeugt FPWN14x, so dass vKE zulässig färbbar ist. Umgefärbte Knoten sind grau hinterlegt


Mit freundlichem Gruß und nochmals ausdrücklichem Dank für dein Interesse und  insbesondere für die Aufdeckung des Problems!
schnodl




  Profil  Quote  Link auf diesen Beitrag Link
schnodl
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.03.2010
Mitteilungen: 49
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, vom Themenstarter, eingetragen 2019-03-26


Moin allerseits,
Beitrag wurde NICHT beantwortet und hat sich NICHT erledigt...
Mit freundlichen Grüßen
schnodl
PS Das war doch nicht etwa "Haken"?



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7371
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, eingetragen 2019-03-26


Hi schnodl,

keine Panik wegen des Hakens. Der hat keinerlei Relevanz für beteiligte Mitglieder eines Threads. Diese sehen ja - wie aber auch alle anderen Mitglieder - ob etwas Neues hinzugekommen ist.

Da sich bisher nur Philipp mit deinem Beweis beschäftigt hat - großes Lob an sein Engagement übrigens - kannst du ihm (zur Sicherheit) auch zusätzlich eine PM schicken.

Gruß, Slash



  Profil  Quote  Link auf diesen Beitrag Link
schnodl hat die Antworten auf ihre/seine Frage gesehen.
schnodl hatte hier bereits selbst das Ok-Häkchen gesetzt.
Seite 2Gehe zur Seite: 1 | 2  
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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]