解説（研究紹介）♦♦♦♦♦♦解 説♦♦♦♦♦♦

グラフ理論の紹介とグラフの本型埋め込み問題について

田中 勇樹1はじめに

1「グラフ理論とは何ですか？」と聞くと，ほとんどの方が “グラフ” という言葉を “棒グラフや円グラフなど，様々な数値を視覚的に表現したもの” の意味で捉えるので，「グラフ理論？どう書いたら見やすくなるか，とかですか？」や，「理論なんてあるんですか？」と答えると思います．ここで言う “グラフ” とはそのようなものではなく，“対象物（有形，無形を問わない）の集まり” と，“対象物間の関係” を簡単な図で表したものを指します（graph という英単語には “図示する” という意味がありますので，厳密には間違いではありませんが，図示する対象が異なります）．図 1 にグラフの例を示します．丸で描かれているものを頂点と呼び，対象物を表します．頂点の間にある線を辺と呼び，辺がある対象物のペアには関係があることを，辺がないペアには関係が無いことを表します．表 1 に対象物とその関係についていくつかの例を挙げ，図 2 に，代表的なグラフを例示します．
表 1: 対象物とその関係

頂点辺

図 1: グラフの例

対象物関係

人間

知り合い

家族

親子，親類縁者駅

路線

端子，電子部品

電気回路

コンピュータネットワーク（プログラミングでの）関数

呼び出し

ウェブサイトリンク

グラフの数学的な定義は，次のように書き表すことができます（[9] より抜粋）．
グラフとは，頂点集合 V と辺集合 E の 2 種類の集合の対 (V, E) である．Vの要素を頂点，E の要素を辺と呼ぶ．辺 e ∈ E には，端点と呼ばれる 2 つの頂点（V の要素）が対応する．
1

情報科学センター 助教 ytanaka@isc.kyutech.ac.jp

九州工業大学 情報科学センター
広報 第 21 号 2009.3

56

解説（研究紹介）

PathCycle

Wheel

Grid(Mesh)

Hypercube

Complete graph

Tree

Bipartite graph

図 2: 様々なグラフ

グラフ理論は代数論や組合せ論などと同様，整数を主に扱う離散数学の一分野であり，離散数学は理論計算機科学の分野で頻繁に利用されます．理論計算機科学はコンピュータに様々な問題を解かせる上で基礎となっている分野であり，その中でグラフは特にアルゴリズム理論や計算量理論，データ構造論などで道具として多用されます．グラフに置き換えて問題を考えることで，コンピュータで解きやすくしたり，関連性の類似点などを見つけたりなど，様々な応用が考えられています．
本稿では，グラフ理論の紹介として，始めに身近にあるグラフの例，次にグラフ理論の分野で広く研究されているグラフの描画問題について触れます．そして，我々の研究テーマの一つであり，表題にもあるグラフの本型埋め込みについての紹介と研究成果，その応用分野について解説を行います．

身近にあるグラフ2

本節ではグラフ理論の紹介として，身近にある例を二つ挙げ，グラフ理論との関係について説明します．一つめはグラフを利用して問題を解く例，二つめはある社会的性質からグラフを構成し，研究されている例です．

2.1

全ての橋を上手に渡るには？
：ケーニヒスベルグの橋渡り

最初に，ケーニヒスベルグの橋渡り問題を紹介します．この問題はグラフ理論の問題として最も古いものであり，最も有名なものです．
ケーニヒスベルグ（現：カリーニングラード）には，図 3 のようなプレーゲル川と，その川に大小 2 つの中州があります．大きな方の中州には川の両岸から 2 本ずつ橋が架かっており，57

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）

図 3: ケーニヒスベルグの橋

図 4: 両岸と中州，橋を表したグラフ

