作者arist ( 在他方 )
看板puzzle
标题Re: [构造]3-regular graph,d<4
时间Tue Nov 11 23:44:09 2003
※ 引述《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)