[其他] [圖論]關於Knight's tour之疑問
不好意思,近來小弟因個人需要正在複習圖論
其中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......
可否請教各位高手是否有巧妙解法?感激不盡!!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.38.93.31
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1413924572.A.E5B.html
推
10/22 05:03, , 1F
10/22 05:03, 1F
→
10/22 13:14, , 2F
10/22 13:14, 2F
→
10/22 13:17, , 3F
10/22 13:17, 3F
→
10/22 13:18, , 4F
10/22 13:18, 4F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 3 篇)：