小さな方には両岸から 1 本ずつ橋が架かっています．加えて，2 つの中州の間にも橋が 1 本架かっています．
問題です．ケーニヒスベルグの川には全部で 7 本の橋が架かっていますが，7 本の橋全てを，それぞれちょうど 1 回ずつ渡る道順はあるでしょうか？出発地，到着地はどちらの川岸からでも，どちらの中州でも構いません．
この程度の大きさ（橋の本数）であれば，橋を渡る順番を全て考え，それらを調べ尽くすことも可能ですが，これが 100 個の島からなる橋渡りの問題だとしたら非常に大変です．この問題はグラフ理論の話を用いると，理論的に “求めたい渡り方は存在しない” とすぐに言えます．
両岸と 2 つの中州の計 4 つを頂点，橋を辺に対応させると図 4 のようなグラフを作ることができます．このグラフを一筆書きできるならば，その順に従って渡れば良いのですが，一筆書きができる図形は “始点と終点を除いて，他の全ての経由地は偶数本の線がつながっていなければならない” という原則があることが知られています．図 4 を見ると，4 つある頂点のうちどの 2 つを始点と終点に選んでも，経由地となる残りの頂点には奇数本の辺がつながっていますので，一筆書きが出来ない，つまり，求めたい渡り方は存在しないと言うことができます．
この問題は 1736 年に数学者オイラーによって証明されたため，グラフ理論の分野では一筆書きができるグラフをオイラリアンである，と呼び，一筆書きの経路はオイラー閉路と呼ばれています．

2.2

見知らぬ誰かまで，何人で辿りつく？
：スモールワールド

友達の友達の友達の…と辿っていくと，およそ 6 人辿ることで世界中の誰とも繋がる，という話を聞いたことはありませんか？これはスモールワールド現象と呼ばれるもので，1967 年に心理学者スタンレー・ミルグラムが行った実験 [6]（アメリカ合衆国国民から無作為にペアを抽出し，そのペアが知り合い関係で繋がるとき，何人を経由するか）の平均距離がおよそ 6であったことから，この数字が有名になりました．近年ではスモールワールドグラフという形で，グラフ理論の研究者はもとより，局所的な構造（知り合い関係）のみを考えることで全体の構造がどのように構成されるかの例として，社会科学や複雑系の研究者などにも研究の対象
九州工業大学 情報科学センター
広報 第 21 号 2009.358

解説（研究紹介）とされており，関連する本なども出版されています [3]．
この考えの応用として，ベーコン数 [10] とエルデシュ数 [11] と呼ばれるものがあります．ベー
コン数は映画俳優，ケビン・ベーコンを基点とし，彼と共演したことのある俳優はベーコン数

1，ベーコン数 1 の俳優と共演した俳優はベーコン数 2 と数値が振られていきます．各自の持つベーコン数は，ケビン・ベーコンまでの最短の共演関係で計算し，新たな共演関係が増えるごとに変化する可能性があります．
図 5 は頂点を俳優，辺を共演関係としたグラフで，ケビン・ベーコンを表す頂点を最上部に配置したものです．ケビン・ベーコンを中心に，ピラミッド状にグラフを描くことができます．
ケビン・ベーコン

ケビン・ベーコンと共演したことのある俳優
ベーコン数1

ベーコン数1の俳優と共演したことのある俳優
ベーコン数2

図 5: ベーコン数を表すグラフ

日本人では渡辺謙や北野武，役所広司などがベーコン数 2 です．ハリウッドで活躍する俳優はもとより，日本人やその他の国の俳優でもそのほとんどがベーコン数が 6 以下だと言われています．
エルデシュ数は数学者ポール・エルデシュを基点とし，エルデシュと論文を共著で出版した
ことのある研究者はエルデシュ数 1，エルデシュ数 1 の研究者と論文を共著したことのある研究
者は 2 と，ベーコン数と同じように論文の共著関係をたどっていくことで与えられます．ポール・エルデシュ自身は故人ですので，エルデシュ数 1 を持つ研究者は今後増えることはありませんが，世界で 500 人ほどおり，エルデシュ数 2 を持つ研究者は 8000 人以上います2 ．更に，エルデシュ数を持つほとんどの研究者が 10 以下という統計結果もあります．ポール・エルデシュ
は数学の研究を幅広く行っていましたが，数学に限らず計算機科学の分野でもエルデシュ数を持つ人が多くおり，他には統計学や遺伝学，言語学者，政治学者でさえエルデシュ数を持っていることがあります．

