グラフ (離散数学)

数学のグラフ理論におけるグラフとは数学的構造の一つ。対象の集合で、対象の一部が相互に何らかの脈絡で「関係している」ようなものをいう。ここで対象とは頂点と呼ばれる抽象物であり、互いに関係のある頂点の対は辺と呼ばれる。一般的に、グラフは点または丸で表した頂点の集合に直線または曲線で辺を描き加えたダイアグラムで表現される。グラフは離散数学の研究対象の一つである。

辺には無向と有向の場合がある。例えば頂点をパーティ参加者として、2人が握手するとその間に辺が結ばれるとする場合、握手はお互い対等で行うものなので無向な辺といえる。対照的に、お金の貸し借り関係を辺とした場合、どちらか一方にのみ返済義務があるので有向な辺といえる。前者をグラフにしたものは無向グラフ  と呼ばれ、後者のグラフは有向グラフ  と呼ばれる。

グラフはグラフ理論における基本的な研究対象である。「グラフ」という言葉は、1878年にジェームズ・ジョセフ・シルベスターによってこの意味で最初に使用された。

1. 定義
-----

グラフ理論における定義はさまざまである。以下、グラフや関連する数学的構造の定義で基本的なものを幾つか挙げる。

1.1. グラフ
--------

グラフBenderとは順序対 1=//G// = }} である。ここで V}} は頂点  と呼ばれる元の集合、E}} は頂点の対の集合でありその元は辺  と呼ばれる。

辺 //x//, //y//}}} に含まれる頂点 //x//}}と//y//}} は、その辺の「端点」と呼ばれる。辺は頂点 //x//}} と //y//}} を「結び 」、//x//}} や //y//}} に「接続する 」と言い表す。頂点がいかなる辺にも含まれないこともあり、その場合は他のどの頂点とも結ばれていない。

頂点をそれ自身と結ぶ辺である「ループ」を許すグラフもある。このように一般化されたグラフは「ループ付きグラフ 」と呼ばれる。文脈からループを許すことが自明な場合は単にグラフと呼んだりもする。

「多重グラフmultigraph}}」とは、2つの頂点間に複数の辺がある「多重辺」を許すように一般化したグラフである。一部のテキストでは、多重グラフのことを単にグラフと呼んでいたりもするBender。多重辺を許すにあたり、上述の辺に関する定義を頂点対の集合ではなく、頂点対の多重集合に変更する必要がある。

一般に、頂点 V}} の集合は有限集合と想定されており、これはまた辺の集合も有限集合だということも意味する。時には「無限グラフInfinite graph}}」が考慮されることもあるが、殆どの場合は特別な種類の二項関係だと見なされる、というのも有限グラフで得られた結果の大部分が無限のケースに拡張できなかったり、だいぶ異なる証明を必要とするためである。

空グラフとは、頂点の集合が空であるグラフをいう。頂点の数 absをグラフの「位数」といい、辺の数 absをグラフの「サイズ」という。ただし、アルゴリズムの計算複雑性を表現するなど一部の文脈では、サイズが absである。頂点の次数とは頂点に接続する辺の数のことで、ループ付きグラフの場合ループは2回カウントされる。

位数 //n//}} のグラフにおける、各頂点の最大次数は //n// − 1}}、辺の最大数は //n///2}}となる。

グラフの辺は「隣接関係」と呼ばれる頂点間の対称関係を定義する。具体的には、mset が辺であれば、2つの頂点 //x//}} と //y//}} は「隣接している 」という。

一つのグラフは の正方行列である隣接行列 によって完全に指定できる。 は頂点 //i//}} と頂点 //j//}} をつなぐ接続の数を指定する。単純グラフの場合、であり、0と1が非接続と接続をそれぞれ表す。またこのとき である。ループ付きグラフは、一部または全ての が正の整数になり、多重グラフは一部または全ての が正の整数になる。無向グラフの隣接行列は対称行列となる 。

1.2. 有向グラフ
----------

有向グラフ  は、辺に向きがあるグラフである。

限定的だが非常に一般的な意味においてBender、有向グラフは以下の条件を満たす対として定義される。

は、頂点の集合
は辺の集合で、辺は頂点の順序対である。つまり1辺が異なる2頂点と関連している。曖昧さを避けるため、この種類のグラフは厳密に「単純有向グラフ 」と呼ぶ場合もある。

辺 は から の向きを表し、頂点 と はその辺の「端点」であるが、 は辺の「始点 」そして は辺の「終点 」という。辺は と を「結び」、 と に「接続する」と表現される。頂点は、グラフ内にあっても辺を持たない場合もある。辺 は の「逆向辺 」と呼ばれる。「多重辺」は、上述の定義だと許されないが、同じ始点と終点を持つ辺が複数あるものを言う。

多重辺を許す条件のより一般的な意味でBender、有向グラフは以下によって構成される順序三つ組 として定義される。

