Re: [理工] 圖論

[Bearcome (超級喜歡哈孝遠)]

※ 引述《Bearcome (超級喜歡哈孝遠)》之銘言：
:  http://miupix.cc/pm-VKFHXW
: 8*8西洋棋盤的一題
: 不知道下面答案表格怎麼來的
: 請大家幫個忙
Draw a graph with 64 vertices representing the squares of a chessboard.
Connect two vertices with an edge if you can move legally between the
corresponding squares with a single move of a knight.
[The moves of a knight are L-shaped, two squares vertically (or horizontally)
followed by one square horizontally (respectively, vertically).]
(a)This graph is bipartite.
(b)4 vertices of degree 2
(c)4 vertices of degree 3
(d)20 vertices of degree 6
(e)16 vertices of degree 8

Ans:a b e

在黃子嘉的離散課本上有看到類似的題目

答案上有個8*8表格

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

想了很久還是不太懂這個表格的意思

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.186.95
※ 編輯: Bearcome        來自: 123.193.186.95       (10/12 11:28)
推 XII:騎士在每個位置可走的方法(不就是題目嗎?)
→ Bearcome:234我大概懂 卡在68不知道怎麼出來的= =
推 numin:簡單說,就是你在每一個格子,把他當成象棋的馬,可有幾種走法
→ numin:假設表格左下是(1,1):則走"馬"字可以走到(3,2)和(2,3),所以2
→ numin:若現在算(3,2)=6:有(1,1)(1,3)(2,4)(4,4)(5,3)(5,1)六種走法
→ Bearcome:原來是日...我搞錯題目意思