推 vincentflame: 了解了,感激不盡! 10/22 13:14
※ 引述《vincentflame (vincent)》之銘言：
: 不好意思,近來小弟因個人需要正在複習圖論
: 其中Knight's tour的問題困擾小弟非常久......
: 這裡先提供兩個關於Hamiltonian path/cycle的定理:
: (摘自D. B. West的Introduction to graph theory)
: 1. If G has a Hamiltonian cycle, then for each nonempty subset
: S of V(G), the graph G-S has at most |S| components.
: 2. If G has a Hamiltonian path, then for each nonempty subset
: S of V(G), the graph G-S has at most |S|+1 components.
: 問題來了!!
: 證明:在3X6的西洋棋盤裡,西洋棋中的騎士無法走遍所有格子
: (亦即沒有Hamiltonian path).
: 小弟試圖要用2.的contrapositive sentence(逆否命題)下手,
: 誰料試了許多回,卻一直找不出會讓(G-S的component個數)>|S|+1的S......
: 可否請教各位高手是否有巧妙解法?感激不盡!!
1 2 S S 3 4
5 6 S S 7 8
2 1 S S 4 3
|S|=6,但 c(G-S)=8>|S|+1
故無 Hamiltonian path
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1413951673.A.BAF.html