グラフ理論

グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。

グラフ（データ構造）などの応用がある。

概要

グラフによって、様々なものの関連を表すことができる。

6つの節点と7つの辺から成るグラフの一例

例えば、鉄道や路線バス等の路線図を考える際には、駅（節点）がどのように路線（辺）で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。

したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば実際の地理上とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。

このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり^[1]、グラフがもつ様々な性質を探求するのがグラフ理論である。

つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフ、または、ダイグラフという。矢印のないグラフは、無向グラフという。

グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。

${\displaystyle {\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$

グラフの例

→詳細は「グラフ (離散数学)」を参照

日常的な問題や工学的問題の多くをグラフとして考えることができる。

• 路線図: 前節のとおり。
• 電気回路: 回路図を書く場合、実際のリード線どおりの形状に図を描いたりはしない。この場合も、「接点がどうつながっているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。
• WWWの構造: WWWにおけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である^[2]。

起源

グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示した^[3][4]のが起源のひとつとされる^[5]。この問題は、一筆書きと深く関連している^[6]。

形式的な定義

有向グラフ

集合 V, E と、E の元（げん、要素）に、二つの V を元の対で対応させる写像

${\displaystyle f\colon \ E\to V\times V}$

の三つ組

${\displaystyle G:=(f,V,E)}$

を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。f(e) = (v,v) となる e ∈ E はループに対応し、f(a) = f(b) となる a, b ∈ E は多重辺に対応する。

無向グラフ

𝔓(V) を V の冪集合とする。E の元に V の 部分集合を対応させる写像

${\displaystyle g\colon \ E\to {\mathfrak {P}}(V)}$

があって、E の任意の元 e について、e の像 g(e) の濃度が1または2であるとき、三つ組

${\displaystyle G:=(g,V,E)}$

を無向グラフという^[7]。 V の元を G の頂点、E の元を G の辺と呼ぶ。g(e) の濃度が1となる e ∈ E はループに対応し、f(a) = f(b) となる a, b ∈ E は多重辺に対応する。

単純グラフに限って言えば、E を最初からある集合の部分集合と考え、写像を用いずにグラフを定義することもできる：有向グラフでは、E を V × V の部分集合、無向グラフでは、E を 𝔓(V) の部分集合で、2つの元の集合だけからなるものとすればよい。

用語

以下では単にグラフといった時には無向グラフを指す。

頂点と辺

頂点の集合は V、辺の集合は E で表す。グラフ G が先に与えられている場合には、頂点集合を V(G)、辺集合を E(G) と表すこともある^[8]。

数学以外の分野では、頂点を節点、辺を枝と呼ぶことが多い。辺を弧やリンクと呼ぶこともある。

重み付きグラフ

グラフの辺に重み（コスト）が付いているグラフを、重み付きグラフと呼ぶ^[9]。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる（フローネットワーク, ベイジアンネットワーク, ニューラルネットワークなど）。

接合と隣接

辺 e の両端の点を端点といい、端点は辺 e に接合（または接続）しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接しているという^[8]。

距離と直径

2頂点間（隣接している必要はない）を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフ G の最大頂点間距離を直径と呼び、diam(G) と表す^[10]。

ループと多重グラフ

ある辺の両端点が等しいとき、ループ（自己ループ）という。また、2頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを単純グラフといい、ループや多重辺を含むグラフのことを多重グラフという^[11]。

部分グラフと拡大グラフ

縮約の図示

2つのグラフ G と G' について、G' の頂点集合と辺集合が共に G の頂点集合と辺集合の部分集合になっているとき、G' は G の部分グラフである、または G は G' の拡大グラフであるといい、G' ⊂ G と表す^[8]。特に、G と G' の頂点集合が等しいとき、G' は G の全域部分グラフであるという。また、G の頂点集合 V の部分集合 U を取り出して、両端点が U に属する全ての辺を辺集合とする G の部分グラフ G[U] を、誘導部分グラフという。グラフ G からある辺 e を取り除き、その辺の両端点を一つの頂点にまとめることを（辺の）縮約といい、縮約の結果得られるグラフを G/e と表す。

なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」がある^[12][13]。このため、誘導部分グラフのことを生成部分グラフということもある^[14]。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。

次数と正則グラフ

→「次数 (グラフ理論)」も参照

3-正則グラフの例

頂点 v に接続する枝の数を次数といい、d(v) で表す。有向グラフにおいては、v に入ってくる辺数のことを入次数、v から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶ^[15]。任意の頂点 v について、d(v) = k が成り立つとき、k-正則という。k-正則なグラフのことを k-正則グラフという。グラフ G が持つ頂点の次数の最小値を δ(G)、最大値を Δ(G) で表す。また、次数 0 の頂点のことを孤立点という。

道と閉路

隣接している頂点同士をたどった v₀, e₀, v₁, e₁, ... , e_n−1, v_n の系列を長さ n の歩道（鎖・ウォーク）という。辺の重複を許さない歩道を路（小径・トレイル）という^[16]。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道（パス）、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路（回路・循環 ・サーキット、サイクル）、始点と終点が同じ道（つまり e₁, e₂, ... , e_n, e₁ という路で e_i が相異なるもの）のことを閉道（サイクル）という^[17]。

完全グラフとクリーク

3頂点からなる完全グラフ：三角形

任意の 2 頂点間に枝があるグラフのことを完全グラフ（完備グラフ）という^[8][18]。n 頂点の完全グラフは、K_n で表す。K₃ は三角形と呼ばれる。また、完全グラフになる誘導部分グラフのことをクリークという。大きさ（サイズ） n のクリークを含むグラフは「n-クリークである」という。辺をもつグラフは必ず2頂点の完全グラフを含むので 2-クリークである。また n-クリークであって、直径が n 未満となるグラフを n-クランという。

その他の用語

• オイラー路（オイラー閉路・オイラーグラフ）
• ハミルトン路（ハミルトン閉路・ハミルトングラフ）
• 木 （根つき木・森）
  • 全域木
  • シュタイナー木
• 直径
• カット
• 2部グラフ （n 部グラフ・彩色）
• 同型グラフ
• 連結グラフ （連結成分・連結度）
• 平面グラフ （平面的グラフ）
• 隣接行列
• 接続行列
• 次数行列
• 対称グラフ
• マッチング
• 閉路グラフ
• 有向非巡回グラフ
• 独立集合
• ランダム・グラフ（英語版）
• マイナー (グラフ理論)（英語版）
• グラフ代数（英語版）
• 空グラフ
• 量子グラフ
• （有向グラフの）強連結成分分解
• グラフのゼータ関数
• ダルメジ・メンデルゾーン分解(Dulmage–Mendelsohn decomposition （DM 分解）)
• トポロジカルソート

応用

• デッドロックの検出
• ガベージコレクション
• ファイルシステム
• ニューラルネットワーク
• ペトリネット
• ループ量子重力理論
• スケジューリング問題
• 意味ネットワーク
• パーコレーション
• 複合進化（英語版）
• PERT
• 全域木
• タングル
• 結び目理論

2013年の夏の1カ月の間に異なる言語版のWikipedia（頂点）に貢献したWikipedia編集者（辺）によって形成されたネットワークグラフ^[19]。

グラフは物理学的、生物学的^[20][21]、社会的、および情報システムにおける多くの種類の関係と過程をモデル化するために使うことができる。多くの現実的問題はグラフによって表すことができる。現実世界のシステムへの応用を強調する時には、「ネットワーク」という用語がグラフを意味するために定義されることがある。このグラフでは、属性（例えば名前）が頂点および辺と関連付けられる。現実世界のシステムをネットワークとして表現し理解する主題はネットワーク科学（英語版）と呼ばれる。

計算機科学

計算機科学において、グラフはコミュニケーション、データ編成、計算装置、計算の流れ等のネットワークを表すために使われる。例えば、ウェブサイトのリンク構造は有向グラフとして表すことができる。ここでは、頂点がウェブページを表し、有向辺があるページから別のページへのリンクを表す。同様のアプローチを、ソーシャルメディア^[22]、旅行、生物学、コンピュータチップ設計、神経変性疾患の進行のマッピング^[23][24]、そしてその他多くの分野における課題について取ることができる。したがって、グラフを取り扱うためのアルゴリズムの開発が計算機科学における主要な興味である。グラフの変換（英語版）はグラフ書換え系によってしばしば定式化され、表現される。グラフ変換系と相補的なグラフの規則に基づくメモリー内操作に注目したシステムが、グラフ構造を持つデータのトランザクションセーフで永続的な格納と問い合わせに対応したグラフデータベース（英語版）である。 数値計算の分野では、疎行列を係数とする連立1次方程式を消去法により計算して解く際に、行列の非零構造をグラフと対応づけて消去の順序をうまく選ぶことで、消去法計算の過程で発生する非零要素の数をなるべく抑える方法などが多く研究されてきた。

言語学

様々な形式のグラフ理論的手法は言語学において特に有用であることが証明されている。これは、自然言語がしばしば離散構造へとよく適しているためである。伝統的に、統語論と合成意味論は木構造に従い、それらの表現力は、階層的グラフによってモデル化される構成性の原理（英語版）に密接に関係する。主辞駆動句構造文法といったより現代的な手法は型付き素性構造（これは有向非巡回グラフである）を用いて自然言語の構文をモデル化する。語彙意味論内、特に計算機へ応用としては、単語の意味のモデル化は、与えられた単語が関連する単語の観点から理解される時により容易である。したがって意味ネットワークは計算言語学において重要である。今で、哲学（例えば、格子グラフ（英語版）を用いる最適性理論）や形態論（例えば有限状態トランスデューサ（英語版）を用いる有限状態形態論）におけるその他の手法は、グラフとしての言語の解析において一般的である。実際、この数学の分野の言語学への有用性は、TextGraphs^[25]、WordNetやVerbNet（英語版）といった様々な "Net" プロジェクトのような組織を生んできた。

物理学および化学

グラフ理論は化学および物理学において分子を研究するためにも使われる。凝縮系物理学では、シミュレーションした複雑な原子構造の3次元構造は、原子のトポロジーに関連したグラフ理論的性質に関する統計量を集めることによって定量的に研究することができる。また、ファインマンの計算のグラフと規則は、理解したい実験的数字と密接に関係した形式で量子場理論を要約する^[26]。化学では、グラフは分子についての自然な模型を作り、ここでは頂点が原子、辺が結合を表わす。このアプローチは分子構造の計算処理（分子エディタからデータベース探索まで）において特に使われる。統計物理学では、グラフは系の相互作用している部位間の局所的つながりや、こういった系における物理的過程のダイナミクスを表わすことができる。同様に、計算論的神経科学では、グラフは様々な認知過程を生じさせるために相互作用する脳領域間の機能的結合を表わすために使うことができる。ここでは、頂点が脳の異なる領域を表わし、辺がそれらの領域間の結合を表わす。グラフ理論は電気回路網の電気的モデリングにおいて重要な役割を果たす。ここで、重みはネットワーク構造の電気的性質を得るために有線部分の抵抗と関連付けられる^[27]。グラフは多孔質材料のミクロスケールチャネルを表わすらために使うこともできる。ここでは、頂点が孔を表わし、辺が孔間をつなぐより小さなチャネルを表わす。化学グラフ理論は分子をモデル化する手段として分子グラフを使用する。

社会科学

社会学におけるグラフ理論: モレノのソシオグラム（英語版）（1953年）^[28]。

グラフ理論は社会学においても、例えば、特に社会ネットワーク分析（英語版）ソフトウェアを使って俳優の名声を見積ったり（英語版）、うわさの広がりを調査したりする手段として広く使われている。社会ネットワークの傘の下に、多くの異なる種類のグラフがある^[29]。知り合い関係グラフと友情関係グラフは人々が知り合いかどうかを記述する。影響グラフは特定の人々が他者の振る舞いに影響するかどうかをモデル化する。最後に、協調グラフは2人の人物が、映画で一緒に演技するといったある特定のやり方で協力するかどうかをモデル化する。

生物学

同じく、グラフ理論は生物学および保全の取り組みにおいて有用である。ここでは、頂点が特定の種が存在（または生息）する地域を表わすことができ、辺は地域間の移動経路または移動を表わす。この情報は、繁殖パターンを見る時や、病気や寄生虫の広がり、移動が他の種にどのように影響しうるかを追跡するために重要である。

グラフ理論はコネクトミクスでも使われる^[21]。神経系はグラフとして見ることができる。ここで、節点はニューロンであり、辺はニューロン間のつながりである。

数学

数学では、グラフは幾何学ならびに結び目理論といったトポロジーの特定の分野において有用である。代数的グラフ理論は群論と密接なつながりを持つ。代数的グラフ理論は動的系や複雑性を含む多くの分野に応用されている。

その他

グラフ構造は、グラフのそれぞれの辺に重みを割り当てることによって拡張することができる。重み付きグラフは、対ごとのつながりが何らかの数値を持つ構造を表わすために使われる。例えば、グラフが道路網を表わすとすると、重みは各道路の長さを表わすことができるだろう。それぞれの辺に関連した複数の重み（距離、旅行時間、金銭的コストなど）が存在するかもしれない。このような重み付きグラフはGPSおよび飛行時間と費用を比較する旅行計画探索エンジンをプログラムするために一般的に使われる。

問題と定理

• 最短経路問題
• ハミルトン閉路問題
• 巡回セールスマン問題
• 中国人郵便配達問題
• 最小全域木問題
• 最大クリーク問題
• 頂点被覆問題
• 最大流最小カット定理
• グラフ彩色問題 - 四色定理^[30]
• ワーシャル-フロイド法 (Warshall-Floyd 問題)
• 次数直径問題
• 安定結婚問題
• グラフ・マイナー定理
• グラフサンドウィッチ問題（英語版）
• 小石運動問題（英語版）

備考

2022年から日本で導入される高等学校新学習指導要領の数学C（公式配布されるのは2024年4月）には「図、表、統計グラフ、離散グラフ及び行列などを用いて、日常の事象や社会の事象などを数学的に表現し、考察すること」とあり、日本では初めてグラフ理論にかかわる分野が高等学校の数学教科書に掲載される予定である^[31]。ただし、その分野を入試に出題する大学は殆どない^[32]。