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} Printen

3 reguliere graaf: bewijzen dat er altijd een cykel met even lengte bestaat

Ik wil bewijzen dat een 3 reguliere graaf g=(v,e) altijd een cykel van even lengte bevat. Je kunt niet aannemen dat de graaf samengesteld is toch? Als hint wordt gegeven dat je kunt kijken naar het langste pad: Het startpunt heeft graad drie, 'wat betekent dit?' Ik had bedacht dat het langste pad altijd door alle punten kan gaan in een drie reguliere graaf en dus lengte |v| - 1 heeft, hebben we hier wat aan?

Lisa
Student universiteit - dinsdag 16 juni 2015

Antwoord

Hallo Lisa,

Laten we er vanuit gaan dat de graaf samenhangend is, kies zonodig een samenhangende deelgraaf.

Kies een punt p van de graaf, zodanig dat de graaf samenhangend blijft als het punt wordt verwijderd. Punt p was verbonden met drie punten, zeg q, r en s. Aangezien de graaf zonder p nog steeds samenhangend is, is q verbonden met r via een pad (t0=q, t1, ..., tn=r). We kunnen een kortste verbinding maken van s met een van de punten ti op dit pad (eventueel kan s met ti samenvallen). Dat betekent dat er vanuit het oorspronkelijke punt p drie disjuncte paden lopen naar ti, via q, via r en via s. Van deze drie hebben er ofwel twee even lengte, ofwel twee oneven lengte (duiventilprincipe). Een dergelijk tweetal laat zich combineren tot een cykel van even lengte.

Vriendelijke groet,

Zie DisWis - Grafentheorie

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 19 juni 2015



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

©2001-2024 WisFaq - versie 3