グラフ理論

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

グラフ理論(グラフりろん、: graph theory)は、数学の一分野。ノード節点[1]頂点[2])の集合とエッジ[3])の集合で構成されるグラフ[4]の性質について研究する学問。コンピュータのデータ構造アルゴリズムなどに広く応用されている。

概要[編集]

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

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

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

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

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

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

グラフの例[編集]

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

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

起源[編集]

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

厳密なグラフの定義[編集]

有向グラフ[編集]

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

f\colon\  E \to V \times V

の三つ組

G := (f, V, E)

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

無向グラフ[編集]

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

g\colon\  E \to P(V)

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

G := (g, V, E)

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

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

用語[編集]

頂点と辺[編集]

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

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

重み付きグラフ[編集]

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

接合と隣接[編集]

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

距離と直径[編集]

2頂点間の最短経路における辺数を距離[14]と呼ぶ。グラフの最大頂点間距離を直径[15]と呼ぶ。

ループと多重グラフ[編集]

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

部分グラフと親グラフ[編集]

二つのグラフ GG' について、G' の頂点集合と辺集合が共にG の頂点集合と辺集合の部分集合になっているとき、G'G部分グラフ[18]であるという。逆に、GG'拡大グラフであるという。特に、頂点集合が等しい部分グラフのことを、全域部分グラフ[19]生成部分グラフ因子)という。また、G の頂点集合V の部分集合Sを取り出して、両端点がSに属する全ての辺を辺集合とする G の部分グラフを、誘導部分グラフ[20]という。グラフ G からある辺を取り除き、その辺の両端点を一つの頂点にまとめたとき、縮約グラフ[21]商グラフ)という。

次数と正則グラフ[編集]

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

通路(ウォーク)と循環(サイクル)[編集]

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

完全グラフとクリーク[編集]

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

その他のグラフ理論の用語[編集]

問題と定理[編集]

応用[編集]

参考文献[編集]

脚注[編集]

  1. ^ a b c : node
  2. ^ a b c : vertex
  3. ^ a b c : edge
  4. ^ : graph
  5. ^ : directed graph
  6. ^ : digraph
  7. ^ : undirected graph
  8. ^ : arc
  9. ^ : arc
  10. ^ : link
  11. ^ : weighted graph
  12. ^ : endpoint
  13. ^ : adjacent
  14. ^ : distance
  15. ^ : diameter
  16. ^ : loop
  17. ^ : simple graph
  18. ^ : subgraph
  19. ^ : spanning graph
  20. ^ : induced subgraph
  21. ^ : degenerate graph
  22. ^ : k-regular
  23. ^ : walk
  24. ^ : trail
  25. ^ : path
  26. ^ : cycle
  27. ^ : complete graph

関連項目[編集]