グラフ理論

提供: miniwiki
2018/10/11/ (木) 07:31時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

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

概要

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

ファイル:6n-graf.svg
6 つのノードと 7 つのエッジから成るグラフの一例

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

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

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

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

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

[math]\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}[/math]

グラフの例

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

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

起源

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

形式的な定義

有向グラフ

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

[math]f\colon\ E \to V \times V[/math]

の三つ組

[math]G := (f, V, E)[/math]

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

無向グラフ

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

[math]g\colon\ E \to P(V)[/math]

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

[math]G := (g, V, E)[/math]

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

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

用語

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

頂点と辺

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

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

重み付きグラフ

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

接合と隣接

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

距離と直径

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

ループと多重グラフ

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

部分グラフと拡大グラフ

ファイル:Edge contraction.svg
縮約の図示

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

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

次数と正則グラフ

ファイル:3r3c well-covered.svg
3-正則グラフの例

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

道と閉路

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

完全グラフとクリーク

ファイル:Complete graph K3.svg
3頂点からなる完全グラフ：三角形

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

その他の用語

問題と定理

応用

脚注

出典と補足

  1. ↑ 概念
  2. ↑ ハイパーリンク
  3. ↑ (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140.　Konigsberg Bridge problemを参照。
  4. ↑ Diestel, p. 20
  5. ↑ グラフ理論の歴史を扱っているBiggs et al. (1998)にオイラーの論文の英訳を含む節がある。
  6. ↑ 詳しくは、一筆書きの項を参照。
  7. ↑ 無向グラフと有向グラフ
  8. ↑ 8.0 8.1 8.2 8.3 ディーステル 2000, テンプレート:Google books quote
  9. ↑ Bondy & Murty 2008, p. 50.
  10. ↑ 10.0 10.1 ディーステル 2000, p. テンプレート:Google books quote.
  11. ↑ 多重グラフ
  12. ↑ ベルジュ「グラフの理論I」p.8.
  13. ↑ ディーステル, 2000
  14. ↑ 茨木「アルゴリズムとデータ構造」
  15. ↑ Bondy & Murty 2008, p. 80.
  16. ↑ 閉路
  17. ↑ Diestel, p. 115
  18. ↑ Fritsch (2012), p. 99

英語による専門用語

  1. ↑ 1.0 1.1 1.2 node
  2. ↑ 2.0 2.1 2.2 vertex
  3. ↑ 3.0 3.1 3.2 edge
  4. ↑ graph
  5. ↑ directed graph
  6. ↑ digraph
  7. ↑ undirected graph
  8. ↑ 8.0 8.1 arc
  9. ↑ link
  10. ↑ weighted graph
  11. ↑ endpoint
  12. ↑ adjacent
  13. ↑ length
  14. ↑ distance
  15. ↑ diameter
  16. ↑ loop
  17. ↑ simple graph
  18. ↑ subgraph
  19. ↑ spanning subgraph
  20. ↑ induced subgraph
  21. ↑ contraction
  22. ↑ k-regular
  23. ↑ walk
  24. ↑ trail
  25. ↑ path
  26. ↑ cycle
  27. ↑ complete graph

参考文献

  • 『グラフの理論I』 伊理正夫・伊理由美・岩坪秀一・小林欣吾・佐藤創・星守訳、サイエンス社、1976年。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.
  • (1998) Graph theory 1736–1936, Reprint with corrections, Oxford University Press. ISBN 0-19-853916-9. 
  • (2008) Graph theory, Graduate Texts in Mathematics. Springer. ISBN 978-1-84628-969-9. 
  • 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

関連文献

日本語の文献

日本語以外

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

関連項目

外部リンク

テンプレート:Graph Theory-footer テンプレート:最適化アルゴリズム



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=グラフ理論&oldid=235485」から取得