Hamiltoncykel i bipartit graf
Hej!
Usel bild. Jag ska rita en hamiltoncykel som finns i en bipartit graf. Det måste tydligen finnas ett sammanband mellan grafens m,n för att en hamiltoncykel ska finnas.
Jag har av kurskamrat fått höra att M och N måste vara lika, dvs att det måste finnas lika många hörn på vänster och höger led för att en hamiltoncykel ska finnas. Men jag förstår inte detta. I bilden har jag ritat en hamiltoncykel som är 4x4 som i uppgiften, men även testat 4x3 vilket också verkar funka. Vad är det jag inte förstår?
Du har hittat en hamiltonstig, men för att det ska vara en cykel måste den börja och sluta på samma ställe.
Tänk efter och rita lite på saken så kommer du inse varför det måste vara lika många på båda sidor. Bipartit betyder ju att man alltid går från ena sidan till andra. Om du bara får använda varje hörn en gång, vad skulle då hända när de är slut på ena sidan men inte den andra?
