Week 2
Vlakke grafen: van Euler tot Kuratowski
Inhoud
Wat is een vlakke graaf? ...................................................................................................... 1
Definitie F1 .............................................................................................................................. 1
Facetten en facetgraad ...................................................................................................... 2
Definitie F2 ............................................................................................................................ 2
De facetgradensom............................................................................................................... 2
De formule van Euler en het bewijs ................................................................................. 2
K₃,₃ en K₅ zijn niet vlak........................................................................................................... 3
Hoge valenties passen niet in het vlak ........................................................................... 3
Onderverdelingen en uitbreidingen .................................................................................. 3
Stelling van Kuratowski en vlakheidsonderzoek .......................................................... 4
Key Terms ................................................................................................................................. 4
Een vlakke graaf kun je je voorstellen • Voorbeeld K₄:
als een netwerk dat je op een plat vel
papier kunt leggen zonder dat de • Met één diagonal kun je K₄ plat
verbindingslijnen elkaar kruisen. De tekenen → vlakke tekening.
vraag “wanneer lukt dat?” leidt tot • Door een andere diagonal te
Euler’s formule en Kuratowski’s stelling kiezen ontstaat een kruising →
– de twee hoekstenen van planair- niet-vlakke tekening.
grafentheorie.
Wat is een vlakke
graaf?
Definitie F1
Een graaf heet vlak als hij zonder
doorsnijdingen kan worden
getekend; zo’n tekening heet een
• De Petersen-graf P blijft een open
vlakke tekening van de graaf.
vraag: kan er een vlakke tekening van
• Een graaf en zijn tekening zijn bestaan? (Later wordt aangetoond
verschillende objecten: dezelfde dat hij niet vlak is.)
graaf kan zowel een vlakke als een
niet-vlakke tekening hebben.
Vlakke grafen: van Euler tot Kuratowski
Vlakke grafen: van Euler tot Kuratowski
Inhoud
Wat is een vlakke graaf? ...................................................................................................... 1
Definitie F1 .............................................................................................................................. 1
Facetten en facetgraad ...................................................................................................... 2
Definitie F2 ............................................................................................................................ 2
De facetgradensom............................................................................................................... 2
De formule van Euler en het bewijs ................................................................................. 2
K₃,₃ en K₅ zijn niet vlak........................................................................................................... 3
Hoge valenties passen niet in het vlak ........................................................................... 3
Onderverdelingen en uitbreidingen .................................................................................. 3
Stelling van Kuratowski en vlakheidsonderzoek .......................................................... 4
Key Terms ................................................................................................................................. 4
Een vlakke graaf kun je je voorstellen • Voorbeeld K₄:
als een netwerk dat je op een plat vel
papier kunt leggen zonder dat de • Met één diagonal kun je K₄ plat
verbindingslijnen elkaar kruisen. De tekenen → vlakke tekening.
vraag “wanneer lukt dat?” leidt tot • Door een andere diagonal te
Euler’s formule en Kuratowski’s stelling kiezen ontstaat een kruising →
– de twee hoekstenen van planair- niet-vlakke tekening.
grafentheorie.
Wat is een vlakke
graaf?
Definitie F1
Een graaf heet vlak als hij zonder
doorsnijdingen kan worden
getekend; zo’n tekening heet een
• De Petersen-graf P blijft een open
vlakke tekening van de graaf.
vraag: kan er een vlakke tekening van
• Een graaf en zijn tekening zijn bestaan? (Later wordt aangetoond
verschillende objecten: dezelfde dat hij niet vlak is.)
graaf kan zowel een vlakke als een
niet-vlakke tekening hebben.
Vlakke grafen: van Euler tot Kuratowski
