| |
|
グラフ理論は、数学の一分野。ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフの性質について研究する学問である。
コンピュータのデータ構造、アルゴリズムなどに広く応用されている。
| Table of contents |
|
2 グラフの例 3 グラフ理論の起源 4 厳密なグラフの定義 5 グラフ理論の用語 6 グラフ理論の問題・定理 7 応用 8 関連項目 |
 |
| 6つのノードと7つのエッジから成るグラフの一例 |
つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフという。矢印のないグラフは、無向グラフという。
グラフの例
;乗り換え案内図: 前述の通り。
;電気回路:回路図を書く場合、実際のリード線通りの形状に図を書いたりはしない。この場合も、「接点がどのようにつながれているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。
;WWWの構造:WWWにおけるウェブページの、リンク・被リンク関係がなす構造は、有向グラフの一種である。
グラフ理論の起源
グラフ理論は、1736年、「ケーニヒスベルクの問題」に対してオイラーが解法を示したのが起源とされる。この問題は、一筆書きと深く関連している。（詳しくは、一筆書きの項を参照。）
厳密なグラフの定義
有向グラフ
V をノードの集合、E をエッジの集合とする。エッジに二つのノードの対を対応させる関数 f を
無向グラフ
P(V) を V のベキ集合とする。エッジにいくつかのノードを対応させる関数 g を
E を最初からある集合の部分集合と考えれば、上の定義から関数を除くこともできる。有向グラフでは、E を V×V の部分集合、無向グラフでは、E を P(V) の部分集合とすればよい。
グラフGの頂点集合はV(G)、枝集合はE(G)で表すことが多い。
辺eの両端の点を端点といい、端点はeに接合しているという。また、辺と辺がある頂点を共有しているとき、その辺同士は隣接しているという。ある辺の両端点が等しいとき、ループ（自己ループ）という。また、2頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを、単純グラフという。
二つのグラフGとG'について、G'の頂点集合と辺集合が共にGの頂点集合と辺集合の部分集合になっているとき、G'はGの部分グラフであるという。逆に、GはG'の拡大グラフであるという。特に、頂点集合が等しい部分グラフのことを、全域部分グラフ（生成部分グラフ・因子）という。また、Gの頂点集合Vの部分集合Sを取り出して、両端点がSに属する全ての辺を辺集合とするGの部分グラフを、誘導部分グラフという。それから、グラフGからある辺を取り除き、その辺の両端点を一つの頂点に縮約したとき、縮約グラフ（商グラフ）という。
有向グラフにおいて、ある頂点vに入ってくる枝の数のことを入次数、出て行く枝の数のことを出次数という。そして、頂点vに接続する枝の数を次数といい、d(v)で表す。すべてのvについて、d(v)=kが成り立つとき、k-正則という。あるkについてk-正則なグラフのことを正則グラフという。グラフG中の最小次数の頂点の次数をδ(G)、最大次数の頂点の次数をΔ(G)で表すことが多い。また、次数0の頂点のことを孤立点という。
隣接している頂点同士をたどったv1, e1, v2, e2,..., en-1, vnの系列を歩道（鎖）という。辺の重複を許さない場合、路（小径）といい、頂点の重複も許さない場合、道という。また、始点と終点が同じ路のことを閉路（回路・サイクル）という。
任意の2頂点間に枝があるグラフのことを完全グラフ（完備グラフ）という。n頂点の完全グラフは、Knで表す。また、完全グラフになる誘導部分グラフのことをクリークという。サイズnのクリークを含むグラフは「n-クリークである」と言う。辺を持つグラフは必ず2頂点の完全グラフを含むので2-クリークである。またn-クリークであって、直径がn未満となるグラフをn-クランと言う。
グラフ理論の用語
グラフの定義によっては、辺に重み（コスト）が付いていることがある。このようなグラフは、重み付きグラフと呼ばれる。その他のグラフ理論の用語
グラフ理論の問題・定理
応用
関連項目