Handledningsforum

Antal Hamiltonkretsar i en komplett graf?

Antal Hamiltonkretsar i en komplett graf?

by PATRIK BLOMQVIST -
Number of replies: 2

Uppgift 15.12 a i boken.

a) Hur många olika Hamiltonkretsar finns det i K_n, n ≥ 3?

Fråga: Vad menas med att två Hamiltonkretsar är olika? Om man t.ex. tittar på K_3 och antar att hörnen heter v_1, v_2 och v_3. Är kretsarna v_1-v_2-v_3-v_1 och v_2-v_3-v_1-v_2 olika kretsar? Och hur är det med v_1-v_2-v_3-v_1 och v_1-v_3-v_2-v_1? Är dessa olika?

Så vad jag egentligen undrar är om svaret till frågan 

"Hur många olika Hamiltonkretsar finns det i K_3" 

är 1? 

In reply to PATRIK BLOMQVIST

Sv: Antal Hamiltonkretsar i en komplett graf?

by JACOB LÖFVENBERG -
Jag tror att en krets definieras av sina ingående kanter, sedda som en mängd. Din uppräkning är snarare att betrakta som en beskrivning av två möjliga rundturer i din krets. Rundturen kan börja på 3 olika ställen, och den kan ha två olika riktningar, men det är bara en krets (som råkar vara en Hamiltonkrets). Detta framgår inte tydligt i boken, men man kan hitta stöd t.ex. i https://en.wikipedia.org/wiki/Cycle_graph, där en cyklisk graf beskrivs som en graf med exakt en cykel, som kan ha godtyckligt antal hörn.
In reply to JACOB LÖFVENBERG

Sv: Antal Hamiltonkretsar i en komplett graf?

by PATRIK BLOMQVIST -
Tack, det är så jag också valt att tolka det.