グラフ理論

点と、その間を結ぶ線。グラフとはそれだけのものです。それでも同じ図が道路地図、友人のネットワーク、分子、インターネットを表し、そこから生まれる問い、たとえば何色必要か、一筆書きできるかといった問いは、1736年から数学者たちを夢中にさせてきました。

10 個の頂点を持つグラフ(ピーターセングラフ)。同じ色の頂点どうしを結ぶ辺がないように、頂点が3色で塗り分けられている
10 個の頂点を持つグラフ(ピーターセングラフ)。同じ色の頂点どうしを結ぶ辺がないように、頂点が3色で塗り分けられている

頂点と辺

グラフは頂点(ノードともいいます)と辺からなり、各辺は2つの頂点を結びます。頂点をどこに描くかは関係なく、どの組が結ばれているかだけが重要なので、同じグラフでも紙の上ではまったく違って見えることがあります。プレイグラウンドのグラフは単純グラフです。頂点から自分自身への辺はなく、2つの頂点の間の辺は多くても1本です。頂点が n 個なら辺は最大 n(n − 1) / 2 本で、辺をすべて持つグラフを完全グラフといいます。K5 は5頂点の完全グラフです。

次数と握手補題

頂点の次数とは、その頂点につながる辺の数です。すべての次数を足すと、ちょうど辺の数の2倍になります。どの辺にも端が2つあり、それぞれの端で1回ずつ数えられるからです。これが握手補題です。どんなグループでも、一人ひとりが数えた握手の回数を合計すると、握手の総数の2倍になります。このことから、次数が奇数の頂点の数は必ず偶数になります。すべての頂点の次数が同じ k であるグラフを k-正則グラフといいます。

連結グラフ、木、閉路

どの頂点からも辺をたどって他のすべての頂点に行けるとき、グラフは連結です。そうでなければ、連結成分と呼ばれるいくつかの部分に分かれます。閉路とは、同じ頂点を2度通らずに出発点に戻る一周の道で、最短の閉路の長さを内周といいます。閉路のない連結グラフが木で、頂点が n 個の木には必ずちょうど n − 1 本の辺があります。1本少なければばらばらになり、1本多ければ閉路ができます。どの連結グラフにも全域木、つまり一部の辺だけを使ってすべての頂点に届く木が含まれています。

二部グラフと彩色

同じ色の頂点どうしを結ぶ辺がないように、頂点に色を塗ります。そのために必要な最小の色数が彩色数です。1色で足りるのは辺がないときだけです。2色で足りるのは、ちょうどグラフが二部グラフのとき、つまり頂点を2つの側に分けて、どの辺も両側をまたぐときです。デーネシュ・ケーニグは1936年、これが長さ奇数の閉路を持たないことと同値であることを示しました。奇数長の閉路は2色で交互に塗れないからです。3色以上については、このような簡単な判定法は知られていません。3色で足りるかどうかの判定は NP 完全なので、プログラムはプレイグラウンドと同じように探索します。

例:ピーターセングラフ

五角形 A–B–C–D–E と、その内側の五芒星 F–H–J–G–I を考え、五角形の各頂点を星の点と1つずつ結びます: A–F、B–G、C–H、D–I、E–J。これがピーターセングラフで、頂点は 10 個、辺は 15 本です。どの頂点も次数は 3 なので、次数の合計は 30、つまり 15 の2倍です。最短閉路の長さは 5 なので三角形はありませんが、五角形は奇数長の閉路なので二部グラフではなく、3色が必要です。どの2頂点も最大 2 本の辺で結ばれるので、直径は 2 です。10 個の次数はすべて奇数なのでオイラー路はなく、交差なしに描くこともできません。

オイラー路とケーニヒスベルクの橋