グラフをきれいに描く

3グラフそのものの数学的な定義は 56 ページにある通り二種類の集合の対なので，グラフが与えられたら必ずこのように描かなくてはならない，という決まったルールは存在しません．そ2

筆者の 2009 年 1 月時点でのエルデシュ数は 459

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）のため，隣接関係をきちんと守ってさえいれば頂点をどのような形に配置しても問題はありません．例えば図 6 は九州 7 県を頂点，陸続きの県境を持つ県同士を辺で結んだグラフです．この図の頂点は各県の位置関係を基本に図示されていますが，グラフを描く際には隣接関係を正確に表していれば良いので，図 7 のような描き方をしても問題はありません．本節の表題にある “きれいに” の尺度は，見る人の主観により大きく異なりますので，図 7 がよりきれいに描けている，と思う人もいるかもしれません．
福岡佐賀
長崎 佐賀
長崎

福岡 大分 宮崎 鹿児島

大分
熊本
熊本宮崎

図 7: 図 6 の異なる描き方

鹿児島

図 6: 九州 7 県とその隣接関係

人間がグラフを見る際に “きれいに描けている” と思う基準として(1) 頂点が順序よく，規則正しく並んでいる(2) 頂点が格子点上などに等間隔に並んでいる(3) 辺の交差が最小限になるように描かれている(4) 辺が全て直線で描かれている(5) 辺の交差する角度が直角に近い(6) 図 6 のように付加情報が含まれているのようなものが挙げられます．またグラフを回路設計など他の分野へ応用する際には，その分野に応じた制約条件（辺の長さや密度など）が関係してくるため，人間が見てきれいと思えるグラフの描画が制約条件を満たさないことも考えられます．そのため，グラフの描画方法として様々なものが提案され，現在も研究が進められています．
本稿では，グラフの描画問題の一つである本型埋め込みに関して解説を行い，具体的なグラフについての結果を与えます．

4

頂点を一直線に並べるレイアウト：本型埋め込み
本節では我々が研究の対象として扱ったグラフのレイアウト問題である，本型埋め込み [1] について紹介します．
九州工業大学 情報科学センター
広報 第 21 号 2009.360

解説（研究紹介）

表 2: 様々なグラフクラスのページ数
グラフクラス

ページ数

外平面グラフ142⌈n/2⌉≤ ⌈(m + 2n)/4⌉≤ 2k + ⌈2k/(r − 1)⌉
≤ 2k3
≤d+1
≤d+1n−1

平面グラフ
メッシュ完全グラフ Kn
完全 2 部グラフ Km,nk 進 r 桁 butterfly グラフ（r が奇数）
k 進 r 桁 butterfly グラフ（r が偶数）
Shuffle-exchange グラフ
de Bruijn グラフ D(d, n)Kautz グラフ K(d, n)
hypercube“本” とは，スパイン（本の背の部分）と呼ばれる直線と，ページと呼ばれるスパインを境界線とする半平面から構成される構造体を表します．本型埋め込みとは，この本にグラフの頂点と辺を配置する問題です．頂点はスパイン上に配置されます（配置する順序はこちらで与えることができます）．辺はページに割り当てるのですが，各ページ内では辺の交差が起きないよ
うに適切に振り分けることが制約条件となります．
図 8 に本，図 9 にグラフの本型埋め込みの例を示します．
Page 2

Page 1Page 3Spine
Page 4
Page 6

Page 5

図 8: 本と各部名称

図 9: グラフの本型埋め込みの例

