Springen naar inhoud

Hamiltonian cycles


  • Log in om te kunnen reageren

#1

gpsgek

    gpsgek


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 21 juni 2008 - 12:59

Het al dan niet vinden van Hamiltonian cycles in eenvoudige grafen lukt mij in veel gevallen wel, maar van de volgende graaf lukt het me het niet. Wie kan helpen? De vraag is of er een Hamiltonian cycle in zit. Zo ja, welke en zo nee, waarom niet?
Geplaatste afbeelding

Alvast bedankt

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 21 juni 2008 - 13:12

'a' zit alleen aan 'c' en 'e'. Als er een Hamiltonian cycle is, dan zal er dus een pad moeten zijn door alle nodes, uitgezonderd 'a', van 'c' naar 'e' waarbij elke node maar een keer wordt aangedaan. Als je kan aantonen dat dat pad er niet is, kun je ook aantonen dat die Hamiltonian cycle er niet is.

#3

gpsgek

    gpsgek


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 21 juni 2008 - 18:53

'a' zit alleen aan 'c' en 'e'. Als er een Hamiltonian cycle is, dan zal er dus een pad moeten zijn door alle nodes, uitgezonderd 'a', van 'c' naar 'e' waarbij elke node maar een keer wordt aangedaan. Als je kan aantonen dat dat pad er niet is, kun je ook aantonen dat die Hamiltonian cycle er niet is.

Beste EvilBro,

Bedankt voor je reactie. Scherp gezien overigens, het feit dat er een edge twee keer getekend was/is was mij niet opgevallen... :D

Overigens aangetoond dat er geen hamiltonian cycle is:

1) Verwijder (d,e), dan moeten (a,c), (a,e), (c,d), (d,f) zich in de cycle bevinden. De cycle kan echter niet gesloten woren, want ofwel vertex g ofwel vertex b mist.
2) Verwijder (e,g) dan moeten (a,c), (a,e), (f,g) en (c,g) zich in de cycle bevinden. Weer kan de cycle niet gesloten worden, want ofwel vertex d, ofwel vertex b mist.
3) Verwijder (b,e) dan moeten (a,c), (a,e), (b,c) en (b,f) zich in de cycle bevinden. Weer kan de cycle niet gesloten worden, ofwel vertex g, ofwel vertex d mist.

Nogmaals dank!

Grtz, Martijn





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures