グラフ (離散数学)
ハイパーグラフでは、1つの辺が2つ以上の頂点と接合可能である。
無向グラフは、1次元単体(辺)と 0次元単体(頂点)からなる単体複体と見なすことも可能である。複体はより高次元の単体を容認しうるので、それ自体がグラフの一般化である。
全てのグラフはマトロイドを持ちうる。
モデル理論においてグラフは単なる構造である。しかしその場合、辺の数に制限はなく何らかの基数になりうる(詳細はen:Graphonを参照)。
計算生物学において、パワーグラフ分析は無向グラフの代替表現としてパワーグラフを導入している。
地理情報システム (GIS) では、地理的ネットワークがグラフを基に厳密にモデル構築され、グラフ理論から多くの概念を借用して道路網や電力系統の空間解析を行っている。
初期のグラフから新しいグラフを生成する数学的操作が幾つかあり、次のように分類される場合がある。
「単項演算 (unary operation)」では、1つの初期グラフから以下のような新たグラフを生み出す。 辺の縮約 (edge contraction) -ある1辺を縮めて両端点を1頂点にする操作 ライングラフ 双対グラフ 補グラフ-頂点集合はそのままで隣接関係を逆にする操作 グラフ書換え (graph rewriting)
「二項演算 (binary operation)」では、2つの初期グラフから以下のような新たグラフを生み出す。 グラフ同士の交わりを持たない和 グラフ同士のデカルト積 (cartesian product of graphs) グラフ同士のテンソル積 (tensor product of graphs) グラフ同士の強い積 (strong product of graphs) グラフ同士の辞書積 (lexicographic product of graphs) 直並列グラフ (series-parallel graph)
具体的には、{x, y} が辺であれば、2つの頂点 x と y は「隣接している (adjacent)」という。
一つのグラフは n × n {\displaystyle n\times n} の正方行列である隣接行列 A {\displaystyle A} によって完全に指定できる。 A i j {\displaystyle A_{ij}} は頂点 i と頂点 j をつなぐ接続の数を指定する。単純グラフの場合、 A i j ∈ { 0 , 1 } {\displaystyle A_{ij}\in \{0,1\}} であり、0と1が非接続と接続をそれぞれ表す。またこのとき A i i = 0 {\displaystyle A_{ii}=0} である(つまりループを持たない)。ループ付きグラフは、一部または全ての A i i {\displaystyle A_{ii}} が正の整数になり、多重グラフ(頂点間に複数の辺がある)は一部または全ての A i j {\displaystyle A_{ij}} が正の整数になる。無向グラフの隣接行列は対称行列となる ( A i j = A j i {\displaystyle A_{ij}=A_{ji}} )。
「重み付きグラフ (weighed graph)」もしくは「ネットワーク (network)」とは、各辺に数値(重み)が割り当てられているグラフ 。この重みとは、扱う問題次第で例えば料金や距離や所要時間だったりする。こうしたグラフは、例えば巡回セールスマン問題のような最短経路問題など、多くの文脈で作成される。
有向グラフ (directed graph, digraph) は、辺に向きがあるグラフである。
限定的だが非常に一般的な意味において、有向グラフは以下の条件を満たす対 G = ( V , E ) {\displaystyle G=(V,E)} として定義される。
V {\displaystyle V} は、頂点の集合
E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 and x ≠ y } {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}} は辺の集合で、辺(有向辺とも言う)は頂点の順序対である。つまり1辺が異なる2頂点と関連している。
曖昧さを避けるため、この種類のグラフは厳密に「単純有向グラフ (directed simple graph)」と呼ぶ場合もある。
辺 ( x , y ) {\displaystyle (x,y)} は x {\displaystyle x} から y {\displaystyle y} の向きを表し、頂点 x {\displaystyle x} と y {\displaystyle y} はその辺の「端点」であるが、 x {\displaystyle x} は辺の「始点 (tail)」そして y {\displaystyle y} は辺の「終点 (head)」という。