De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath}

Equivalentie aantonen van definities

Beste,

Een outerplanar graaf heeft twee definities. 1) Een graaf G is outerplanar als het een planaire tekening heeft waarbij all vertices op de ongebonden (externe) regio ligt. 2) Een graaf G is outerplanar als je een vertex kan tekenen in de ongebonden regio, en die met lijnen verbindt met alle vertices in G, zodanig dat deze nieuwe graaf nog steeds planair is.

Het lukt mij niet om te bewijzen dat 1 impliceert 2, en dat 2 impliceert 1. Met een tekening lukt het maar dat is geen bewijs. Hulp is gewenst.

Marco
Student universiteit - woensdag 2 maart 2022

Antwoord

Dit is niet geheel flauw. Bij het werk aan planaire grafen wordt gebruik gemaakt van de Curvenstelling van Jordan; het bewijs hiervan is niet triviaal.

Met behulp hiervan kun je inzien dat de rand van de onbegrensde component van het complement uit de punten en een deel van de lijnen uit de graaf bestaat en dat je met de klok meet over een grote cirkel je graaf kunt lopen en dan aan je rechterhand om en om een punt en een lijn ziet (het kan zijn dat je sommige lijnen en punten meer dan één keer ziet. Je kun dan telkens een kromme van de cirkel naar elk punt dat je ziet maken en zo dat die krommen elkaar niet snijden. Buiten de cirkel kun je die doortrekken naar één enkel punt en dat bewijst de ene implicatie (er zijn veel details in te vullen).

Het omgekeerde is makkelijker: als die uitgebreide graaf planair is teken hem dan zonder kruisende lijnen op een boloppervlak. De krommen vanuit het extra punt laten zien dat alle punten liggen op de rand van de component van het complement waar het extra punt in ligt. Laat uit die component één punt weg (dat niet op de graaf ligt. Wat je overhoudt van het boloppervlak is het platte vlak.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 2 maart 2022



klein |  normaal |  groot

home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3