Re: [構造]3-regular graph,d<4
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arist ( 在他方 )時間21年前 (2003/11/11 23:41)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/13 (看更多)
※ 引述《arist ( 在他方 )》之銘言：
: 這是我最近在想一個圖論問題，而延伸想到的問題。
: 我想要構造一個圖，每個頂點有三條邊，(3-regular graph)
: 但任兩個頂點的距離要不超過d。那最多可以擺幾個頂點。
: (a,b兩頂點的距離指連結這兩點最少要通過的線段數。)
: 當d=2時，最多可有10點，如下圖。
: http://homepage.ntu.edu.tw/~r92221005/10_310_01.jpg
: 那d=3時，最多可有幾點？點數會小於1+3+6+12=22
: 我目前只構造出16個點的圖。以下為一個12個點的圖。16點過幾天再post。
: http://homepage.ntu.edu.tw/~r92221005/12_312_01.jpg
: ───────────────────────────────────────
: ※ 編輯: arist 來自: 140.112.25.183 (11/11 21:16)
我剛應該畫出20點的，不過現在圖形有點亂，還需想個好的擺法。
因不可能為22 但又不可能為奇數，所以若我沒畫錯則，20點是最多的情況。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.183
※ 編輯: arist 來自: 140.112.25.183 (11/11 23:53)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 13 篇)：
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
107
356