グラフが与えられたとき，そのグラフを埋め込むのに必要なページの数はそれぞれ異なります．本型埋め込みの解の尺度として，いかに少ないページ数で埋め込むか，というのがあります．表 2 にグラフの本型埋め込みに関する既知の結果を示します．
我々はこれまでに，キューブ連結サイクルと呼ばれるグラフが 3 ページ本型埋め込み可能であること [7]，また Trivalent Cayley グラフと呼ばれるグラフが 5 ページ以下での本型埋め込み
61

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）が可能であること [8] を示しました．前者の 3 ページという結果は，理論的にほぼ最適な値であることも示せます．本稿では前者について説明を行いますが，その前にこの問題の難しさについて解説します．

4.1

最適な本型埋め込みを求めるために必要な計算の量グラフの本型埋め込み問題，特にページ数最小の埋め込みを与えることは非常に難しい問題であることが知られています．その難しさは，解となりうる組合せの膨大さから説明することができ，その膨大さは二種類の組合せから導かれます．最初に頂点をどのような順序でスパインへ配置するかを考える必要があります．これは n 個の頂点を持つグラフに対し (n − 1)!/2 =(n − 1) × (n − 2) × · · · × 4 × 3 通り考えることができ，この中から最適なものを選ぶ必要がありますが，頂点の順序が決まっただけではページ数を決定することはできません．頂点の順序を決定した上で，次に辺のページへの割り当てを考えます．頂点の順序を決定すると，各辺の長さと両端点の位置が決定します．この条件をもとに，各分割集合内で辺が交差することがないように辺集合をいくつかに分割するという問題を考える必要がありますが，この問題は NP完全に属することが示されています．表 2 に挙がっているページ数は，各グラフの定義や，そのグラフが持つ性質などからそれぞれ個別に解を得ています．

キューブ連結サイクルの 3 ページ本型埋め込み

5

本節ではキューブ連結サイクルの本型埋め込みについて説明します．始めに今回扱うグラフクラスであるキューブ連結サイクルの定義を紹介し，次に最適な本型埋め込みを与える手順について説明します．

5.1

キューブ連結サイクルの定義

n 次元キューブ連結サイクル CCC(n) [4] は，レベルと呼ばれる 0 から n − 1 までの整数と，列と呼ばれる二進 n 桁列のペアにより頂点集合が定義されます．キューブ連結サイクルの隣接関係は 2 種類あり，一つはレベルが n を法としてちょうど 1 異なり，列が同じであること，もう一つはレベルが同じで，列のちょうどレベル桁目のみ異なることです．前者の隣接関係によって作られる辺をここでは C 辺，後者のそれを S 辺と呼んで区別します．図 10 に 4 次元キュー
ブ連結サイクル CCC(4) を示します．図 10 では C 辺を左右方向，S 辺を上下方向に描いています．
図 10 では，頂点を格子状に整列させています．上にある数字がレベルを表し，同じ列にある頂点は同じレベルを持ちます．グラフの右に書いてある二進 4 桁列は頂点の列を表し，同じ行にある頂点は同じ二進列を持ちます．

九州工業大学 情報科学センター
広報 第 21 号 2009.362

解説（研究紹介）

012

30000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
110011011110
1111

図 10: 4 次元キューブ連結サイクル

5.2

キューブ連結サイクルに関するこれまでの結果

キューブ連結サイクルの本型埋め込みは以前 [2] で研究され，そこでの結果は n − 1 ページあれば十分であるというものでした．この結果はキューブ連結サイクルと類似した構造を持つハイパーキューブのページ数が n − 1 ページであることに由来しています．我々の研究はそれとは全く異なったアプローチにより，[2] で与えられた結果を改善，ページ数に関して最小の本型埋め込みを与えています．また，CCC(3) に関しては今回の結果とは別の方法で 2 ページに埋め込み可能であることが簡単に示せます．

5.3

