[理工] [離散] Hamiltonian Path 應用問題

[kev72806 (想太多oo)]

各位鄉民好

對於此題的理解不是很深

題目講：13 個考試排在連續 13 天內，若有兩個考試排到同一個 instructor 則這兩個
考試不會連續兩天出現。

若一個 instructor 不可能被分配到超過 7 個考試，則這樣的情形是否存在？
http://i.imgur.com/WQsjguN.jpg

小弟的想法是：
造 13 個點表示 13 場考試，而數字表示是哪位 instructor，相鄰兩場考試會不同天出
現這樣。
http://i.imgur.com/bBL5M9z.jpg

可是跟小黃的答案差好多 .....
請教一下是不是有什麼誤解呢 ><

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.19.1.141
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1446277147.A.A67.html
→ jerry031181: 這題算是要證明 不是只找出其中一解而已
推 goldflower: 其實我更無法理解的是這題好像沒指定有幾個instructor
→ goldflower: …
→ goldflower: 這樣可以證嗎XD 還是我英文不好
推 tedchang102: 考慮1～13點，若必須是不同instructor則連成一邊則v1
→ tedchang102: -v2-.......-v13,考慮只有兩個instructor則v1又必須
→ tedchang102: 與v4 6 8 10 12連成邊，以此類推得最小度數=6
推 goldflower: 也就是證明兩個以上的instructor一定排的出來？
→ goldflower: 看起來好像是這樣
→ tedchang102: 感覺好像也可以用生成函數証
噢噢！我可能當成著色問題去想了
※ 編輯: kev72806 (117.19.1.141), 10/31/2015 21:58:18
→ jerry031181: 怎麼用生成函數證阿... 其實這題不太會哈哈QQ
→ tedchang102: 考慮n元13串列不含連續數字的排列方法，n>1必有解
→ jerry031181: 這樣好像也可以轉成Pn的著色數 只是不知道怎套<=7証