グラフ

グラフ (graph)†

グラフ G は2項組 (V,E)．\(V=(v_1,\ldots,v_n)\) はノード (節点，頂点, node，vertex) の集合，E は辺 (枝，edge，arc，branch) の集合．辺は頂点の対 \((v_i,v_j),\;v_i,v_j\in V\)．

辺 \((v_i,v_j)\) と \((v_j,v_i)\) を区別するとき 有向グラフ (directed graph)，区別しないとき 無向グラフ (undirected graph) という．有向のとき辺の向きは \(v_i\) から \(v_j\)．
一つのノードに連結している辺の数をそのノードの 次数 (degree)．
二つのノードの間に辺があるときこれらのノードは 連結 (connected) である．辺が有向のとき，辺の向きに沿っているなら 強連結 (strongly connected)，逆向きなら 弱連結 (weakly connected)．
辺やノードに重みが割り当てられているものを重み付グラフ (weighted graph)．ラベルが付いているものをラベル付グラフ (labeled graph)．
V中の頂点の全ての対の間に辺が存在するとき 完全 (complete)，そうでないとき 不完全 (incomplete)
V'⊆V かつ E'⊆E なるグラフ G'=(V',E') をGの 部分グラフ (subgraph)
ノードの列 \(v_{i_0},\ldots,v_{i_k}\) について，\(v_{i_j}\) から \(v_{i_j+1}\) j＝0…k-1 でへ連結しているとき，この列を パス (路，道，path)，同じノードを通過しないパスを 単純路 (simple path)
始点と終点が同じパスを 閉路 (closed path)，同じノードを通過しない閉路を 単純閉路 (simple path)，全ての頂点を通過する単純閉路を Hamilton閉路 (Hamiltonian cycle)
有向グラフで，強連結の閉路が存在するとき 循環グラフ (cyclic graph)，存在しないとき 非循環グラフ (acyclic graph)