本型埋め込みの第一段階：頂点のスパインへの順序づけ

本型埋め込みの第一段階として，頂点をどのような順序でスパインへ配置するかについて考えます．本来であれば数式を用いて理論的に証明を行う必要がありますが，ここでは紙面の都合上，図を用いて直感的に説明を行います．
図 10 を見ると，C 辺同士は交差することなく描けていますが，S 辺は他の S 辺と交差しているものがほとんどです．頂点を格子状に整列させているこのレイアウトを基本に，S 辺同士の交差をなくすような頂点のレイアウトを考えることができます．
レベル 0 同士の頂点を結ぶ S 辺に着目すると，S 辺で隣接する頂点は図で言うと 8 つ隣となります．これはどのレベル 0 の頂点も同じです．このことから，グラフの下半分を（他のレベ63

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）

ルも含めて）上下反転して描画することを考えます．すると，1111 の列を持つ頂点が 0111 の列を持つ頂点のすぐ下に配置され，その上下にはそれぞれ 1110 と 0110 が，そのさらに上下には 1101 と 0101 が，という形に配置されます．その結果，レベル 0 の頂点同士を結ぶ全ての S辺を，入れ子構造を持つような形で描くことが出来ます．
図 10 の下半分を上下反転させたグラフが図 11 です．
012300000

1230000

0001

0001

0010

0011

0011

0010

0100

0110

0101

0111

0110

0101

0111

0100

1111

1100

1110

1101

1101

1111

1100

1110

1011

1010
1011

1010

1001

1001

1000

1000

図 11: 図 10 の下半分を上下反転させた CCC(4)図 12: 行の入れ替えを何度か行った CCC(4)次に，レベル 1 の頂点同士を結ぶ S 辺に着目します．このレベルにある S 辺も，レベル 0 と同様に行ごと入れ替えを行うことで交差をなくすことができます．ここで，レベル 1 の頂点のみに着目して行の入れ替えを行うときに，レベル 0 の頂点同士を結ぶ S 辺の入れ子構造を崩さないようにする必要があります．ここでは内側の 8 行（0100〜1100）を，4 列ごと上下反転させる形をとります．すると，レベル 0 同士の辺を結ぶ S 辺の入れ子構造を保持したまま，レベル 1 同士の頂点を結ぶ S 辺もまた，入れ子構造を持つような形で互いに交差することなく描くことができます．
レベル 2 も同様に，レベル 0 やレベル 1 の構造を崩さないように行の入れ替えを行います．
上記の操作をレベルの大きな頂点集合に対して順次着目して行うことで， S 辺同士の交差がない，格子点上へ頂点を配置するレイアウトが得られます．図 12 は次元が 4 のとき，上記の手順を行うことで S 辺同士の交差をなくしたレイアウトです．頂点のスパインへの順序づけは，レベル 0 の頂点は図 12 で言うところの上から下の順とし（ここでは正順と呼びます），その次にレベル 1 の頂点を下から上の順（同，逆順），レベル 2 の頂点を正順，レベル 3 の頂点を逆順とします．次元が偶数のときは，このようにレベルが偶数であるものを正順，奇数であるものを逆順としてスパインへの順序づけを行いますが，次元が奇数のときは，レベル n − 2 の頂点集合とレベル n − 1 の頂点集合を，ともに逆順になるように，かつ S 辺同士，C 辺同士が交差しないように一つの頂点集合に，図 13 の手順でまとめます．この操作は，後述する辺のペー
九州工業大学 情報科学センター
広報 第 21 号 2009.364

解説（研究紹介）

ジへの割り当てに関して重要な役割を持ちます．
(n-2;*00)(n-2;*00)n-2(n-1;*00)(n-1;*00)*00(n-1;*01)(n-1;*01)*01(n-2;*01)(n-2;*01)*11(n-2;*11)(n-2;*11)*10(n-1;*11)(n-1;*11)(n-1;*10)(n-1;*10)n-1(n-2;*10)(n-2;*10)

