グラフ理論

グラフ理論（グラフりろん、英: graph theory）は、ノード（節点^{[英 1]}・頂点^{[英 2]}）の集合とエッジ（枝・辺^{[英 3]}）の集合で構成されるグラフ^{[英 4]}に関する数学の理論である。グラフ (データ構造) などの応用がある。

概要

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

6 つのノードと 7 つのエッジから成るグラフの一例

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

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

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

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

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

displaystyle beginpmatrix0&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\endpmatrix

グラフの例

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

路線図：前節のとおり。

電気回路：回路図を書く場合、実際のリード線どおりの形状に図を描いたりはしない。この場合も、「接点がどうつながっているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。

WWWの構造：WWWにおけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である^[2]。

起源

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

形式的な定義

有向グラフ

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

fcolon Eto Vtimes V

の三つ組

G:=(f,V,E)

を有向グラフという。V の元を G の頂点^{[英 2]}またはノード^{[英 1]}、E の元を G の辺^{[英 3]}または弧^{[英 8]}と呼ぶ。

無向グラフ

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

gcolon Eto P(V)

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

G:=(g,V,E)

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

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

用語

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

頂点と辺

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

数学以外の分野では、頂点を節点^{[英 1]}、辺を枝と呼ぶことが多い。辺を弧^{[英 8]}やリンク^{[英 9]}と呼ぶこともある。

重み付きグラフ

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

接合と隣接

辺 $e$ の両端の点を端点^{[英 11]}といい、端点は辺 $e$ に接合 (または、接続) しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接している^{[英 12]}という^[8]。

距離と直径

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

ループと多重グラフ

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

部分グラフと拡大グラフ

縮約の図示

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

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

次数と正則グラフ

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

3-正則グラフの例

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

道と閉路

隣接している頂点同士をたどった $displaystyle v_0,~e_1,~v_1,~e_2,...,~e_n-1,~v_n$ の系列を長さ n (≥ 0) の歩道^{[英 23]}（鎖・ウォーク）という。辺の重複を許さない歩道を路^{[英 24]}（小径・トレイル）という^[16]。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道^{[英 25]}（パス）、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路（回路・循環・サーキット、サイクル^{[英 26]}）、始点と終点が同じ道（つまり $e_1,~e_2,~...,~e_n,~e_1$ という路で $e_i~$ が相異なるもの）のことを閉道（サイクル）という^[17]。

完全グラフとクリーク

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

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

その他の用語

オイラー路（オイラー閉路・オイラーグラフ）

ハミルトン路（ハミルトン閉路・ハミルトングラフ）

木（根つき木・森）
- 全域木
- シュタイナー木

直径

カット

2部グラフ（n 部グラフ・彩色）

同型グラフ

連結グラフ（連結成分・連結度）

平面グラフ（平面的グラフ）

隣接行列（接続行列）

対称グラフ

マッチング

閉路グラフ

有向非巡回グラフ

独立集合

ランダム・グラフ（英語版）

マイナー（グラフ理論）（英語版）

グラフ代数（英語版）

空グラフ

量子グラフ（英語版）

問題と定理

最短経路問題

ハミルトン閉路問題

巡回セールスマン問題

中国人郵便配達問題

最小全域木問題

最大クリーク問題

頂点被覆問題

最大流最小カット定理

グラフ彩色問題 - 四色定理^[19]

ワーシャル-フロイド法 (Warshall-Floyd 問題)

次数直径問題

安定結婚問題

グラフ・マイナー定理（英語版）

グラフサンドウィッチ問題（英語版）

小石運動問題（英語版）

応用

デッドロックの検出

ガベージコレクション

ファイルシステム

ニューラルネットワーク

ペトリネット

ループ量子重力理論

スケジューリング問題

意味ネットワーク

パーコレーション

複合進化（英語版）

PERT

備考

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

脚注

出典と補足

^ 概念

^ ハイパーリンク

