4 Kleuren probleem

[HansH]

@HansH,

Dan.moet men wel bewijzen dat er "geen andere mogelijkheden" bestaan ........ en dat deed de computer niet in het 4 kleuren probleem.
Het waren de onderzoekers die kwamen tot 1*** mogelijke configuraties , en later 1*** (ken de getallen. niet uit het hoofd), en straks 1???dus een waardeloos bewijs

uiteraard. Hoe ga je bewijzen dat je bij een redenatie niet iets doms over het hoofd hebt gezien?

[wnvl1]

Ik heb aan AI gevraagd om het bewijs even eenvoudig samen te vatten. Onderstaande tekst geeft zonder dat ik het daarom helemaal begrijp wel een goed idee van hoe het bewijs werkt. Ik kan me er zo wel wat bij voorstellen.

--------------

Het vierkleurenprobleem stelt dat elke kaart in het vlak kan ingekleurd worden met hoogstens vier kleuren, zodanig dat aangrenzende gebieden verschillende kleuren hebben. Dit probleem kan zonder verlies van algemeenheid vertaald worden naar de grafentheorie, waarbij gebieden worden voorgesteld als knopen en aangrenzende gebieden als verbindingen tussen knopen.

Eerst vereenvoudigt men het probleem door elke kaart te trianguleren, dat wil zeggen dat men extra verbindingen toevoegt zodat elk gebied begrensd wordt door precies drie zijden. Dit verandert het probleem niet, want als de uitgebreidere graaf met vier kleuren kan worden ingekleurd, dan geldt dat ook voor de oorspronkelijke graaf.

Vervolgens gebruikt men de formule van Euler, namelijk \( v - e + f = 2 \), samen met het feit dat in een getrianguleerde graaf elke zijde tot precies twee driehoeken behoort, zodat \( 2e = 3f \). Hieruit volgt dat
\[
\sum_{i}(6 - i)v_i = 12,
\]
waarbij \( v_i \) het aantal knopen van graad \( i \) voorstelt. Omdat deze som positief is, moet er minstens één knoop bestaan met graad kleiner dan of gelijk aan vijf.

Men redeneert vervolgens via tegenspraak. Stel dat er een graaf bestaat die niet met vier kleuren kan worden ingekleurd, en neem een minimale dergelijke graaf \( G \). In deze graaf kan geen knoop voorkomen met graad kleiner dan of gelijk aan drie, want dan kan men deze knoop verwijderen, de kleinere graaf inkleuren, en de knoop daarna terugplaatsen en inkleuren.

Ook knopen van graad vier kunnen uitgesloten worden met behulp van zogenaamde Kempe-ketens, waarbij men kleuren langs bepaalde paden verwisselt om een geldige inkleuring te bekomen.

Het moeilijke geval is dat van knopen met graad vijf. De oorspronkelijke redenering van Kempe voor dit geval bleek echter fout te zijn. Moderne bewijzen lossen dit op door niet slechts één knoop te beschouwen, maar grotere lokale structuren, zogenaamde configuraties.

Men toont enerzijds dat een eindige verzameling van configuraties onvermijdelijk is, wat betekent dat elke planaire graaf minstens één van deze configuraties bevat. Anderzijds toont men dat elk van deze configuraties reduceerbaar is, wat betekent dat elke geldige inkleuring van de rest van de graaf kan uitgebreid worden tot de configuratie zelf.

Om aan te tonen dat een verzameling configuraties onvermijdelijk is, gebruikt men de zogenaamde discharging-methode. Hierbij kent men aan elke knoop een beginlading toe gelijk aan \( 6 - \deg(v) \), en herverdeelt men deze lading volgens vaste regels. Omdat de totale lading positief blijft, moeten bepaalde configuraties noodzakelijk voorkomen.

Ten slotte wordt met behulp van computerondersteuning nagegaan dat alle configuraties in de onvermijdelijke verzameling effectief reduceerbaar zijn. Hieruit volgt dat een minimale tegenvoorbeeldgraaf niet kan bestaan, en dus dat elke planaire graaf met vier kleuren kan worden ingekleurd.

[Professor Puntje]

@PP,

Een reken machine of een spreadsheet kan de wiskundige helpen .. om tot zijn wiskundig bewijs te komen .......maar het item kan op zichzelf niet gebruikt worden als bewijs ..... denk ik ........ met een zekere overtuiging.
Als men het wel doet is men "niet goed bezig"

Nou - daarbij valt voor jou dan een groot deel van de moderne wiskunde als ondeugdelijk af. De bewijzen die volgens jou dan nog "te redden" zijn zouden dan zo goed als onleesbaar worden omdat je dan om de haverklap expliciet allerlei berekeningen met het handje moet toevoegen om het gebruik van hulpmiddelen als een rekenmachine of spreadsheet maar te kunnen te vermijden. Ik vraag mij af of je de consequenties van je positie wel goed realiseert. De wiskunde zal daar zeker niet leuker of mooier van worden, en van haar praktische bruikbaarheid zou weinig overblijven.

[wnvl1]

As ik het allemaal zo lees, dan verwondert het mij niet echt daat je tot zo een boekhoudkundig bewijs komt. Het is zaak van heel veel configuraties aflopen. Ik snap best dat het zich vertaalt in veel configuraties die afgelopen moeten worden.

[Professor Puntje]

Het kan zijn dat er een diepere logica is die het aflopen van de mogelijke configuraties overbodig maakt, maar een dergelijk bewijs zal dan niet via grafen lopen. Ik vind het wel leuk om daar naar op zoek te gaan, ook al is de kans dat ik dat vind miniem.

[Regor]

@PP,

Neen, die kans is er wel degelijk.
Elkeen die geinfecteerd is met de grafen virus zal er nooit toe komen.
Het was / is een verleidelijke soort mapping om de / een oplossing éénvoudiger te laten lijken......... maar niets van.
Ik sta te popelen om de nieuwe topic te starten.
Deze namiddag in mijn oud VW T3 camperbusje zal ik er mij op voorbereiden.samen met mijn muze.

Maar toch PP.
Als U het bewijs leest in de download file ...... bent U verloren.
Probeer voorlopig met de schets die ik poste in de topic van Euleriaans netwerk.
Kies één kleur ( of beter A, B,C, OF D ) voor het omgevingsvlak van het netwerk ....... ja die moet ook een kleur hebben en wordt niet toegepast in het reguliere bewijs.......een serieus tekort ...... en toch zijn er in het totaal maar 4 kleuren nodig, inclusief het oneindige buitenvlak.
r
Loopt de buitenste and van het netwerk af en pas de regels toe van vlakken en punten (uit mijn opsomming).
Ga dan over naar de buitenste min één laag .... en pas hetzelfde toe.

Later meer in de nieuwe topic.

[Regor]

@wnvl1,

Dan moet je toch ook snappen dat men nog niet bewezen heeft dat er "net zoveel "mogelijke configuraties zijn !
Men is afgedaald in het aantal ..... en straks misschien weer.
Kleuterklas bewijs !