グラフ（数学）：構造、種類、応用

基本要素と用語

頂点はグラフの基本要素であり、辺は頂点間の接続を表す。ある辺で結ばれた二つの頂点は隣接しているという。頂点の次数は、その頂点に接続する辺の本数である（有向グラフでは入次数と出次数を区別する）。頂点の数はグラフの位数、辺の数はそのサイズと呼ばれることが多い。道とは、相異なる頂点の列を結ぶ辺の列であり、同じ頂点で始まり同じ頂点で終わる道は閉路である。連結性、連結成分、頂点間の距離は、グラフを記述するために用いられる基本的な性質の一部である。

主な種類と変種

グラフには、特定の用途に適したいくつかの標準的な形式がある。重要な区別には、次のようなものがある。

• 無向グラフと有向グラフ：無向辺には向きがなく、有向辺（弧）は一方の頂点から他方の頂点へ向かう。
• 単純グラフと多重グラフ：単純グラフでは任意の頂点対の間に存在できる辺は高々1本で、通常はループを含まない。多重グラフは複数の平行辺を含むことができ、場合によってはループ、すなわち頂点自身を結ぶ辺も含む。
• 重み付きグラフ：辺に、費用、長さ、容量、強度などを表す数値の重みを付与する。
• 特別なクラス：完全グラフ（すべての頂点対が辺で結ばれる）、二部グラフ（頂点が二つの集合に分かれ、辺は集合間にのみ存在する）、木（連結で閉路をもたないグラフ）、平面グラフ（辺の交差なしに描けるグラフ）がある。

歴史と発展

グラフに基づく考え方の起源は、一般に18世紀、レオンハルト・オイラーによるケーニヒスベルクの橋の問題の解法にさかのぼる。この解法は、頂点と辺によって問題をモデル化した初期の例であった。その後、この分野は組合せ論的なパズルの集まりから、数学および離散科学の体系的な一分野へと発展した。19世紀から20世紀にかけて、グラフ理論は代数学、位相幾何学、確率論の手法を取り入れ、理論的領域と応用領域の双方で中心的な位置を占めるようになった。

応用と例

グラフは多くの分野に広く存在する。コンピュータ科学では、データ構造、依存関係、制御フロー、状態遷移を表現し、最短路、全域木、マッチング、ネットワークフローのためのアルゴリズムは基礎的なものである。交通および物流では、道路、時刻表、経路選択をモデル化する。社会科学では、つながり、影響、コミュニティを捉え、化学では分子の結合関係を、生物学では神経ネットワークやタンパク質相互作用ネットワークを表す。有向グラフおよび重み付きグラフの変種により、容量、距離、非対称な関係をモデル化できる。

性質、問題、注目すべき事実

グラフ理論における重要な問いの多くは、存在や最適化に関するものである。たとえば、グラフはハミルトン閉路または完全マッチングを含むか、すべての頂点を結ぶ辺の最小集合、すなわち全域木は何か、ノード間で最も安価な経路をどう見つけるか、といった最短路問題がある。確立されたアルゴリズムによって効率よく解ける問題もあれば、計算量の面で困難な問題もある。グラフは視覚的表現と代数的表現の両方を可能にする。隣接リストや隣接行列は計算のために構造を符号化し、図示は接続性のパターンを明瞭にする。

区別と慣例

著者や分野によって採用する慣例は異なる。多重グラフでループを認める場合もあれば、認めない場合もある。また、次数を計算する際にループの寄与を2回数える場合もある。グラフは、頂点が名称によって区別される標識付きグラフの場合も、同型を除いてのみ考察される非標識グラフの場合もある。辺の列を記述するときは、順序を強調するために列という語がよく用いられる。アルゴリズムの文脈では、ウォーク、トレイル、道、閉路にはそれぞれ厳密な意味がある。現実世界の問題をグラフモデルへ翻訳する際には、こうした区別を理解することが重要である。

視覚的な例と特別な場合

よく用いられる例には、最大限の接続性を示す小さな完全グラフ、階層的なデータを表すための疎な木、平行接続やループを強調する多重グラフがある。グラフの描画では、閉路、関節点（それを除くと連結成分の数が増える頂点）、橋（それを除くとグラフが非連結になる辺）を強調できる。これらは、信頼性や脆弱性の分析に役立つ。