図 13: 次元が奇数のときの，レベル n − 2 と n − 1 のまとめ方

5.4

本型埋め込みの第二段階：辺のページへの割り当て

前節でスパインへの頂点の順序づけを与えました．本節では，その順序づけに基いて辺を 3ページに割り当てる方法について説明します．
はじめに S 辺について考えます．図 14 は図 12 から S 辺のみ抜き出したものです．この図を見ると全ての S 辺がスパインの左側に描かれており，S 辺同士で交差は発生していません3．
よって，全ての S 辺を 1 つのページに割り当てることが可能です．
0120

3

12

30000

0000

0001

0001

0011

0011

0010

0010

0110

0110

0111

0111

0101

0101

0100

0100

1100

1100

1101

1101

1111

1111

1110

1110

1010

1010

1011

1011

1001

1001

1000

1000

図 15: 図 12 から C 辺のみ抜き出したグラフ

図 14: 図 12 から S 辺のみ抜き出したグラフ

次に C 辺について考えます．図 15 は図 12 から C 辺のみ抜き出したグラフです．図 15 で上下に折り返して描かれているスパインを直線状にしたものを図 16 に示します．網掛けの部分
3スパインと重なって描かれている S 辺もありますが，これは問題ありません．

65

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）が 4 つありますが，それぞれがレベル 0 の頂点からレベル 3 の頂点の集合で，16 個ずつ頂点が含まれます．

図 16: 図 15 のスパインを直線状に表した状態と C 辺

全ての C 辺は図 16 のように，レベル間の辺が全て入れ子構造を持つように描画することができます．これは，偶数のレベルを持つ頂点が正順に，奇数のレベルを持つ頂点が逆順にスパインへ配置されているためです．このことから，この図の上半分を 1 つのページ，下半分を 1つのページと考えれば 2 ページで全ての C 辺を配置することができることが分かります．
次元が偶数のときはレベル n − 1 の頂点集合は逆順になっているので，図 12 のように並べることができます．しかし，次元が奇数のときは，偶数のときと同様にレベルの偶奇性のみによってレベル内の順序を与えると，レベル n − 1 の頂点集合は正順となり，同じく正順である
レベル 0 の頂点との C 辺を図 16 のように並べることができません．しかし，64 ページの図 13で与えたように，レベル n − 1 の頂点集合をレベル n − 2 の頂点集合とまとめ，逆順にすることで，図 16 のように，レベル n − 1 の頂点とレベル 0 の頂点を結ぶ全ての C 辺を，入れ子構造を持つようにページへ配置することができます．
全ての S 辺が 1 ページに配置可能であることと合わせて，全体で 3 ページあればキューブ連結サイクルの全ての辺を配置できることが示せました．図 17 に 4 次元キューブ連結サイクルの 3 ページ埋め込みを，辺や頂点を省略しない形で掲載します．楔形に描かれた辺 は S 辺で，1 ページめに配置されています．矩形状に描かれた辺は C 辺で，頂点の列の上側が 2 ページめ，下側が 3 ページめに配置されています．
この埋め込みがページ数に関して最適であることを示して，この節を閉じます．あるグラフが 2 ページ以下に埋め込みが可能がであるならば，グラフを平面に辺の交差なく描けると言えます．キューブ連結サイクルは 3 次元のものに関しては 2 ページに埋め込み可能であることが示されていますが，4 より大きな次元では平面に辺の交差なく描くことが出来ないことが示されているため，2 ページでは埋め込めないことが言えます．よって 3 ページが最適と結論づけることができます．

6

本型埋め込みの応用
本稿の最後に，今回扱った本型埋め込みの応用分野について紹介します．本型埋め込み問題

はグラフレイアウト問題の一つなので，電気回路などの設計に直接応用が可能です．一般のグ
九州工業大学 情報科学センター
広報 第 21 号 2009.366