は、頂点の集合
は、辺の集合
は全ての辺を頂点の順序対に写す写像「接続関数 」である。曖昧さを避けるため、この種類のグラフは厳密に「多重有向グラフ」と呼ぶ場合もある。

「ループ」は始点と終点が同一な辺である。上述の2種類の定義においては有向グラフはループを持つことができない、なぜなら、辺 の定義に の条件があるので、頂点 と自分自身を結ぶループは辺の定義を満たさないためである。 そのためループを許すには定義を拡張させる必要がある。有向単純グラフに対しては の定義を と修正し、有向多重グラフに対しては の定義を と修正することになる。曖昧さを避けるため、これらの種類のグラフは厳密にそれぞれ「ループを許す単純有向グラフ 」そして「ループを許す多重有向グラフ」と呼ばれる場合もある。

ループを許す単純有向グラフ において、辺は の頂点に関する自己関係を成す。これを と表し、 の「隣接関係」と呼ぶ。具体的には、各辺 について、その端点 と は互いに「隣接する」と言い、 と表記される。

1.3. 混合グラフ
----------

「混合グラフ  」とは、一部の辺が有向、一部の辺が無向であるグラフ。混合単純グラフは順序三つ組 1=//G// = }} である。混合複合グラフは 1=//G// = }} の五つ組で、//V//, //E// , //A// , //ϕ////E// ,//ϕ////A// は上述にて定義したものである。有向グラフと無向グラフは混合グラフの特殊なケースである。

1.4. 重み付きグラフ
------------

「重み付きグラフ 」もしくは「ネットワーク 」とは、各辺に数値が割り当てられているグラフ 。この重みとは、扱う問題次第で例えば料金や距離や所要時間だったりする。こうしたグラフは、例えば巡回セールスマン問題のような最短経路問題など、多くの文脈で作成される。

2. グラフの種類
---------

2.1. Oriented graph
-------------------

「Oriented graph」の定義の1つは、 と のうち高々1つがグラフの辺となりうる有向グラフ。すなわち、単純無向グラフに向き付け  を行うことで形成されうる有向グラフである。

一部の著者は「有向グラフ」と同じ意味で「Oriented graph」を使っている。与えられた無向グラフや多重グラフへの任意の向き付けという意味で「Oriented graph」を使っている著者もいる。

2.2. 正則グラフ
----------

「正則グラフ 」は各頂点がいずれも同じ数の頂点と隣接しているグラフ。すなわち頂点の次数が全て等しいグラフ。次数が k}} の正則グラフを「k}}-正則グラフ」または「次数 k}} の正則グラフ」と呼ぶ。

2.3. 完全グラフ
----------

「完全グラフ 」は、どの2頂点間にも1本の辺があるグラフ。完全グラフにはありうる全ての辺が含まれている。

2.4. 有限グラフ
----------

「有限グラフ 」は、頂点集合と辺集合が有限集合のグラフ。それ以外のものは「無限グラフ」と呼ばれる。

グラフ理論ではほとんど一般的に、議論されるグラフは有限グラフであることを暗に前提としている。グラフが無限の場合、通常はそれと明記されている。

2.5. 連結グラフ
----------

無向グラフでは、頂点 x}} から y}} まで道がたどれる場合、非順序対 が「連結している 」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。

「連結グラフ」は、グラフにある任意の頂点の非順序対が連結している無向グラフである。それ以外の場合は非連結グラフと呼ばれる。

有向グラフでは、x}} から y}} まで有向道がたどれる場合に、頂点の順序対 が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後なら x}} から y}} までの無向道がたどれる場合は「弱連結」であると言う。それ以外の場合、その順序対は非連結と呼ばれる。

強連結グラフは、グラフにある任意の頂点の順序対が強連結している有向グラフである。それ以外で、グラフにある任意の頂点の順序対が弱連結している場合は、弱連結グラフという。それ以外のものは非連結グラフという。

k}}-頂点連結グラフやk}}-辺連結グラフは、取り除いた場合にグラフが非連結となる //k//−1}} 個の頂点集合が存在しないグラフ である。k}}-頂点連結グラフは単に「k}}-連結グラフ」と言うことも多い。

2.6. 2部グラフ
----------

「2部グラフ 」とは、頂点集合を と の2集合に分割し、 内で任意の2頂点が辺を共有することがなく、 内でも任意の2頂点が辺を共有することがないようにできる単純グラフのこと。言い換えるなら、彩色数2となるグラフ。

完全2部グラフにおいて、頂点集合は2つの素集合 と の合併  であり、 内にある全ての頂点が 内にある全ての頂点と隣接しているのだが、素集合の 内や 内で完結する辺がないものをいう。

2.7. パスグラフ
----------

位数 の「パスグラフ 」とは、頂点の集合を のように順序付けすることで、辺の集合が のようになりうるグラフ。一本道のようなダイアグラムとなる。パスグラフは、2頂点を除き全ての頂点の次数が2、残る2頂点の次数が 1という特徴を持つ連結グラフとも言える。他のグラフの部分グラフとしてパスグラフを作った場合、それは元のグラフにおける道にあたる。

