グラフ (離散数学)
グラフの2辺が共通の頂点を共有する場合は、2辺が「隣接する (adjacent)」という。有向グラフの2辺は、1番目の終点が2番目の始点になっている場合に「連続する (consecutive)」という。同様に、2頂点が1辺を共有する場合は、2頂点が「隣接」する(有向グラフで、片方の頂点が始点、もう一方が終点ならば「連続」)といい、この場合に共通の1辺が2頂点を「結ぶ (join)」と言う。辺とその頂点とは「接続する (incident)」という。
頂点が1つだけで辺のないグラフは「自明なグラフ (trivial graph)」という。頂点だけからなるグラフは「辺のないグラフ (edgeless graph)」と呼ばれる。頂点も辺もないグラフは「空グラフ (null graph, empty graph)」と呼ばれたりもするが、この用語は一貫しておらず数学者全員がこの対象を容認しているわけではない。
通常、グラフの頂点は集合の元としての性質から互いに識別可能である。この種のグラフは「ラベル付き頂点を持つ (vertex-labeled)」と呼ぶ場合もある。
「完全グラフ (complete graph)」は、どの2頂点間にも1本の辺があるグラフ。完全グラフにはありうる全ての辺が含まれている。
右のダイアグラムは次のグラフを模式的に表現したものである。 頂点 V = { 1 , 2 , 3 , 4 , 5 , 6 } {\displaystyle V=\{1,2,3,4,5,6\}} 辺 E = { { 1 , 2 } , { 1 , 5 } , { 2 , 3 } , { 2 , 5 } , { 3 , 4 } , { 4 , 5 } , { 4 , 6 } } {\displaystyle E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}}
コンピュータサイエンスでは、有向グラフが知識(概念グラフなど)や有限状態機械(状態遷移図)ほか多くの離散構造を表すのに使われている。
集合 X {\displaystyle X} 上の二項関係 R {\displaystyle R} は有向グラフを定義する。
φ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 and x ≠ y } {\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}} は全ての辺を頂点の順序対に写す写像「接続関数 (incidence function)」である。
曖昧さを避けるため、この種類のグラフは厳密に「多重有向グラフ(directed multigraph)」と呼ぶ場合もある。
「ループ」は始点と終点が同一な辺である。上述の2種類の定義においては有向グラフはループを持つことができない、なぜなら、辺 ( x , y ) {\displaystyle (x,y)} の定義に x ≠ y {\displaystyle x\neq y} の条件があるので、頂点 x {\displaystyle x} と自分自身を結ぶループ(すなわち ( x , x ) {\displaystyle (x,x)} )は辺の定義を満たさないためである。 そのためループを許すには定義を拡張させる必要がある。
無向グラフでは、頂点 x から y まで道がたどれる場合、非順序対 { x , y } {\displaystyle \{x,y\}} が「連結している (connected)」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。
「連結グラフ」は、グラフにある任意の頂点の非順序対が連結している無向グラフである。それ以外の場合は非連結グラフと呼ばれる。
有向グラフでは、x から y まで有向道がたどれる場合に、頂点の順序対 ( x , y ) {\displaystyle (x,y)} が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後なら x から y までの無向道がたどれる場合は「弱連結」であると言う。それ以外の場合、その順序対は非連結と呼ばれる。
強連結グラフは、グラフにある任意の頂点の順序対が強連結している有向グラフである。それ以外で、グラフにある任意の頂点の順序対が弱連結している場合は、弱連結グラフという。それ以外のものは非連結グラフという。
k-頂点連結グラフやk-辺連結グラフは、取り除いた場合にグラフが非連結となる k−1 個の頂点(後者なら辺)集合が存在しないグラフ である。k-頂点連結グラフは単に「k-連結グラフ」と言うことも多い。