ケーニヒスベルクの町には4つの陸地を結ぶ7つの橋があり、人々はどの橋もちょうど1回ずつ渡って歩けるかと考えました。1736年、レオンハルト・オイラーはそれが不可能であることを示し、ここからグラフ理論が始まりました。歩く道が陸地を通過するたびに橋を2本使うので、つながる橋の数が奇数でよいのは出発点と終点だけです。ところがケーニヒスベルクの4つの陸地は、どれも橋の数が奇数でした。すべての辺を1回ずつ通る道は、今ではオイラー路、出発点に戻る場合はオイラー閉路と呼ばれます。カール・ヒールホルツァーは1873年、この条件が十分でもあることを証明しました。すべての辺がひとつながりで、奇数の次数が2つ以下なら、その道は存在します。一周する道をつなぎ合わせていく彼の方法は、今でもその道を見つけるのに使われています。

ケーニヒスベルク(図では Koningsberga)の歴史的な鳥瞰図。プレゲル川と七つの橋の問題の中心である島が見える。1736年、レオンハルト・オイラーは各橋をちょうど一度ずつ渡る散歩が不可能であることを示し、グラフ理論が始まった。
ケーニヒスベルク(図では Koningsberga)の歴史的な鳥瞰図。プレゲル川と七つの橋の問題の中心である島が見える。1736年、レオンハルト・オイラーは各橋をちょうど一度ずつ渡る散歩が不可能であることを示し、グラフ理論が始まった。
レオンハルト・オイラーの肖像
レオンハルト・オイラーの肖像

距離、直径、補グラフ

2つの頂点の間の距離とは、それらを結ぶ道の辺の数の最小値で、直径はグラフ内の距離の最大値です。連結でないグラフでは直径は無限大です。ソーシャルネットワークの直径は小さく、これが「6次の隔たり」の考え方の背景にあります。グラフの補グラフは同じ頂点を持ち、つながっていなかった組をちょうど結びます。グラフとその補グラフのうち、少なくとも一方は必ず連結です。

試してみよう

プレイグラウンドを開くと、3色で塗り分けられたピーターセングラフが表示されます。「次数」をクリックして握手補題を確かめ、「二部グラフ」をクリックして奇数長の閉路を見たら、立方体を読み込んで2つの側が現れる様子を見てみましょう。家を読み込んで「オイラー路」をクリックすると、一筆書きをどこから始めればよいかがわかります。自分でグラフを描いて辺を1本ずつ加え、最短閉路が短くなり、直径が小さくなり、K4 の最後の辺が入ったときに彩色数が上がる様子を観察しましょう。

よくある質問

パス、トレイル、ウォークの違いは?

ウォーク(歩道)は辺で結ばれた頂点の並びなら何でもよく、頂点も辺も繰り返してかまいません。トレイル(小道)は頂点を繰り返してもよいものの辺は繰り返さないもので、オイラー路が同じ頂点を何度も通れるのはこのためです。パス(道)はどちらも繰り返しません。

四色定理とは?

辺を交差させずに紙に描けるグラフはどれも、4色以下で塗り分けられるという定理です。つまり、どんな地図も4色あれば足ります。1976年にケネス・アッペルとヴォルフガング・ハーケンがコンピュータの助けを借りて証明しました。このような方法で証明された初めての主要な定理です。

ハミルトン閉路とは?

すべての辺ではなく、すべての頂点をちょうど1回ずつ通る閉路です。オイラーの問題に似ていますが、簡単な判定法は知られていません。グラフがハミルトン閉路を持つかどうかの判定は NP 完全です。ピーターセングラフにはハミルトン路はありますが、ハミルトン閉路はありません。

グラフ理論はどこで使われていますか?

経路検索は道路のグラフを探索し、検索エンジンはリンクをもとに Web ページを順位付けし、コンパイラはグラフ彩色でプロセッサのレジスタを割り当て、時間割は衝突のグラフを彩色して重なりを避け、化学者は分子をグラフとして数え上げます。コンピュータや送電線、友人のネットワークもグラフとして研究されています。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

グラフ理論プレイグラウンドを開く