【益智問題】graceful labeling
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arist ( 說故事的人 )時間22年前 (2003/01/19 10:27)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
﹝問題﹞
如下圖，在七個圈圈中，填入1~7這七數，使得相鄰兩隔的差可以從1~6。答案不
唯一，我只試列一組。請問：
(1)下一個圖從1~10要如何填入使其相鄰的差為 1~9？(猜想是可完成。)
(2)有何好的方法(or演算法)來判別呢？(ps:我不知答案)
(6) (5) (4) (3)
○─○─○─○─○ 1 7 2 6 3
│ → (2)
○ 4
│ (1)
○ 5
○─○─○─○─○─○
｜ ｜
○ ○ → ？？
｜ ｜
○ ○
﹝說明﹞
這問題是我在《Graph Theory》─B.West一書中(圖論課本)看見的，有個猜想是
所有的tree(沒有迴圈的連結圖)都可完成，但尚未被證明。
﹝備註﹞
圖論中有蠻多有趣簡單問題(敘述上)，當作益智問題還蠻不錯。有些數學家並不
覺得圖論算是正統數學，像是數學遊戲，不過在電腦進來後就變重要些。
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.83
※ 編輯: arist 來自: 140.112.249.83 (01/19 10:27)
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
16
26
20
30