sciencetalk

Ik heb op een website over het vierkleurenprobleem wat rondgeneust omdat ik een presentatie moet houden over grafen. Ik heb het probleem van de zeven bruggen van Koningsbergen en de puzzel Instant Insanity al als voorbeelden gebruikt en omdat ik nog meer materiaal nodig had besloot ik de opstap naar het vierkleurenprobleem te maken, ofwel het bewijs dat elke kaart met 6 en het bewijs dat elke kaart met 5 kleuren gekleurd kan worden.

Ik loop echter vast op de ontkrachting van het bewijs van Kempe wat toch wel belangrijk is aangezien hij wel de vijfkleurenstelling bewezen heeft. Het is dit figuur waar ik op vastloop.



De tekst zegt dat Rood-Geel omgewisseld kan worden en dat Rood-Groen gewisseld kan worden maar niet allebei, omdat er dan twee rode landen naast elkaar komen te liggen. Maar dat is toch ook al het geval als er een van de twee gewisseld wordt? En het is in deze figuur toch ook mogelijk om de twee Rode landen respectievelijk Groen en Geel te kleuren? Kan iemand dit voor me verduidelijken?

De rest van de redenatie en de uitleg, verder zonder complexe wiskunde, is hier te vinden:

http://hhofstede.nl/bewijzen/4kleuren.htm

Onder aan de pagina staat de index. Ik zou het zeer op prijs stellen als iemand me dit uit kan leggen.

Hier kun je het verkeerde deel van het bewijs van Kempe bekijken en een pagina verder wordt de fout toegelicht/uitgewerkt

Op de volgende pagina wordt alleen over het ontladen en de onvermijdelijke sets gesproken. De fout van Kempe wordt verder niet in het artikel besproken, of mis ik iets?

De site kan nuttig zijn als inspiratie, maar er staan toch vrij veel fouten op de site in het algemeen, ook bij andere onderwerpen dan het vierkleurenprobleem. Een kritische blik en eigen uitwerking is dan ook vaak aangewezen, maar als inspiratie kan de site dus wel helpen.

Ik denk (zonder het helemaal uitgespit te hebben) dat hier twee fouten in staan.

1) Er wordt een stap overgelaten. Eerst ontkracht je de eerdere figuur die gegeven werd bij het "bewijs" van Kempe http://hhofstede.nl/bewijzen/4kleuren19.gif door de ketens te laten kruisen (doe je zelf eens?).

2) Daarnaast heb je de andere mogelijkheid met deze figuur die je hier bekijkt. Als de ketens niet kruisen heb je de andere figuur http://hhofstede.nl/bewijzen/4kleuren23.gif en dan kan je (wat het moet zijn denk ik) een van de rode "veilig" groen maken en de andere geel, zodat er geen rode meer zijn. Door het kruisen kan dat niet meer (kan je dit zelf uitleggen?).

Op kleurwisselingen, spiegelingen, rotaties, enz... na denk ik dat je enkel deze beide mogelijkheden hebt om twee ketens te kiezen zodat je na het kiezen (als die niet kruisen) ook kan gaan vervangen. Het enige verschil is of je het kleur dat twee keer voorkomt meeneemt of niet meeneemt.

Als ik dan weer de link van Jaimy11 bekijk lijkt het dat Kempe mss enkel deze tweede mogelijkheid gebruikte (hoewel ik de uitwerking zelf daar toch niet terug vind?) en mss daarom enkel deze mogelijkheid vermeld staat op de site.

Volgens mij heeft "hhofstede" een dergelijke uitleg ergens, misschien in het Engels, gezien, en het foutief overgenomen op zijn site. Of begrijp ik hem niet helemaal correct? Omdat ik al vaker fouten op de site heb zien staan ben ik ook sneller geneigd om te zeggen dat het fout staat op de site. Nu ja, het is duidelijk voor je dat doordat de ketens kunnen kruisen het bewijs faalt?

Ik ben bang dat ik het nog steeds niet snap. Waarom is het een probleem dat de lijnen elkaar kruisen? Het beste wat ik kan bedenken is dat het probleem ook als volgt kan geformuleerd:

Is het mogelijk de knopen in een plenaire graaf zo met vier kleuren te kleuren dat er geen twee knopen van dezelfde kleur met elkaar verbonden zijn?

In een plenaire graaf mogen twee lijnen tussen punten elkaar niet kruisen, dan is het geen plenaire graaf meer. Maar deze lijnen zijn geheel denkbeeldig, in werkelijkheid bestaan ze niet omdat de betreffende punten niet aan elkaar grenzen. Ze mogen hoogstens eerst verbonden worden met het 'onbekende' grijze land dat hier als een grote cirkel weergegeven is maar natuurlijk eigenlijk ook een knoop is. Ik ben bang dat ik er zo niet uit ga komen...

sjasogun1 schreef:Ik ben bang dat ik het nog steeds niet snap. Waarom is het een probleem dat de lijnen elkaar kruisen? Het beste wat ik kan bedenken is dat het probleem ook als volgt kan geformuleerd:

Is het mogelijk de knopen in een plenaire graaf zo met vier kleuren te kleuren dat er geen twee knopen van dezelfde kleur met elkaar verbonden zijn?

