WisFaq!

Hamilton pad

Is er een algemene formule te vinden waarmee je kunt berekenen of er een Hamilton pad in een veelvlak zit? Of is een hamilton pad in elke veelvlak mogelijk? Hopelijk kunnen jullie me helpen...Bvd

Judith
21-4-2003

Antwoord

Hoi Judith,

Ik zag dat je vraag al een tijdje niet beantwoord was, dus waag ik een poging.

Laat ik eerst voor de duidelijkheid het onderscheid maken tussen een hamilton-pad en een hamilton-cykel:

• Een hamilton-pad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op het pad ligt.
• Een hamilton-cykel is een hamilton-pad, waarbij het eindpunt hetzelfde is als het beginpunt (dit punt komt dus als enige 2 keer voor op je pad)

De eerste van je twee vragen kan ik met zekerheid beantwoorden:
Er is geen formule waarmee je kunt berekenen of er een Hamilton pad in een veelvlak zit. Om te bepalen of er een hamilton-pad in een graaf zit (veelvlak is een speciaal geval van een graaf) zit er meestal niks anders op om net zolang paden te proberen tot je er een gevonden hebt (wordt meestal aan een computer overgelaten).

De tweede vraag is erg interessant, en hierover hebben veel beantwoorders nagedacht. Veelvlakken kunnen hele vreemde dingen zijn. Je kunt bijvoorbeeld een vierkant gat in een kubus maken (zodat je een soort vierkante donut hebt). Dit ding is ook een veelvlak. Hierin is geen hamiltonpad te vinden, omdat de binnenkant van het gat en de buitenkant van de kubus niet met elkaar verbonden zijn (tenzij je natuurlijk zelf een extra verbinding maakt). Niet in elk veelvlak is dus een hamiltonpad te vinden. Ik weet niet of jij ook zulk soort veelvlakken in je hoofd had toen je deze vraag stelde of dat je het alleen had over de zogenaamde convexe veelvlakken.

• Een veelvlak is convex als elke rechte lijn tussen twee willekeurige punten in het veelvlak geheel binnen het veelvlak ligt.

Ik heb geen voorbeeld gevonden van een convex veelvlak waar geen hamiltonpad in zit, en ook heb ik geen bewijs gevonden dat in elk convex veelvlak een hamiltonpad zit, dus ik weet het niet zeker.

Ik hoop dat je hier wat aan hebt,

groeten,

Casper

cz
27-4-2003