解説（研究紹介）

図 17: 4 次元キューブ連結サイクルの 3 ページ埋め込み

ラフレイアウト問題と異なる点は頂点を直線状に並べることですが，物理的な配置として直線でなくても，平面上でスパインが交差しないように配置すれば良いので，図 12 のような形で頂点を配置し，それに従って辺を配置することも可能です．
本型埋め込みの応用として有名なものに，プロセッサアレイを構築するための DIOGENES法 [5] があります．DIOGENES 法はまず，図 18 のように回路基板上にプロセッサを並べ，その両側に相互結合用の配線束を設置します．各プロセッサはその配線束と電気的なスイッチにより接続しています．

図 18: プロセッサの列と配線束プロセッサ間の相互結合を配線束を使用することで構成する際に，どの配線束のどの位置にある配線を使用するかは，相互結合網をモデル化したグラフをどのように本型埋め込みするかによって決定できます．プロセッサをグラフでの頂点に対応づけ，配線束一つを本の 1 ページに対応させる．配線束は両側だけではなく，より多く使用することができますが，配線束やスイッチを多く用意することはコストに直結しますので，より配線束数の少ない，つまりページ数の少ないグラフの本型埋め込みを求めることが重要になります．

67

九州工業大学 情報科学センター
広報 第 21 号 2009.3

解説（研究紹介）

7

おわりに
本稿では，グラフ理論の紹介と身近にあるグラフ，そしてグラフのレイアウト問題の一つとしてグラフの本型埋め込みについて解説し，我々の研究成果の紹介としてキューブ連結サイクルの本型埋め込みに関する結果を示しました．
はじめにでも示した通り，グラフ理論は，離散数学の分野の中でも基礎的なものなので，応用の幅は非常に広く，グラフを便利な道具として利用している研究は多岐に渡っています．特にデータ構造やアルゴリズム理論，組合せ最適化問題などにはグラフの話が頻繁に顔を出し，その解法にグラフ理論での定理が利用されていることもあります．
本稿を通じ，皆さんがグラフ理論に興味を持っていただけたら幸いです．

参考文献[1] F. R. K. Chung, F. T. Leighton and A. L. Rosenberg, Embedding graphs in books: Alayout problem with application to VLSI design, SIAM J. Alg. Discr. Methods, 8(1987)
33–58.
[2] 鴻江 美智子，萩原 兼一，都倉 信樹，本型埋め込みにおける超立方体グラフと超立方体環グラフのページ数について, 信学論 J71-D，No.3，pp.490–500，1988．

[3] 増田 直紀, 今野 紀雄, 「複雑ネットワーク」とは何か – 複雑な関係を読み解く新しいアプ
ローチ, 講談社, 2006.

[4] F. P. Preparata and J. Vuillemin, The Cube-Connected Cycles: A versatile network forparallel computation, Commun. ACM, vol.24, No.5, pp.300–309, May 1981.
[5] A. Rosenberg, DIOGENES, circa 1986, Aegean Workshop on Computing VLSI Algorithms
and Architectures,Loutraki, Greece, Lecture Notes in Comput. Sci. 227, pp.96–107, 1986.
[6] Stanley Milgram, The Small World Problem, Psychology Today. Vol.1(1),pp.60–67, 1967.
[7] Y. Tanaka and Y. Shibata, On the pagenumber of the cube-connected cycles, Proc. of
19th International Workshop on Combinatorial Algorithms, pp.155–165, 2008.
[8] Y. Tanaka and Y. Shibata, On the pagenumber of trivalent Cayley graphs, Disc. Appl.
Math. 154, pp.1279–1292, 2006.
[9] 徳山 豪, 工学基礎 離散数学とその応用, 数理工学社, 2003.
[10] The oracle of Bacon, http://oracleofbacon.org/[11] Erdös number project, http://www.oakland.edu/enp/

九州工業大学 情報科学センター
広報 第 21 号 2009.368