作者arist ( 在他方 )
看板puzzle
標題[構造]3-regular graph,d<4
時間Tue Nov 11 21:14:18 2003
這是我最近在想一個圖論問題，而延伸想到的問題。
我想要構造一個圖，每個頂點有三條邊，
(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)