《グラフ・ネットワーク》

提供: ORWiki
ナビゲーションに移動 検索に移動

【ぐらふ・ねっとわーく (graphs and networks) 】

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

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

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

 二つのグラフに対して, グラフの点と枝の接続関係は保ったままの各点の名前(ラベル)を変えてとし,同時にの各枝の名前(ラベル)を変えてとしてグラフからグラフを得ることが可能であるとき, これらの二つのグラフは同形である (isomorphic)という.また,二つのグラフに対して, , であり,を,を,それぞれ,上に制限したものになっているとき, グラフをグラフの部分グラフという.与えられたグラフの幾何学的表現から,いくつかの枝を消し,いくつかの孤立して残る点を消して得られる幾何学的表現に対応するグラフが元のグラフの部分グラフである.



参考文献

[1] C. Berge, Graphes et Hypergraphes, Dunod, 1970. 伊理正夫 他 訳,『グラフの理論, I~III』, サイエンス社,1976.

[2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, 1976.

[3] R.Diestel, Graph Theory, 3rd ed., Springer, 2005.

[4] F. Harary, Graph Theory, Addison-Wesley, 1969. 池田貞雄 訳,『グラフ理論』, 共立出版,1971.

[5] 伊理正夫, 藤重悟, 大山達雄,『グラフ・ネットワーク・マトロイド』,産業図書,1986.