2.8. 平面的グラフ
-----------

「平面的グラフ 」とは、辺同士が一切交差することなく平面上に頂点と辺を描くことができるグラフである。

2.9. 閉路グラフ
----------

位数 の「閉路グラフ 」とは、頂点の集合を のように順序付けすることで、辺の集合が に を付け加えたものとなりうるグラフ。ダイアグラムは閉路状になる。閉路グラフはあらゆる頂点の次数が2の連結グラフという特徴がある。他のグラフの部分グラフとして閉路グラフを作った場合、元のグラフにおける閉路にあたる。

2.10. 木
-------

「木 」とは、あらゆる頂点の対が厳密に1つの道で連結されている無向グラフ。あるいは連結で閉路のない無向グラフとも言える。

「森 」とは、あらゆる頂点の対が高々1つの道で連結されている無向グラフ。あるいは閉路がない無向グラフ、または複数の木の交わりを持たない和 でもある。

2.11. 有向木
---------

「有向木 」とは、有向グラフの一種であって、その有向辺をすべて無向辺に置き換えたものが木グラフになるような有向非巡回グラフである。

同様に、「有向森」は、その有向辺をすべて無向辺に置き換えたものが森グラフになるような有向非巡回グラフである。

2.12. 高度なグラフ
------------

より高度なグラフの種類を幾つか挙げると、以下のものがある。

ピーターセングラフとその一般化
パーフェクトグラフ
補グラフ
弦グラフ
大きなグラフ自己同型群Graph automorphism}}を持つその他のグラフ
強正則グラフとその一般化である距離正則グラフ

3. グラフ属性
--------

グラフの2辺が共通の頂点を共有する場合は、2辺が「隣接する 」という。有向グラフの2辺は、1番目の終点が2番目の始点になっている場合に「連続する 」という。同様に、2頂点が1辺を共有する場合は、2頂点が「隣接」するは蛇足説明なので割愛-->。

全てのグラフの圏はコンマ圏である。ここで は、集合 を に対応付ける関手である。

4. 用例
-----

右のダイアグラムは次のグラフを模式的に表現したものである。
頂点
辺
コンピュータサイエンスでは、有向グラフが知識や有限状態機械ほか多くの離散構造を表すのに使われている。
集合 上の二項関係 は有向グラフを定義する。 の元 は、 である場合にのみ の元 の直前元  となる必要十分条件を満たす。
有向グラフは、あるユーザーが別の人をフォローするTwitter等の情報ネットワークを図に表すことができる。
とりわけ正則的な有向グラフの例としては、有限生成群のケイリーグラフやシュライアーコセットグラフなどが挙げられる。
圏論では、全ての小さい圏が台有向多重グラフ  を持っており、そこでの頂点は元の圏の対象、辺は元の圏の矢印である。圏論の言葉では、それを小さい圏の圏から箙の圏への忘却関手forgetful functor}}がある、と表現する。

5. グラフ操作
--------

初期のグラフから新しいグラフを生成する数学的操作が幾つかあり、次のように分類される場合がある。

「単項演算 」では、1つの初期グラフから以下のような新たグラフを生み出す。
辺の縮約edge contraction}}-ある1辺を縮めて両端点を1頂点にする操作
ライングラフ
双対グラフ
補グラフ-頂点集合はそのままで隣接関係を逆にする操作
グラフ書換え
「二項演算 」では、2つの初期グラフから以下のような新たグラフを生み出す。
グラフ同士の交わりを持たない和
グラフ同士のデカルト積
グラフ同士のテンソル積
グラフ同士の強い積
グラフ同士の辞書積
直並列グラフ

6. 一般化
------

ハイパーグラフでは、1つの辺が2つ以上の頂点と接合可能である。

無向グラフは、1次元単体と 0次元単体からなる単体複体と見なすことも可能である。複体はより高次元の単体を容認しうるので、それ自体がグラフの一般化である。

全てのグラフはマトロイドを持ちうる。

モデル理論においてグラフは単なる構造である。しかしその場合、辺の数に制限はなく何らかの基数になりうる。

計算生物学において、パワーグラフ分析は無向グラフの代替表現としてパワーグラフを導入している。

地理情報システム  では、地理的ネットワークがグラフを基に厳密にモデル構築され、グラフ理論から多くの概念を借用して道路網や電力系統の空間解析を行っている。

7. 関連項目
-------

グラフ理論
グラフ 
名称のあるグラフのギャラリー
ネットワーク理論

8. 脚注
-----

8.1. 出典
-------

8.2. 参考文献
---------

陳慰・和田幸一『[1]』森北出版、2014年11月7日
加納幹雄『[2]』森北出版、2013年12月27日
「[3]」-英語版wikiの翻訳時に参照した専門用語一覧

9. 外部リンク
--------