連結グラフ
グラフ G から取り除くと非連結になるような k 個の頂点集合をk-点切断とよぶ。G においてk-点切断の最小サイズを点連結度または連結度とよび、 κ ( G ) , χ ( G ) {\displaystyle \kappa (G),\chi (G)} で表す。特に、1-点切断を切断点 (cut vertex) または関節点 (articulation point) とよぶ。k-連結グラフ (k-connected graph) は点連結度が k 以上のグラフである。
G から S を取り除いたグラフにおいて x と y の間に道が存在しないことを頂点の集合 S が x, y を分離するという。グラフ G から(もし存在すれば)辺 xy を除いたグラフにおいて、二つの頂点 x, y を分離するために必要な頂点の個数を s とするこのとき、x, yが隣接していないなら s を、x, y が隣接しているなら s + 1 を x, y の局所連結度といい、κ(x, y) 等で表すことが多い。点連結度は局所連結度の最小値と一致する。
グラフ G のある因子が k連結なら、G 自身も k 連結となる。G が k 連結で、G の自分自身を除いた因子が k 連結でないとき(つまり、G から一つでも辺を取り除くと k 連結でないとき)、G を 極小 k 連結 (minimally k-connected) という。
ある2点 x, y を指定したとき、除去することで x, y のどちらを始点にしても有向路が存在しなくなるような辺集合の大きさの最小値として、 x, y の局所有向辺強連結度 (local arc-strong connectivity) が定義される。また、局所有向辺強連結度の最小値を有向辺強連結度 (arc-strong connectivity) と呼ぶ。有向辺強連結度が k 以上のグラフを k 有向辺強連結グラフ (k-arc-strongly connected graph) 、または、k 有向辺強グラフ (k-arc-strong graph) と呼ぶ。
ある2点 x, y を指定したとき、除去することで x, y のどちらを始点にしても有向路が存在しなくなるような点集合の大きさの最小値として、x, y の局所点強連結度 (local vertex-strong connectivity) が定義される。 また、局所点強連結度の最小値を点強連結度 (vertex-strong connectivity) と呼ぶ。点強連結度が k 以上のグラフを k 点強連結グラフ (k-strongly connected graph) 、または、 k 強グラフ (k-strong graph) と呼ぶ。