連結グラフ（れんけつグラフ, "connected graph"）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ ("disconnected graph") と呼ぶ。極大で連結な部分グラフは、連結成分 ("connected component") という。グラフがどの程度かたく結びついているかを示す不変量として連結度があり、主に点連結度 ("vertex-connectivity") と辺連結度 ("edge-connectivity") に分類される。また、グラフ全体の連結度 (それぞれ、辺連結度) について、指定した2点間に対する連結性を示す不変量として、局所点連結度 ("local vertex-connectivity") (それぞれ、局所辺連結度 ("local edge-connectivity") ) がある。点連結度 (それぞれ、局所点連結度) は単に連結度 (それぞれ、局所連結度) と呼ぶ場合があることを付記しておく。グラフGから取り除くこと非連結になるようなk個の頂点集合をk-点切断とよぶ。G においてk-点切断の最小サイズを点連結度または連結度とよび、formula_1で表す。特に、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の局所連結度といい、formula_2 等で表すことが多い。点連結度は局所連結度の最小値と一致する。グラフGのある因子がk連結なら、G自身もk連結となる。Gがk連結で、Gの自分自身を除いた因子がk連結でないとき（つまり、Gから一つでも辺を取り除くとk連結でないとき）、Gを 極小k連結 ("minimally k-connected") という。グラフGから取り除くこと非連結になるようなk本の辺集合をk-辺切断 (またはk-カット) とよぶ。G において k-辺切断の最小サイズを辺連結度とよび、formula_3で表す。特に、1-辺切断を切断辺または橋 ("bridge") とよぶ。k-辺連結グラフ ("k-edge-connected graph") は、辺連結度がk以上のグラフのことを指す。点連結度と同様に、2点 formula_4 を分離する辺集合の大きさの最小値として、局所辺連結度が定義され formula_5 で表記される。また、 formula_6 となることを付記しておく。有向グラフにおいて、無向グラフと同様に連結度の対応物が定義されている。有向グラフが強連結であるとは、グラフ上の任意の2点間に有向路が存在することである。極大で強連結な部分グラフは、強連結成分という。ある2点 formula_4 を指定したとき、除去することで formula_4 のどちらを始点にしても有向路が存在しなくなるような点集合の大きさの最小値として、formula_4 の局所点強連結度 ("local vertex-strong connectivity") が定義される。 また、局所点強連結度の最小値を点強連結度 ("vertex-strong connectivity") と呼ぶ。点強連結度が formula_10 以上のグラフを formula_10 点強連結グラフ (formula_10-"strongly connected graph") 、または、formula_10 強グラフ (formula_10-"strong graph") と呼ぶ。ある2点 formula_4 を指定したとき、除去することで formula_4 のどちらを始点にしても有向路が存在しなくなるような辺集合の大きさの最小値として、formula_4 の局所有向辺強連結度 ("local arc-strong connectivity") が定義される。また、局所有向辺強連結度の最小値を有向辺強連結度 ("arc-strong connectivity") と呼ぶ。有向辺強連結度が formula_10 以上のグラフを formula_10 有向辺強連結グラフ (formula_10-"arc"-"strongly connected graph") 、または、formula_10 有向辺強グラフ (formula_10-"arc"-"strong graph") と呼ぶ。

出典:wikipedia