グラフ理論

グラフ理論は、ノードの集合とエッジの集合で構成されるグラフに関する数学の理論である。

グラフなどの応用がある。

1. 概要
-----

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

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

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

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

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

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

1.1. グラフの例
----------

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

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

2. 起源
-----

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

3. 形式的な定義
---------

3.1. 有向グラフ
----------

集合 //V// , //E// と、//E// の元に、二つの //V// を元の対で対応させる写像

の三つ組

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

3.2. 無向グラフ
----------

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

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

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

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

4. 用語
-----

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

4.1. 頂点と辺
---------

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

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

4.2. 重み付きグラフ
------------

グラフの辺に重みが付いているグラフを、重み付きグラフと呼ぶBondy。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる。

4.3. 接合と隣接
----------

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

4.4. 距離と直径
----------

2頂点間を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフ //G// の最大頂点間距離を直径と呼び、diam と表すディーステル。

4.5. ループと多重グラフ
--------------

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

4.6. 部分グラフと拡大グラフ
----------------

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

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

4.7. 次数と正則グラフ
-------------

頂点 に接続する枝の数を次数といい、 で表す。有向グラフにおいては、 に入ってくる辺数のことを入次数、 から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶディーステル。任意の頂点 について、 が成り立つとき、// -正則という。//k// -正則なグラフのことを//k// -正則グラフという。グラフ が持つ頂点の次数の最小値を 、最大値を で表す。また、次数 0 の頂点のことを孤立点という。

4.8. 道と閉路
---------

隣接している頂点同士をたどった の系列を長さ //n//  の歩道という。辺の重複を許さない歩道を路というBondy。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路、始点と終点が同じ道のことを閉道という。

4.9. 完全グラフとクリーク
---------------

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

4.10. その他の用語
------------

5. 応用
-----

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

5.1. 計算機科学
----------

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

5.2. 言語学
--------

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

5.3. 物理学および化学
-------------

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

5.4. 社会科学
---------

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

5.5. 生物学
--------

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

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

5.6. 数学
-------

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

5.7. その他
--------

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

6. 問題と定理
--------

7. 備考
-----

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

8. 脚注
-----

8.1. 出典と補足
----------

9. 参考文献
-------

和書

Reinhard Diestel , Graphentheorie. Springer-Verlag, Vierte Auflage, 2010 Korrigierter Nachdruck 2012 Heidelberg xviii+355 Seiten, 129 Abbildungen September 2010  ISBN 978-3-642-14911-5 EUR 32,99.
Rudolf Fritsch, Gerda Fritsch, translated by J.lie Peschke:The Four-Color Theorem : History, Topological Foundations, and Idea of Proof, Springer; Softcover reprint of the original 1st edition 1998; ISBN 978-1-46127-254-0

10. 関連文献
--------

10.1. 日本語の文献
------------

秋山仁 『グラフ理論最前線』朝倉書店 ISBN 978-4-254-11420-1.
加納幹雄 『情報科学のためのグラフ理論』朝倉書店 ISBN 978-4-254-11424-9.
鈴木晋一編著 『数学教材としてのグラフ理論』, 早稲田教育叢書 31, 学文社, ISBN 978-4-76202-253-1
ノラ・ハーツフィールド&ゲーハード・リンゲル著 鈴木晋一訳,『グラフ理論入門』,サイエンス社, ISBN 978-4-78190-654-6
ボロバシュ・ベーラ著 斎藤伸自, 西関隆夫訳,『グラフ理論入門』,培風館, ISBN 978-4-56300-544-3

10.2. 日本語以外
-----------

Berge, Claude , 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 , Introductory Graph Theory, Dover, ISBN 0-486-24775-9.
Leonhard Euler, Euler Complete Edition 
Hajnal Péter , [2] - Polygon jegyzet
Harary, Frank , Graph Theory, Reading, MA: Addison-Wesley.
Harary, Frank; Palmer, Edgar M. , Graphical Enumeration, New York, NY: Academic Press.
Lovász László , Kombinatorikai problémák és feladatok, Typotex Kiadó, ISBN 978-963-9664-93-7.
Manfred Nitzsche , 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  Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin - Heidelberg . ISBN 3-540-00045-3
William Thomas Tutte , Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3.

11. 関連項目
--------

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

12. 外部リンク
---------

[3]
[4]
[5] 2007 by Jorgen Bang-Jensen and Gregory Gutin
[6]
[7] - tools to teach and learn graph theory
[8]
[9]  by Hartmann and Weigt
[10] - a graph theory IDE
[11] - non-technical paper discussing graphs of people and computers