ネットワークの数理的構造に関する研究

 

すべての頂点の次数が3であるようなグラフをキュービックグラフと呼びます.キュービックグラフの頂点数は必ず偶数になることが知られています(離散数学の授業で習っているはずですが,おぼえていますか?).頂点数Xのキュービックグラフの中で「頂点間の平均距離」がもっとも短いグラフを構成する問題を考えます.

 

X=4のときは4頂点からなる完全グラフが唯一の解で,平均距離は1.0になります.

 

X=6のときは,三角形を2個つくり,それらを平行な3本の辺で結んだグラフの平均距離が1.4となり,これが最小です (これは唯一の解でしょうか?)

 

X=8のときは,8個の頂点を円形に並べ,各自が自分と対面にある頂点との間に辺を張ってつくられるグラフの平均距離が11/7 1.57となり,これが最小です.

 

X=10のときはどうでしょう?平均距離が15/9   1.67となるようなグラフの存在が知られているのですが,自力で構成できますか?

 

より一般的には,与えられた次数と頂点数から,そのときに実現できるグラフの中でもっとも平均距離が短いものを求める問題として考えることができます.この問題は,たとえばスーパーコンピュータやVLSIのレイアウト設計などに応用されています(単純なパズルのようにも見えますが,理論的にもかなり奥の深い問題です).画期的な解法を見つけることができれば,十分卒業論文になります.計算機屋さんや競技プログラマなどが参加しているGraphGolfというコンペもあるので,興味のある人は参加して見てはいかがですか.

 

ップページへ戻る