WisFaq!

Hoe maak ik van een graaf een Euler-graaf?

Hoe kan ik een graaf die geen Euler-graaf is aanpassen zodat het er wel een wordt?

Maike
21-10-2004

Antwoord

Ik neem aan dat je een Euler-wandeling bedoelt, d.w.z. dat je een wandeling kan maken waarbij ieder pad precies een keer gebruikt wordt.

Definitie
Een graaf bestaat uit een verzameling van vertices (punten, knopen,...) en een verzameling van paden (takken, bogen,lijnstukken,..., Engels: edges) die paren vertices verbinden.

Stelling
Als een graaf een Euler-wandeling toestaat dan zijn er hoogstens twee vertices van oneven orde.

Bewijs
Neem een vertex die niet het begin- of eindpunt is. Dan moet voor iedere inkomend pad er ook een uitgaand pad zijn. En al deze paden zijn verschillend. De orde is dus noodzakelijkerwijs even. De enige oneven vertices kunnen het beginpunt en het eindpunt zijn.

Waarmee je probleem in feite is opgelost toch!?

Zie Grafen en Euler-karakteristiek [http://www.science.uva.nl/onderwijs/wns/onderwijsCD/symmetrie/syllabus/node95.html]

WvR
21-10-2004