In een plenaire graaf mogen twee lijnen tussen punten elkaar niet kruisen, dan is het geen plenaire graaf meer. Maar deze lijnen zijn geheel denkbeeldig, in werkelijkheid bestaan ze niet omdat de betreffende punten niet aan elkaar grenzen. Ze mogen hoogstens eerst verbonden worden met het 'onbekende' grijze land dat hier als een grote cirkel weergegeven is maar natuurlijk eigenlijk ook een knoop is. Ik ben bang dat ik er zo niet uit ga komen...

Deze graaf is sowieso planair...

Vooruit, vergeet je plaatje even en bekijk dit nogmaals:



Hier gaat het goed, dit is 4-kleurbaar.

Een fout in een bewijs vinden is moeilijker dan zelf een bewijs opstellen.

Je moet je in ieder geval realiseren dat het vierkleurenprobleem wel kan worden opgelost, en dus een kaart te kleuren is met 4 kleuren. Hier is geen echt bewijs voor. Dat is er alleen voor 5 kleuren. Het vierkleurenprobleem is meer een experimentje geweest waar geen tegenvoorbeeld is gevonden om het "bewijs" te ontkrachten.

Ik heb nog even gezocht en gevonden:

Hier staat wat er niet klopt aan het bewijs van Kempe.

Zoek in het document even op "flaw", de eerste hit is de fout.

Ik ben bang dat ik het nog steeds niet snap. Waarom is het een probleem dat de lijnen elkaar kruisen?

Edit: Post verwijderd: zie zelf nu ook niet waarom het niet zou kunnen als ze kruisen. Zal er later eens naar kijken, want heb nu niet veel tijd.

De vierkleurenstelling kan niet worden bewezen met het bewijs van Kempe, overigens is de vijfkleurenstelling niet bewezen door Kempe, maar met een groot deel van zijn bewijs.

In je eerder gegeven plaatje zie ik niet zo goed hoe of wat, maar ik zie wel dat blauw en blauw met elkaar verbonden zijn....

Ok, nu beter.

1) Begin met in het plaatje de linkse rode groen te maken. Mogelijks breekt de rood-groene keten die hieraan verbonden is door de blauw-groene keten naar buiten. Veronderstel dat dit het geval is.

2) Probeer nu de rechtse rode geel te maken. Ook de rood-gele keten hiermee verbonden kan naar buiten breken door de blauw-gele keten. Omdat in (1) de blauw-groene keten al verbroken is, is de gele knoop niet meer afgeschermd en kan die rood worden. Dit levert dus een probleem op. Elke rode knoop kan apart van kleur veranderd worden (resp groen en geel), maar niet samen (zonder de andere knopen op de cirkel te beïnvloeden).

Je moet je in ieder geval realiseren dat het vierkleurenprobleem wel kan worden opgelost, en dus een kaart te kleuren is met 4 kleuren. Hier is geen echt bewijs voor.

Hier is Wikipedia het niet met je eens en geeft meerdere links naar meerdere bewijzen.

Hier is Wikipedia het niet met je eens en geeft meerdere links naar meerdere bewijzen.

Dat klopt en dat gaf ik ook aan, een computerexperiment, vind ik persoonlijk als wiskundige geen bewijs.....

Voor genoeg mensen is dit wel zo, maarja, wiskundigen hé

Dat klopt en dat gaf ik ook aan

Nee, je had het over "een experimentje waar geen tegenvoorbeeld is gevonden om het "bewijs" te ontkrachten", en dat is het helemaal niet. Er staat ook nog meer in het Wikipedia-artikel.

Nee, je had het over "een experimentje waar geen tegenvoorbeeld is gevonden om het "bewijs" te ontkrachten", en dat is het helemaal niet. Er staat ook nog meer in het Wikipedia-artikel.

De bewijzen zonder computer zijn foutief of onvolledig.

De "correcte" bewijzen zijn gebaseerd op Appel&Haken....

En dat is voor mij in ieder geval niet goed genoeg..

De bewijzen zonder computer zijn foutief of onvolledig.

Ok, ik lees "In 2001 the same authors announced an alternative proof, by proving the snark theorem (Thomas; Pegg et al. 2002)."

Ik ben van plan om het eventueel eens te bekijken, als ik het terugvind op het internet. Kan je zeggen wat er foutief of onvolledig aan is, dan kan dat al een grote hulp zijn vooraf en veel moeite besparen?

kee schreef:Ok, ik lees "In 2001 the same authors announced an alternative proof, by proving the snark theorem (Thomas; Pegg et al. 2002)."

Ik ben van plan om het eventueel eens te bekijken, als ik het terugvind op het internet. Kan je zeggen wat er foutief of onvolledig aan is, dan kan dat al een grote hulp zijn vooraf en veel moeite besparen?

Snark theorem is ook computer gerelateerd.

Kleine figuren als de petersen graaf en de grotere zoals de descartes snark zijn nog wel handmatig te doen.

Grotere snarks werden geverifieerd met computers.

Lees ook dit stukje eens.

Het gaat om het kopje "Bewijs?" onderaan de pagina...