グラフ理論 - Wikipedia

グラフ理論（グラフりろん、英: graph theory）は、数学の一分野。ノード（節点・頂点^[1]）の集合とエッジ（枝・辺^[2]）の集合で構成されるグラフの性質について研究する学問である。なお「エッジ」をリンク^[3]という場合もある。コンピュータのデータ構造、アルゴリズムなどに広く応用されている。

グラフを用いることで、様々な物の関連性を表すことができる。

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

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

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

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

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

グラフの例編集

日常的な問題や工学的問題の多くをグラフとしてみなすことができる。以下はその例である。

路線図

前節の通り。

電気回路

回路図を書く場合、実際のリード線通りの形状に図を書いたりはしない。この場合も、「接点がどのようにつながれているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。

WWWの構造

WWWにおけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である。

有向グラフ編集

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

の三つ組

を有向グラフという。V の元を G の頂点^[7]またはノード^[8]、E の元を G の辺^[9]または弧^[10]と呼ぶ。

無向グラフ編集

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

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

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

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

• 根上生也　『離散構造　情報数学講座3』　共立出版、1993年。
• 秋山仁・R.L.Graham　『離散数学入門　入門有限・離散の数学1』　朝倉書店、1993年。