^ (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140.　Konigsberg Bridge problemを参照。

^ Diestel, p. 20

^ グラフ理論の歴史を扱っているBiggs et al. (1998)にオイラーの論文の英訳を含む節がある。

^ 詳しくは、一筆書きの項を参照。

^ 無向グラフと有向グラフ

^ ^a^b^c^dディーステル 2000, 1.1 グラフ

^ Bondy & Murty 2008, p. 50.

^ ディーステル 2000, p. 10.

^ 多重グラフ

^ ベルジュ「グラフの理論I」p.8.

^ ディーステル, 2000

^ 茨木「アルゴリズムとデータ構造」

^ ディーステル 2000, p. 6.

^ Bondy & Murty 2008, p. 80.

^ 閉路

^ Diestel, p. 115

^ Fritsch (2012), p. 99

^ “高校「新学習指導要領」は教え方改革 - 旺文社教育情報センター”. eic.obunsha.co.jp. 2019年2月1日閲覧。

英語による専門用語

^ ^a^b^cnode

^ ^a^b^cvertex

^ ^a^b^cedge

^ graph

^ directed graph

^ digraph

^ undirected graph

^ ^a^barc

^ link

^ weighted graph

^ endpoint

^ adjacent

^ length

^ distance

^ diameter

^ loop

^ simple graph

^ subgraph

^ spanning subgraph

^ induced subgraph

^ contraction

^ k-regular

^ walk

^ trail

^ path

^ cycle

^ complete graph

参考文献

ベルジュ, C.『グラフの理論I』伊理正夫・伊理由美・岩坪秀一・小林欣吾・佐藤創・星守訳、サイエンス社、1976年。.mw-parser-output cite.citationfont-style:inherit.mw-parser-output .citation qquotes:"""""""'""'".mw-parser-output .citation .cs1-lock-free abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .citation .cs1-lock-subscription abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registrationcolor:#555.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration spanborder-bottom:1px dotted;cursor:help.mw-parser-output .cs1-ws-icon abackground:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center.mw-parser-output code.cs1-codecolor:inherit;background:inherit;border:inherit;padding:inherit.mw-parser-output .cs1-hidden-errordisplay:none;font-size:100%.mw-parser-output .cs1-visible-errorfont-size:100%.mw-parser-output .cs1-maintdisplay:none;color:#33aa33;margin-left:0.3em.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-formatfont-size:95%.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-leftpadding-left:0.2em.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-rightpadding-right:0.2em
ISBN 4-7819-0111-5。

ディーステル, ラインハルト『グラフ理論』根上生也・太田克弘訳、シュプリンガー・フェアラーク東京、2000年、原書第2版。
ISBN 978-4-431-70876-6。(現在は丸善に移管)

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.

Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. (1998). Graph theory 1736–1936 (Reprint with corrections ed.). Oxford University Press.
ISBN 0-19-853916-9. MR
0879117.
Zbl 0904.05001. https://books.google.com/books?id=XqYTk0sXmpoC.

Bondy, J. A.; Murty, U. S. R. (2008). Graph theory. Graduate Texts in Mathematics. 244. Springer.
ISBN 978-1-84628-969-9. MR
2368647.

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

外部リンク

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

[5] 概念

[9] ハイパーリンク

[10] (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140.　Konigsberg Bridge problemを参照。

[11] Diestel, p. 20

[12] グラフ理論の歴史を扱っているBiggs et al. (1998)にオイラーの論文の英訳を含む節がある。

[13] 詳しくは、一筆書きの項を参照。

[15] 無向グラフと有向グラフ

[Diestel-§1.1-16] ディーステル 2000, 1.1 グラフ

[FOOTNOTEBondyMurty200850-19] Bondy & Murty 2008, p. 50.

[FOOTNOTEディーステル200010-25] ディーステル 2000, p. 10.

[28] 多重グラフ

[33] ベルジュ「グラフの理論I」p.8.

[34] ディーステル, 2000

[35] 茨木「アルゴリズムとデータ構造」

[FOOTNOTEディーステル20006-36] ディーステル 2000, p. 6.

[FOOTNOTEBondyMurty200880-40] Bondy & Murty 2008, p. 80.

[43] 閉路

[45] Diestel, p. 115

[46] Fritsch (2012), p. 99

[47] “高校「新学習指導要領」は教え方改革 - 旺文社教育情報センター”. eic.obunsha.co.jp. 2019年2月1日閲覧。

[node-1] ^ ^a^b^cnode

[vertex-2] vertex

[edge-3] ^ ^a^b^cedge

[4] raph

[6] rected graph

[7] raph

[8] undirected graph

[arc-14] rc

[17] ^ link

[18] weighted graph

[20] t

[21] t

[22] th

[23] stance

[24] ter

[26] ^ loop

[27] simple graph

[29] subgraph

[30] spanning subgraph

[31] uced subgraph

[32] traction

[37] -regular

[38] walk

[39] trail

[41] th

[42] ycle

[44] te graph