グラフ (グラフ理論の)

【ぐらふ (graph)】

概要

グラフは, 点の集合 $V\,$ , 枝の集合 $A\,$ および各枝 $a\in A\,$ の始点と終点を指定する2つの写像 $\partial ^{+}:A\to V\,$ と $\partial ^{-}:A\to V\,$ からなる複合概念であり, グラフ $G=(V,A;\partial ^{+},\partial ^{-})\,$ (あるいは $(V,A)\,$ )のように記される. グラフは平面上に, 点を丸で, 枝を矢線で描き, 幾何学的に表現される. 枝 $a\,$ の矢線の始点が $\partial ^{+}a\,$ を, 終点が $\partial ^{-}a\,$ を表す. 枝の方向を考慮する場合を有向グラフ, 考慮しない場合を無向グラフと呼び区別する.

詳説

　グラフ (graph)は，点の集合 $V\,$ ，枝の集合 $A\,$ および各枝 $a\in A\,$ の始点と終点を指定する二つの写像 $\partial ^{+}:A\to V\,$ と $\partial ^{-}:A\to V\,$ からなる複合概念であり，グラフ $G=(V,A;\partial ^{+},\partial ^{-})\,$ のように記される．また，しばしば $G=(V,A)\,$ のように略記される．グラフは平面上に，点を丸で，枝を矢線で描き，幾何学的に表現される．枝 $a\,$ の矢線の始点が $\partial ^{+}a\,$ を，終点が $\partial ^{-}a\,$ を表している． $u=\partial ^{+}a\,$ で $v=\partial ^{-}a\,$ であるとき，枝 $a\,$ は点 $u\,$ から点 $v\,$ への枝といわれる．すべての２点 $u\,$ , $v\,$ に対して点 $u\,$ から点 $v\,$ への枝が高々１本だけであるとき, 点 $u\,$ から点 $v\,$ への枝があればそれを $(u,v)\,$ のように点の順序対で表現することも多い．これからも分かるようにグラフはその点集合上の２項関係を表すものであると考えることができる．様々なシステムの構造を捕らえるとき, それらのシステムの構成要素の間の２項関係を考えることはもっとも基本的であり, モデル化も容易である．枝 $(u,v)\,$ は $u\,$ から $v\,$ へのものの流れ（の存在）を表現したり, $u\,$ から $v\,$ への因果関係，通信ケーブルや道路などのリンクの存在などを表現したりする．日常的にも用いられる「・・・ネットワーク」や「・・・網」といわれるものはグラフ構造を持つものである．

　取り扱う問題によっては, 各枝の始点と終点がどちらであるかを気にしない（すなわち対称な２項関係を考える）こともある．このようなとき，平面上の幾何学的表現では各枝を表現する矢線から矢印を取って，そのグラフを表現する．このようなグラフは無向グラフ (undirected graph) と呼ばれる．最初に定義した通常のグラフを無向グラフと対比して示したいとき, これを有向グラフ (directed graph あるいは digraph) という．グラフの用語については，日本語および英語の両方とも，必ずしも統一されていない．点は，頂点，節点とも呼ばれ，枝は，辺，弧，線などとも呼ばれる．英語では，点はvertex, node, 枝は edge, arc などがよく用いられる（枝に対し有向グラフでarc, 無向グラフでedgeを用いる流儀もある）．グラフの枝（や点）にそれに付随する容量，長さ，費用などの属性を付与してグラフ中のものの流れなどを考える場合, これをネットワーク (network) と呼ぶ．

　グラフ $G=(V,A)\,$ 上の点 $u\,$ から点 $v\,$ へ枝の向きは無視して接続する点と枝をたどって到達できるとき，たどる順に得られる点と枝の交互列を点 $u\,$ から点 $v\,$ への道（あるいは路）(path) という．その道上の枝がたどる向きにすべて揃っているとき，そのような道を有向道（あるいは有向路）(directed path)という．道および有向道は，少なくとも１本の枝を含み, その始点と終点が一致するとき，閉路(closed path (cycle))および有向閉路(directed closed path (directed cycle))と呼ばれる．平面上に枝を交差させることなく幾何学的に表現することが可能なグラフを平面グラフ (planar graph) という．閉路を含まない連結なグラフを木 (tree)という．グラフ $G\,$ の点集合 $v\,$ のある２分割 $\{U,W\}\,$ が存在して，各枝が $U\,$ の点と $W\,$ の点を結ぶとき，このグラフ $G\,$ を2部グラフ (bipartite graph) という． $U\,$ と $W\,$ の点の数がそれぞれ $m\,$ と $n\,$ であって， $U\,$ の各点と $W\,$ の各点を結ぶ枝が丁度１本存在するとき，この２部グラフを完全２部グラフと言い, ${\rm {K}}_{m,n}\,$ のように表す．グラフ $G\,$ が自己閉路（１本の枝からなる閉路）を含まず, そのすべての相異なる２点に対してそれらを結ぶ丁度１本の枝が存在するとき，このグラフを完全グラフ (complete graph)（あるいは完備グラフ）という．ここで， $V\,$ の点の数が $n\,$ であるとき，これを $n\,$ 点完全グラフと呼び, ${\rm {K}}_{n}\,$ のように表す．

　二つのグラフ $G_{1}=(V_{1},A_{1};\partial _{1}^{+},\partial _{1}^{-})\,$ と $G_{2}=(V_{2},A_{2};\partial _{2}^{+},\partial _{2}^{-})\,$ に対して, グラフ $G_{1}\,$ の点と枝の接続関係は保ったまま $V_{1}\,$ の各点の名前（ラベル）を変えて $V_{2}\,$ とし，同時に $A_{1}\,$ の各枝の名前（ラベル）を変えて $A_{2}\,$ としてグラフ $G_{1}\,$ からグラフ $G_{2}\,$ を得ることが可能であるとき, これらの二つのグラフは同形である (isomorphic)という．また，二つのグラフ $G_{1}=(V_{1},A_{1};\partial _{1}^{+},\partial _{1}^{-})\,$ と $G_{2}=(V_{2},A_{2};\partial _{2}^{+},\partial _{2}^{-})\,$ に対して, $V_{2}\subseteq V_{1}\,$ , $A_{2}\subseteq A_{1}\,$ であり， $\partial _{2}^{+}\,$ が $\partial _{1}^{+}\,$ を， $\partial _{2}^{-}\,$ が $\partial _{1}^{-}\,$ を，それぞれ， $A_{2}\,$ 上に制限したものになっているとき, グラフ $G_{2}\,$ をグラフ $G_{1}\,$ の部分グラフという．与えられたグラフ $G\,$ の幾何学的表現から，いくつかの枝を消し，いくつかの孤立して残る点を消して得られる幾何学的表現に対応するグラフが元のグラフ $G\,$ の部分グラフである．