→ TKirby:講得很模糊，能詳細說明嗎？^^ 推 140.112.30.49 01/19
> -------------------------------------------------------------------------- <
作者: andan (英雄) 看板: puzzle
標題: Re: 【益智問題】graceful labeling
時間: Sun Jan 19 23:35:30 2003
※ 引述《andan (英雄)》之銘言：
: ※ 引述《arist ( 說故事的人 )》之銘言：
: : ﹝問題﹞
: : 如下圖，在七個圈圈中，填入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(沒有迴圈的連結圖)都可完成，但尚未被證明。
: : ﹝備註﹞
: : 圖論中有蠻多有趣簡單問題(敘述上)，當作益智問題還蠻不錯。有些數學家並不
: : 覺得圖論算是正統數學，像是數學遊戲，不過在電腦進來後就變重要些。
: 印象中在圖論裡這類問題叫graceful labeling
: 一個重要的猜想是對任意tree都會對
: 不過目前為止只有一些特定的tree被證明
: 上次有看到一篇paper是證明 m-ary tree
: 然後毛毛蟲好像也已經被證明了
: 上面的圖我有一組labeling如下
: 1--10--2--9--3--8
: 4 5
: 7 6
: 基本上我的構想是由path出發
: path的做法是 1 +(n-1) -(n-2) +(n-3) ......就可完成
: 然後這題就被我一試就矇中了
如果你問的是path的做法
(假設path的點從 a_0,a_1,....,a_n-1 共n個點)
那就從a_0開始標號
讓 a_0=1 ,
a_k=a_(k-1)+n-k k is odd 且 0<k<n-1
a_k=a_(k-1)-n+k otherwise
其他的圖我沒有好的方法可以一併解決
所以我說矇中的
另解 1--10--2--9--5--6
8 7
3 4
先做左半再到右半
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.230.107.229
﹝問題﹞
如下圖，在七個圈圈中，填入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)
> -------------------------------------------------------------------------- <
作者: andan (英雄) 看板: puzzle
標題: Re: 【益智問題】graceful labeling
時間: Sun Jan 19 14:16:28 2003
※ 引述《arist ( 說故事的人 )》之銘言：
: ﹝問題﹞
: 如下圖，在七個圈圈中，填入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(沒有迴圈的連結圖)都可完成，但尚未被證明。
: ﹝備註﹞
: 圖論中有蠻多有趣簡單問題(敘述上)，當作益智問題還蠻不錯。有些數學家並不
: 覺得圖論算是正統數學，像是數學遊戲，不過在電腦進來後就變重要些。
印象中在圖論裡這類問題叫graceful labeling
一個重要的猜想是對任意tree都會對
不過目前為止只有一些特定的tree被證明
上次有看到一篇paper是證明 m-ary tree
然後毛毛蟲好像也已經被證明了
上面的圖我有一組labeling如下
1--10--2--9--3--8
4 5
7 6
基本上我的構想是由path出發
path的做法是 1 +(n-1) -(n-2) +(n-3) ......就可完成
然後這題就被我一試就矇中了
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 61.230.107.229