[グラフ] グラフ理論

グラフ理論

グラフ理論（グラフりろん、英: Graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ（データ構造）などの応用がある。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

グラフ$ G(V, E) $ とは、様々なもの同士の「関係」を表す数学の理論です。

グラフは、ノード（節点・頂点・node・vertex）の集合とエッジ（枝・辺・edge）から成り、ノードをエッジがつなぐことで、ノード同士の関係を表します。

エッジが方向を持つ有向グラフと、方向を持たない無向グラフがあります。

有向グラフ

無向グラフ

グラフの表現方法

プログラムでは、グラフは、隣接行列か隣接リストという形で表されます。

隣接行列

隣接行列は、ノード$i$からノード$j$へエッジがある時$A_{ij} = 1$、エッジが無いとき $A_{ij} = 0$となる行列$A$です。

無向グラフ

上の無向グラフは、隣接行列では以下のように表現されます。

$$ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$

例えば、1行目はノード1からノード2へつながりを表すため$A_{12}=1$で、それ以外はつながりがないので0になっています。

隣接リスト

隣接リストは、それぞれのノードごとにそのノードに隣接するノードをリストとして管理する方法です。

無向グラフ

例えば、上の無向グラフは、オブジェクトとして Python で以下のように表現できます。

class Vertex(object):

     def __init__(self, vertex_name, vertex_neighbors=None):
         self.name = vertex_name
         self.neighbors = vertex_neighbors

if __name__ == '__main__':

    v1 = Vertex(1, [2])
    v2 = Vertex(2, [1, 3, 4])
    v3 = Vertex(3, [2])
    v4 = Vertex(4, [2])

    # [1, 3, 4]
    print(v2.neighbors)

辞書を使い表現できます。

verticies = {'v1':[2], 'v2':[1, 3, 4], 'v3':[2], 'v4':[2]}

# [1, 3, 4]
print(verticies['v2'])

それぞれの頂点を0で始まる整数に変換して、リストで表現することもできます。

# Python は0-originなので、
# ここでは上のグラフで、全ての頂点から1を引いてそれぞれの頂点を表す
verticies = [
    [1],
    [0, 2, 3],
    [1],
    [1]
]

# [0, 2, 3]
print(verticies[1])