Grafentheorie: bewijs lengte cyclus

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.
Plaats reactie
Has
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 13 dec 2015, 15:20

Grafentheorie: bewijs lengte cyclus

Bericht door Has » 13 dec 2015, 15:30

Hoe bewijs ik dat elke cyclus in G een minimumlengte heeft gelijk aan 5?

G =
Afbeelding

arie
Moderator
Moderator
Berichten: 3244
Lid geworden op: 09 mei 2008, 09:19

Re: Grafentheorie: bewijs lengte cyclus

Bericht door arie » 13 dec 2015, 16:07

Een mogelijkheid:

Verdeel de graaf in een rood en een zwart gedeelte, met daartussen blauwe verbindingen:

Afbeelding

De rode punten vormen een cykel met lengte 5,
de zwarte punten vormen eveneens een cykel met lengte 5.

Indien een kleinere cykel bestaat, moet die dus zowel rode als zwarte punten bevatten.
Voor elk zwart punt: welk minimum aantal extra rode of zwarte punten moet een cykel vanuit dat punt bevatten?

Has
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 13 dec 2015, 15:20

Re: Grafentheorie: bewijs lengte cyclus

Bericht door Has » 13 dec 2015, 16:30

arie schreef:Een mogelijkheid:

Verdeel de graaf in een rood en een zwart gedeelte, met daartussen blauwe verbindingen:

Afbeelding

De rode punten vormen een cykel met lengte 5,
de zwarte punten vormen eveneens een cykel met lengte 5.

Indien een kleinere cykel bestaat, moet die dus zowel rode als zwarte punten bevatten.
Voor elk zwart punt: welk minimum aantal extra rode of zwarte punten moet een cykel vanuit dat punt bevatten?
Dat zou dan neerkomen op een cykel van opnieuw een minimumlengte van 5. Bijvoorbeeld 3 extra rode en 1 extra zwarte top.

arie
Moderator
Moderator
Berichten: 3244
Lid geworden op: 09 mei 2008, 09:19

Re: Grafentheorie: bewijs lengte cyclus

Bericht door arie » 13 dec 2015, 16:45

Klopt, en daarmee is het bewijs geleverd.

Wat formeler bewijs je dit met een BFS (https://nl.wikipedia.org/wiki/Breadth-first_search) vanuit elk zwart punt.

Voorbeeld vanuit het meest linker zwarte punt:

Afbeelding

De punten op afstand 1 zijn gemarkeerd,
- deze punten zijn onderling niet verbonden (dus geen cykel met lengte 3)
- er is geen enkel ander punt dat 2 van deze punten verbindt (dus ook geen cykel met lengte 4).

Wegens symmetrie van de graaf hoef je hier maar 3 van de 5 zwarte punten te onderzoeken.

Plaats reactie