3-regular graph,d<4 - 拼圖

Steve avatar
By Steve
at 2003-11-11T21:14

Table of Contents

這是我最近在想一個圖論問題，而延伸想到的問題。

我想要構造一個圖，每個頂點有三條邊，(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)

Tags: 拼圖

All Comments

怎麼用程式把所有排列可能列出

Victoria avatar
By Victoria
at 2003-11-08T18:07
#include andlt;stdio.handgt; int num[20]; // 要印出的組合 int used[20]; // 某個數字是否使用過 int n; // 要印多少個數字 void lalala(int a){ int i; if ...

怎麼用程式把所有排列可能列出

Sarah avatar
By Sarah
at 2003-11-08T17:49
若有N個不同的東西 就會有N!不同的排列方法 那我們該怎麼用程式列出N!種的可能呢 就拿1-9九個數字當例子 9!種...要怎麼有效改變排列才能完成呢 --------------- 想了好久都想不出來 - ...

希望拼圖也算益智玩具

Delia avatar
By Delia
at 2003-09-11T00:26
※ 引述《MarsofScor ( 惜 緣)》之銘言： : ※ 引述《cattielin (喵子)》之銘言： : : 你可以去台北車站重慶南路上有那個建宏上達三民書局的那一條 : : 沒記錯的話好像在上達書局前或是在前面一點有一`家 : : 專賣很多拼圖的一個攤子~ : : 有很多你可以去那邊問 ...

三人分果汁...

Vanessa avatar
By Vanessa
at 2003-08-17T02:34
兩個人分果汁的話 最公平的方法是 A分成2杯, B先選 那3個人分果汁的話 有沒有最公平的方法? (要考慮3人中可能會有人串通好的問題) -- 人口壓力，請交給保險套解決 　　不要交給戰爭、墮胎或疾病 - ...

一隻鳥的遊戲....

Edward Lewis avatar
By Edward Lewis
at 2003-08-09T21:07
http://www.abc.net.au/gameon/chasm/chasm.swf 有人知道水壩那裡怎麼過嗎? 我是先從左邊樓梯下來的 - ...