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}

Re: De graad van een vertex in een outerplanar graaf

 Dit is een reactie op vraag 93419 
Bedankt voor uw antwoord. Prachtig bewijs. Stel dat er een lijn is van w1 naar w2, en een lijn van w2 naar w3. Stel nu dat het kortste pad van w1 naar v via w2 en dan w3 gaat. Stel nu ook dat het kortste pad van w2 naar v via w3 gaat. Stel verder dat het kortste pad van w3 naar v niet via de andere w’s gaat. Dan hebben we geen cykel waarin een w ‘opgesloten’ zit. Hoe lossen we dit randgeval op?

Richard
Student universiteit - zaterdag 5 maart 2022

Antwoord

Het geval dat het kortste pad van $w_1$ naar $v$ via $w_2$ en $w_3$ gaat doet zich niet voor: dan is dat kortste pad $1$ langer dan het het pad dat je krijgt door van $u$ naar $w_3$ te gaan en dat het pad vanuit $w_1$ te volgen.
Maar het zou toch mogelijk zijn dat de kortste paden vanuit $w_1$ en $w_3$ (ook) via $w_2$ lopen.

Daarom moeten we he bewijs toch iets aanpassen: volg het bewijs van mathoverflow tot we een graaf zonder inner edges hebben, en neem aan dat die samenhangend is. Bekijk de laatste inner edge, zeg $\{a,b\}$.
Neem vanuit elk ander punt het kortste pad naar $a$, en neem het punt $u$ waarvoor dit punt het langst is, en neem aan dat die drie buren $w_1$, $w_2$, en $w_3$ heeft.
Als nu, bijvoorbeeld, $w_2$ met $w_1$ en $w_3$ verbonden is dan is $\{u,w_2\}$ een inner edge binnen het cykel $\{u,w_1,w_2,w_3\}$, maar dat kan niet.
Er is dus ten hoogste één verbinding tussen de buren. Als die er niet is zijn we klaar, als in het vorige antwoord.
Als, bijvoorbeeld, $\{w_2,w_3\}$ een verbinding is en het kortste pad van beide naar $a$ loopt via $w_2$ dan loopt er geen ander pad van $w_3$ naar $a$, anders krijgen we dezelfde tegenspraak als in het vorige antwoord.
Dus als $v$ een andere buur van $w_3$ is loopt het kortste pad van $v$ naar $a$ via $w_3$, maar dan is het $1$ langer dan het kortste pad van $w_3$ naar $a$ en dus ook $1$ langer dan het kortste pad van $u$ naar $a$, tegenspraak. Conclusie: $w_3$ heeft alleen $u$ en $w_2$ als buren en heeft dus graad $2$.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
zondag 6 maart 2022



klein |  normaal |  groot

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

©2001-2022 WisFaq - versie 3