Re: [其他] [圖論]關於Knight's tour之疑問
※ 引述《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......
: 可否請教各位高手是否有巧妙解法?感激不盡!!
沒有Hamiltonian cycle應該很簡單
Hamiltonian cycle 是一個包含所有點, 每個點都有連兩個邊
只有一個component 的子圖
很多點, 特別是中間那一排,在原圖就只有兩個邊
這些邊一選取就得到矛盾
Halmitonian path 允許兩個點的degree 為1
分類討論一下應該只是麻煩一點而已
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.72.177.253
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1413941960.A.D5F.html
→
10/22 13:15, , 1F
10/22 13:15, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：