Re: [構造]3-regular graph,d<4
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arist ( 在他方 )時間21年前 (2003/11/13 10:30)推噓0(0推 0噓 0→)留言0則, 0人參與討論串9/13 (看更多)
: : 那d=3時，最多可有幾點？點數會小於1+3+6+12=22
: 請教一下這是怎麼算的..?
http://homepage.ntu.edu.tw/~r92221005/22_310_112_01.jpg
先以一個頂點來考慮，和這頂點距離為1的可以有 3點
距離為2的可以有 3x2點
距離為3的可以有3x2x2點。
由上22點的圖，再加些討論，可知末端怎麼連都沒辦法使得任兩點的距離不超過3。
所以要將某些點合併。又知3-regular不可能為奇數點，所以20點是最多的狀況。
: 3-regular graph of diameter d ?
: 這種圖有特別的名字嗎?
我現在也不知。
: 還有我很好奇你在想的圖論問題是什麼...^_^
我想要對頂點編號，
‧使得 相鄰兩點 所編的號碼相差至少為2，
‧距離為2的兩點 所編的號碼相差至少為1。
一般的圖太"鬆"了所以編號很容易，
我想構造一個很"密"的圖，來檢驗演算法編號的好壞。
───────────────────────────────────────
※ 編輯: arist 來自: 140.112.25.183 (11/13 10:46)
討論串 (同標題文章)
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
17
26
