グラフ理論

**グラフ理論**（グラフりろん、）は、**ノード**（**節点**・**頂点、点**）の集合と**エッジ**（**枝**・**辺、線**）の集合で構成される**[[グラフ (離散数学)|グラフ]]**に関する数学の理論である。

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

## 概要
グラフによって、様々なものの関連を表すことができる。
frame|6つの節点と7つの辺から成るグラフの一例

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

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

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

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

グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。
:\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におけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である。

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

## 形式的な定義
### 有向グラフ
集合 ,  と、 の元（げん、要素）に、二つの  を元の対で対応させる写像
:f\colon\  E \to V \times V
の三つ組
:G := (f, V, E)

を**有向グラフ**という。 の元を  の**頂点**または**ノード**、 の元を  の**辺**または**弧**と呼ぶ。 となる  はループに対応し、 となる  は多重辺に対応する。

### 無向グラフ
 を  の冪集合とする。 の元に  の 部分集合を対応させる写像
:g\colon\  E \to \mathfrak{P}(V)

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

:G := (g, V, E)

を**無向グラフ**という。  の元を  の頂点、 の元を  の辺と呼ぶ。 の濃度が1となる  はループに対応し、 となる  は多重辺に対応する。

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

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

### 頂点と辺
**頂点**の集合は 、**辺**の集合は  で表す。グラフ  が先に与えられている場合には、頂点集合を 、辺集合を  と表すこともある。

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

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

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

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

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

### 部分グラフと拡大グラフ

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

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

### 次数と正則グラフ

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

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

### 完全グラフとクリーク

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

### その他の用語

## 応用

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

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

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

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

### 社会科学

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

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

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

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

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

## 問題と定理

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

## 脚注
### 出典と補足

## 参考文献
*
*(現在は丸善に移管)
*Reinhard Diestel (2010), Graphentheorie. Springer-Verlag, Vierte Auflage, 2010 Korrigierter Nachdruck 2012 Heidelberg xviii+355 Seiten, 129 Abbildungen September 2010 (2006, 2000, 1996) ISBN 978-3-642-14911-5 EUR 32,99.
*
*
*Rudolf Fritsch, Gerda Fritsch, translated by J.lie Peschke:The Four-Color Theorem (2012): History, Topological Foundations, and Idea of Proof, Springer; Softcover reprint of the original 1st edition 1998; ISBN 978-1-46127-254-0

## 関連文献
### 日本語の文献
* László Lovász: 「組合せ論演習 1：数え上げの手法」、東海大学出版会、ISBN 4-486-00996-7 (1988年3月14日). 
* László Lovász: 「組合せ論演習 2：グラフの構造」、東海大学出版会、ISBN 4-486-00997-5 (1988年3月28日).
* László Lovász: 「組合せ論演習 3：グラフの不変数」、東海大学出版会、ISBN 4-486-00998-3 (1988年年4月11日).
* László Lovász: 「組合せ論演習 4：集合論的グラフ理論」、東海大学出版会、ISBN 4-486-00999-1 (1988年4月11日).
* 
* 
*秋山仁 『グラフ理論最前線』朝倉書店（1998年8月） ISBN 978-4-254-11420-1.
*加納幹雄 『情報科学のためのグラフ理論』朝倉書店 (2001年2月)、ISBN 978-4-254-11424-9.
*
*
*鈴木晋一編著 『数学教材としてのグラフ理論』, 早稲田教育叢書 31, 学文社, （2012年3月）ISBN 978-4-76202-253-1
*ノラ・ハーツフィールド&ゲーハード・リンゲル著 鈴木晋一訳,『グラフ理論入門』,サイエンス社, （1992年6月1日）ISBN 978-4-78190-654-6
*ボロバシュ・ベーラ著 斎藤伸自, 西関隆夫訳,『グラフ理論入門』,培風館, （1983年4月30日）ISBN 978-4-56300-544-3
* リウ：「組合せ数学入門II」、共立出版（1972年）。
* R.J.ウィルソン：「グラフ理論入門」、近代科学社、ISBN 4-7649-0103-X (1985年3月20日）．
* 榎本彦衛：「グラフ学入門」、日本評論社(1988年)。
* 佐藤公男：「グラフ理論入門：C言語によるプログラムと応用問題」、日刊工業新聞社、ISBN 978-4-526-04361-1 (1999年4月15日)．
* ウィルソン：「グラフ理論入門」、近代科学社(2001年)。
* 惠羅博、土屋守正：「［増補改訂版］グラフ理論」、産業図書、ISBN 978-4-7828-5355-9 (2010年2月25日).
* R.ディーステル：「グラフ理論」、丸善出版、ISBN 978-4621061855（2012年6月5日）。
* 舩曳信夫、渡邊敏正、内田智之、神保秀司、中西透：「グラフ理論の基礎と応用」、共立出版、ISBN 978-4-320-12314-4 (2012年10月15日).
* 小林みどり：「あたらしいグラフ理論入門」、牧野書店、ISBN 978-4-434-17727-9 (2013年4月1日).
* 宮崎修一：「グラフ理論入門：基本とアルゴリズム」、森北出版、ISBN 978-4-627-85281-5（2015年6月）
* J.A.ボンディ、U.S.R.マーティ：「グラフ理論」、丸善出版、ISBN 978-4621307564 （2022年11月26日）。

### 日本語以外
*Berge, Claude (1958), Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II, Paris: Dunod. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.ISBN 978-0-48641-975-6.
*Lowell W. Beineke, Bjarne Toft, and Robin J. Wilson (2025): *Milestones in Graph Theory: A Century of Progress*, AMS/MAA, (SPECTRUM, v.108), ISBN 978-1-4704-6431-8.
*Chartrand, Gary (1985), Introductory Graph Theory, Dover, ISBN 0-486-24775-9.
*Leonhard Euler, Euler Complete Edition (Opera Omnia: Series 1, Volume 7, pp. 1 - 10)
*Hajnal Péter (2003), Gráfelmélet - Polygon jegyzet
*Harary, Frank (1969), Graph Theory, Reading, MA: Addison-Wesley.
*Harary, Frank; Palmer, Edgar M. (1973), Graphical Enumeration, New York, NY: Academic Press.
*Jeremy Kepner and John Gilbert (EDs) (2011): *Graph Algorithms in the Language of Linear Algebra*, SIAM, ISBN 978-0-89871-990-1.
*Lovász László (2008), Kombinatorikai problémák és feladatok, Typotex Kiadó, ISBN 978-963-9664-93-7.
*Manfred Nitzsche (2004), Graphen für Einsteiger, Rund um das Haus vom Nikolaus. XII, 233 S. Br. € 22,90 ISBN 3-528-03215-4
*Peter Gritzmann, René Brandenberg (2003) Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin - Heidelberg (2.Aufl.). ISBN 3-540-00045-3
*William Thomas Tutte (2001), Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3.

## 関連項目

*グラフ (離散数学)
*ラムゼー理論
*マトロイド
*スモール・ワールド現象
*グラフ (データ構造)
*ネットワーク理論
*存在グラフ
*素集合データ構造
*名称のあるグラフのギャラリー
*全域木
*平面グラフ
*応用数学

## 外部リンク

*A searchable database of small connected graphs
*Concise, annotated list of graph theory resources for researchers
*Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
*Graph Theory, by Reinhard Diestel
*Graph Theory Software - tools to teach and learn graph theory
*Graph theory tutorial
*Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs (2006) by Hartmann and Weigt
*rocs - a graph theory IDE
*The Social Life of Routers - non-technical paper discussing graphs of people and computers