PuzzelsHeb het één en het ander gelezen over de hoek / ribben / vlakken stelling van Euler bij veelvlakken in 2D, 3D en meer dimensies.
In mijn tussendoor zoektocht naar een wiskundig bewijs (zonder computer) van de 4 kleuren stelling / vermoeden stelde ik het volgende vast.
In een 2 D netwerk van rechte (of gebogen) lijnen / zijden / ribben, met hoekpunten en ingesloten vlakken geldt steeds
Aantal Hoekpunten + aantal Zijden + aantal Vlakken = 1 als met het omrandende vlak niet meetelt, of =2 als men het omrandende vlak wel meetelt.
Ik vermoed dat dat al lang bewezen is, maar kan het voorlopig niet terugvinden.
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
ads
Steun Sciencetalk
Brepols bureau agenda 2026 - LIMA - Bureau agenda - 1 week op 2 pagina's - Weekoverzicht - Zwart - 17.1 x 22 cm
Re: Is deze stelling al bewezen (Euleriaans)
Denken jullie maar niet aub dat ik vermoed / pretendeer iets nieuws vastgesteld te hebben.
Ik vraag mij enkel af waar ik het bewijs kan vinden ...... omdat ik vermoed dat het correct is.
Ik noem het Euleriaans omdat Euler veel dergelijke identiteiten (bewees?)........; maar ik vond niets terecht over een willekeurig vlak netwerk.
Wie kent er een link ?
Ik vraag mij enkel af waar ik het bewijs kan vinden ...... omdat ik vermoed dat het correct is.
Ik noem het Euleriaans omdat Euler veel dergelijke identiteiten (bewees?)........; maar ik vond niets terecht over een willekeurig vlak netwerk.
Wie kent er een link ?
Re: Is deze stelling al bewezen (Euleriaans)
Wikkel uw tekening om een bol, het buitengebied vormt daarna 1 geheel (een gebold vlak) en het totaal wordt een (gebold) veelvlak
met Eulerkarakteristiek χ = H - R + V = 2
met Eulerkarakteristiek χ = H - R + V = 2
Re: Is deze stelling al bewezen (Euleriaans)
@RedCat,
Dank U,
Maar men bewees (bij mijn weten) de stelling voor regelmatige en onregelmatige veelvlakken.
Mag ik dan volgens uw reactie aannemen / veronderstellen dat mijn "willekeurige" schets daaraan voldoet, er van uitgaande dat alle lijnen ook mogen gebogen zijn ?
Kent U een bewijs voor een 2D netwerk ?
Dank U,
Maar men bewees (bij mijn weten) de stelling voor regelmatige en onregelmatige veelvlakken.
Mag ik dan volgens uw reactie aannemen / veronderstellen dat mijn "willekeurige" schets daaraan voldoet, er van uitgaande dat alle lijnen ook mogen gebogen zijn ?
Kent U een bewijs voor een 2D netwerk ?
Re: Is deze stelling al bewezen (Euleriaans)
Voor een vlakke graaf:
(1) Trianguleer alle veelhoeken in de graaf: elke lijn die we toevoegen splitst daarbij het betreffende vlak in 2 vlakken: zo komen er steeds 1 ribbe en 1 vlak bij,
χ = H - R + V verandert daardoor niet
(2) Herhaal het volgende totdat er 1 driehoek overblijft:
Kies een driehoek grenzend aan het buitengebied:
(2a) heeft die driehoek 1 ribbe die grenst aan het buitengebied: verwijder dan die ribbe: zo verdwijnt er 1 ribbe en 1 vlak:
χ = H - R + V verandert daardoor niet
(2b) heeft die driehoek 2 ribben grenzend aan het buitengebied: verwijder dan die 2 zijden en het hoekpunt dat die 2 zijden verbindt: zo verdwijnen er 2 ribben, 1 hoekpunt en 1 vlak:
χ = H - R + V verandert daardoor niet
(3) Tenslotte blijft er een driehoek over met 3 hoeken, 3 ribben, en 1 vlak (het buitengebied rekenen we doorgaans niet mee).
Hierdoor is χ = 3 - 3 + 1 = 1.
En omdat we de Eulerkarakteristiek in het hele proces nergens veranderd hebben, is deze karakteristiek ook 1 voor de oorspronkelijke graaf.
In een plaatje:
Stap 1:
In uw graaf (A) splitsen we de blauwe vijfhoek (B) door toevoeging van de rode lijn in een gele driehoek en een groene vierhoek (C).
Dit proces herhalen we totdat de graaf volledig getrianguleerd is (D).
Stap 2: kies een driehoek:
Kies bijvoorbeeld de groene buitendriehoek (E) met 1 zijde (donkergroen) gemeenschappelijk met het buitengebied: deze zijde verwijderen we waardoor het groene vlak verdwijnt/opgaat in het buitengebied (F)
Herhaling stap 2: kies een driehoek:
Kies bijvoorbeeld de blauwe buitendriehoek (G) met 2 zijden (donkerblauw) gemeenschappelijk met het buitengebied: deze 2 zijden en hun verbindende hoekpunt (punt 4 in uw oorspronkelijke tekening) verwijderen we waardoor het blauwe vlak verdwijnt in het buitengebied (H)
Ga zo door totdat er één driehoek overblijft.
PS: het gaat om het aantal lijnen, het maakt dus niet uit of dat bv. rechte, gebogen, golvende, dikke of dunne lijnen zijn.
(1) Trianguleer alle veelhoeken in de graaf: elke lijn die we toevoegen splitst daarbij het betreffende vlak in 2 vlakken: zo komen er steeds 1 ribbe en 1 vlak bij,
χ = H - R + V verandert daardoor niet
(2) Herhaal het volgende totdat er 1 driehoek overblijft:
Kies een driehoek grenzend aan het buitengebied:
(2a) heeft die driehoek 1 ribbe die grenst aan het buitengebied: verwijder dan die ribbe: zo verdwijnt er 1 ribbe en 1 vlak:
χ = H - R + V verandert daardoor niet
(2b) heeft die driehoek 2 ribben grenzend aan het buitengebied: verwijder dan die 2 zijden en het hoekpunt dat die 2 zijden verbindt: zo verdwijnen er 2 ribben, 1 hoekpunt en 1 vlak:
χ = H - R + V verandert daardoor niet
(3) Tenslotte blijft er een driehoek over met 3 hoeken, 3 ribben, en 1 vlak (het buitengebied rekenen we doorgaans niet mee).
Hierdoor is χ = 3 - 3 + 1 = 1.
En omdat we de Eulerkarakteristiek in het hele proces nergens veranderd hebben, is deze karakteristiek ook 1 voor de oorspronkelijke graaf.
In een plaatje:
In uw graaf (A) splitsen we de blauwe vijfhoek (B) door toevoeging van de rode lijn in een gele driehoek en een groene vierhoek (C).
Dit proces herhalen we totdat de graaf volledig getrianguleerd is (D).
Stap 2: kies een driehoek:
Kies bijvoorbeeld de groene buitendriehoek (E) met 1 zijde (donkergroen) gemeenschappelijk met het buitengebied: deze zijde verwijderen we waardoor het groene vlak verdwijnt/opgaat in het buitengebied (F)
Herhaling stap 2: kies een driehoek:
Kies bijvoorbeeld de blauwe buitendriehoek (G) met 2 zijden (donkerblauw) gemeenschappelijk met het buitengebied: deze 2 zijden en hun verbindende hoekpunt (punt 4 in uw oorspronkelijke tekening) verwijderen we waardoor het blauwe vlak verdwijnt in het buitengebied (H)
Ga zo door totdat er één driehoek overblijft.
PS: het gaat om het aantal lijnen, het maakt dus niet uit of dat bv. rechte, gebogen, golvende, dikke of dunne lijnen zijn.
Re: Is deze stelling al bewezen (Euleriaans)
@RedCat,
Vreselijk bedankt hoor !
Moet er mijzelf nog eens door - worstelen .... maar vooral het reductie - systeem aan om tot "1" te komen lijkt mij briljant.
Wordt het in de wiskundige literatuur ook zo behandelt ? ....... of is het een een methode "RedCat" ?
Als U zo bedreven bent ... kan U dan niet / of wel aantonen dat er max 4 kleuren nodig zijn om alle vlakken in te kleuren, zonder dat twee aangrenzende vlakken dezelfde kleur krijgen ?
Uiterst benieuwd .. en U begrijpt zeker waarom !
(In het 4 kleuren probleem gebruikt men grafen als verbindingslijnen tussen een punt in de vlakken (als vervanging van de oorspronkelijke tekening) ...............maar niet om tot een uiteindelijk bewijs te komen)!
Vreselijk bedankt hoor !
Moet er mijzelf nog eens door - worstelen .... maar vooral het reductie - systeem aan om tot "1" te komen lijkt mij briljant.
Wordt het in de wiskundige literatuur ook zo behandelt ? ....... of is het een een methode "RedCat" ?
Als U zo bedreven bent ... kan U dan niet / of wel aantonen dat er max 4 kleuren nodig zijn om alle vlakken in te kleuren, zonder dat twee aangrenzende vlakken dezelfde kleur krijgen ?
Uiterst benieuwd .. en U begrijpt zeker waarom !
(In het 4 kleuren probleem gebruikt men grafen als verbindingslijnen tussen een punt in de vlakken (als vervanging van de oorspronkelijke tekening) ...............maar niet om tot een uiteindelijk bewijs te komen)!
Re: Is deze stelling al bewezen (Euleriaans)
@RedCat,
Ik bedoel natuurlijk "heel erg" in plaats van "vreselijk"
Ik bedoel natuurlijk "heel erg" in plaats van "vreselijk"
Re: Is deze stelling al bewezen (Euleriaans)
Ja: een dergelijke simpele maar zeer effectieve oplossingsmethode is ooit (= vorige eeuw) in mijn studie behandeld bij grafentheorie.
Maar voor deze stelling zijn er nog veel meer bewijzen bekend, zie bijvoorbeeld stelling 2.7 onderaan pagina 4 van
https://www.math.ru.nl/~bosma/Students/ ... ersBSc.pdf
Hier bouwen ze het bewijs omgekeerd op: vanuit een graaf bestaande uit 1 ribbe (= edge (E)) met 2 punten(= knopen = vertices (V)) aan weerszijde, waaraan steeds een ribbe wordt toegevoegd (al dan niet met een punt).
Noot: hier tellen ze het buitengebied WEL mee als vlak (= facet (F))
Dat is een probleem van een veel hogere orde.kan U dan niet / of wel aantonen dat er max 4 kleuren nodig zijn om alle vlakken in te kleuren, zonder dat twee aangrenzende vlakken dezelfde kleur krijgen ?
Naar mijn weten is hier nog geen ander bewijs voor gevonden dan het (voor sommigen discutabele) computer-bewijs
Dat vermoedde ik al.
ads
Re: Is deze stelling al bewezen (Euleriaans)
@RedCat,
En toch begrijp ik (nog) niet waarom men voor het 4 kleuren probleem in eerste instantie (om te bewijzen dat 5 kleuren voldoende zijn ) over gaat naar een grafenpatroon van punten binnen de vlakken.
Het probleem vertaald zich daardoor dat twee punten op een graaf ..... niet dezelfde kleur mogen hebben.
Maar ik besef goed dan ik bezig ben de transitie te maken naar het 4 kleuren probleem,(mag ik.niet doen !)
ik maakte daar vroeger een topic voor .... helaas slechts een aanzet ....een onvoltooide symfonie.
Maar toch denk ik dat U in staat bent om via jou / het principe van afbouw of opbouw van complexiteit het 4 kleuren probleem op te lossen.. stelt U voor !
Wel met de insteek dat men niet probeert om met zo weinig mogelijk kleuren (van de vier) een oplossing te hebben ....... maar wel met zoveel mogelijk kleuren (van de vier).
In alle papers gaat men uit van zo weinig mogelijk ...... neen, ga uit van zoveel mogelijk.
En toch begrijp ik (nog) niet waarom men voor het 4 kleuren probleem in eerste instantie (om te bewijzen dat 5 kleuren voldoende zijn ) over gaat naar een grafenpatroon van punten binnen de vlakken.
Het probleem vertaald zich daardoor dat twee punten op een graaf ..... niet dezelfde kleur mogen hebben.
Maar ik besef goed dan ik bezig ben de transitie te maken naar het 4 kleuren probleem,(mag ik.niet doen !)
ik maakte daar vroeger een topic voor .... helaas slechts een aanzet ....een onvoltooide symfonie.
Maar toch denk ik dat U in staat bent om via jou / het principe van afbouw of opbouw van complexiteit het 4 kleuren probleem op te lossen.. stelt U voor !
Wel met de insteek dat men niet probeert om met zo weinig mogelijk kleuren (van de vier) een oplossing te hebben ....... maar wel met zoveel mogelijk kleuren (van de vier).
In alle papers gaat men uit van zo weinig mogelijk ...... neen, ga uit van zoveel mogelijk.
