グラフ理論

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

概要

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

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

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

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

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

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

グラフの例

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

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

起源

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

形式的な定義

有向グラフ

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

$f\colon \ E\to V\times V$

の三つ組

$G:=(f,V,E)$

を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。

無向グラフ

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

$g\colon \ E\to P(V)$

があって、E の任意の元 e の像が g(e) = {v₁, v₂} のようにちょうど二つの元の集合になっているとする。このとき、三つ組

$G:=(g,V,E)$

を無向グラフという。V の元を G の頂点、E の元を G の辺と呼ぶ。g の値が常にk > 2個の元の集合となっているとき、k-ハイパーグラフという。

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

用語

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

頂点と辺

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

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

重み付きグラフ

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

接合と隣接

辺 $e$ の両端の点を端点といい、端点は 辺 $e$ に接合 (または、接続) しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接 しているという。

距離と直径

2頂点間の最短経路における辺数を距離と呼ぶ。グラフ G の最大頂点間距離を直径と呼び、diam(G) と表す。

ループと多重グラフ

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

部分グラフと拡大グラフ

縮約の図示

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

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

次数と正則グラフ

3-正則グラフの例

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

道と閉路

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

完全グラフとクリーク

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

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

その他の用語

• オイラー路（オイラー閉路・オイラーグラフ）
• ハミルトン路（ハミルトン閉路・ハミルトングラフ）
• 木 （根つき木・森）
  • 全域木
  • シュタイナー木
• 直径
• カット
• 2部グラフ （n 部グラフ・彩色）
• 同型グラフ
• 連結グラフ （連結成分・連結度）
• 平面グラフ （平面的グラフ）
• 接続行列・隣接行列
• グラフ的な数列
• マッチング
• 閉路グラフ
• 有向非巡回グラフ
• 独立集合
• ランダム・グラフ
• マイナー（グラフ理論）

問題と定理

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

応用

• デッドロックの検出
• ガベージコレクション
• ファイルシステム
• ニューラルネットワーク
• ペトリネット
• ループ量子重力理論
• スケジューリング問題
• PERT

参考文献

• ベルジュ, C. 著、伊理正夫・伊理由美・岩坪秀一・小林欣吾・佐藤創・星守 訳『グラフの理論I』サイエンス社、1976年。ISBN 4-7819-0111-5。 
• ディーステル, ラインハルト 著、根上生也・太田克弘 訳『グラフ理論』（原書第2版）シュプリンガー・フェアラーク東京、2000年。ISBN 978-4-431-70876-6。https://books.google.com/books?id=CZq8AAAAQBAJ。 (現在は丸善に移管)
• 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. MR0879117. 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. MR2368647 
• 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

関連文献

日本語の文献

• 根上生也『離散構造』共立出版〈情報数学講座 3〉、1993年。ISBN 4-320-02653-5。 
• 秋山仁、ロナルド・ルイス・グラハム『離散数学入門』朝倉書店〈入門有限・離散の数学 1〉、1993年。ISBN 4-254-11419-2。 
• 秋山仁 『グラフ理論最前線』朝倉書店 ISBN 978-4-254-11420-1.
• 加納幹雄 『情報科学のためのグラフ理論』朝倉書店 ISBN 978-4-254-11424-9.
• ハラリー, フランク 著、池田貞雄 訳『グラフ理論』共立出版、1971年。ISBN 978-4-320-01073-4。 
• 茨木俊秀『アルゴリズムとデータ構造』昭晃堂、1986年。ISBN 4-7856-0119-1。 

日本語以外

• 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.
• 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.
• 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