グラフ理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』

グラフ理論（グラフりろん、Graph theory）は、数学の一分野。ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフの性質について研究する学問である。

コンピュータのデータ構造、アルゴリズムなどに広く応用されている。

目次

[編集] グラフとは

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

例えば電車の乗換案内図を考える際には、駅（ノード）がどのように路線（エッジ）で結ばれているかが問題であって、線路が具体的にどのような曲線を描いているかは本質的な問題でないことが多い。

事実、乗換案内図を書く場合には、駅間の距離や微妙な配置、路線の形状といったものは、地理的な実際のそれとは異なって描かれることが多い。（例えば、実際には外回りが左にカーブしている場所のある山手線が楕円形を描いているなど）電車で移動する人を対象とした乗換案内においては、駅と駅の「つながり方」が主に重要なのである。

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

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

[編集] グラフの例

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

[編集] グラフ理論の起源

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

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

[編集] 有向グラフ

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

f\colon E \to V \times V

の三つ組

G := (f, V, E)

を有向グラフという。V の元を G の頂点 (vertex) またはノード、E の元を G の辺 (edge) またはエッジと呼ぶ。

[編集] 無向グラフ

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

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

[編集] 頂点と辺

グラフ G の頂点 [英 vertex; pl. vertices] 集合は V(G)、辺 [英 edge] 集合は E(G) で表す。

[編集] 重みつきグラフ

グラフの辺に重み（コスト）が付いているグラフを、重み付きグラフ (英 weighted graph)と呼ぶ。

[編集] 接合と隣接

辺 e の両端の点を端点 [英 endpoint] といい、端点は 辺e に接合しているという。また、辺と辺がある頂点を共有しているとき、その辺同士は隣接 している[英 形 adjacent; 名 adjacency]という。

[編集] 距離と直径

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

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

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

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

二つのグラフ G と G' について、G' の頂点集合と辺集合が共にG の頂点集合と辺集合の部分集合になっているとき、G'は Gの部分グラフ [英 subgraph]であるという。逆に、G はG' の拡大グラフ[英 supergraph?]であるという。 特に、頂点集合が等しい部分グラフのことを、全域部分グラフ（生成部分グラフ・因子）[英 spanning graph]という。また、G の頂点集合V の部分集合Sを取り出して、両端点がSに属する全ての辺を辺集合とする G の部分グラフを、誘導部分グラフ[英 induced subgraph]という。それから、グラフ G からある辺を取り除き、その辺の両端点を一つの頂点に縮約したとき、縮約グラフ（商グラフ）[英 degenerate graph ?]という。

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

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

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

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

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

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


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

[編集] グラフ理論の問題・定理

[編集] 応用

[編集] 関連項目

"http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" より作成