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
2-3-2022
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
2-3-2022
#93416 - Grafen - Student universiteit