OR事典

グラフ (QC七つ道具の)

読み方：ぐらふ
【英】：graph

QC七つ道具の1つで, データを図に表し, データ全体の傾向を把握したり,変化の状態を明確にしたりするために用いられる. 折れ線グラフ, 棒グラフ,円グラフ, 帯グラフ, レーダーチャートなどがよく用いられる.

---

グラフ (グラフ理論の)

読み方：ぐらふ
【英】：graph

概要

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

詳説

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

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

グラフ上の点から点へ枝の向きは無視して接続する点と枝をたどって到達できるとき，たどる順に得られる点と枝の交互列を点から点への道（あるいは路）(path) という．その道上の枝がたどる向きにすべて揃っているとき，そのような道を有向道（あるいは有向路）(directed path)という．道および有向道は，少なくとも１本の枝を含み, その始点と終点が一致するとき，閉路(closed path (cycle))および有向閉路(directed closed path (directed cycle))と呼ばれる．平面上に枝を交差させることなく幾何学的に表現することが可能なグラフを平面グラフ (planar graph) という．閉路を含まない連結なグラフを木 (tree)という．グラフの点集合のある２分割が存在して，各枝がの点との点を結ぶとき，このグラフを2部グラフ (bipartite graph) という．との点の数がそれぞれとであって，の各点との各点を結ぶ枝が丁度１本存在するとき，この２部グラフを完全２部グラフと言い, のように表す．グラフが自己閉路（１本の枝からなる閉路）を含まず, そのすべての相異なる２点に対してそれらを結ぶ丁度１本の枝が存在するとき，このグラフを完全グラフ (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. 根上生也，太田克弘 訳，『グラフ理論』, シュプリンガー・フェアラーク東京，2000．

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

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

「OR事典」の他の用語

グラフ･ネットワーク：

TSP多面体  クラスカル法  クラスター分析  グラフ  シュタイナー最小木  ダイクストラ法  ダルメジ・メンデルゾーン分解