連結グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/28 02:31 UTC 版)
連結グラフ（れんけつグラフ、英: connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ（disconnected graph）と呼ぶ。極大で連結な部分グラフは、連結成分（connected component）という。
連結度
グラフがどの程度かたく結びついているかを示す不変量として連結度があり、主に点連結度（vertex-connectivity）と辺連結度（edge-connectivity）に分類される。また、グラフ全体の連結度 (それぞれ、辺連結度) について、指定した2点間に対する連結性を示す不変量として、局所点連結度（local vertex-connectivity）（それぞれ、局所辺連結度（local edge-connectivity））がある。点連結度（それぞれ、局所点連結度）は単に連結度（それぞれ、局所連結度）と呼ぶ場合があることを付記しておく。
点連結度
グラフ G から取り除くと非連結になるような k 個の頂点集合をk-点切断とよぶ。G においてk-点切断が存在するような最小の k を点連結度または連結度とよび、
カテゴリ / 
コモンズ
連結グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/12 14:26 UTC 版)
「グラフ (離散数学)」の記事における「連結グラフ」の解説
詳細は「連結グラフ」を参照 無向グラフでは、頂点 x から y まで道がたどれる場合、非順序対 { x , y } {\displaystyle \{x,y\}} が「連結している (connected)」と言う。道が存在しない場合、その非順序対は「非連結」と呼ばれる。 「連結グラフ」は、グラフにある任意の頂点の非順序対が連結している無向グラフである。それ以外の場合は非連結グラフと呼ばれる。 有向グラフでは、x から y まで有向道がたどれる場合に、頂点の順序対 ( x , y ) {\displaystyle (x,y)} が「強連結」であると言う。有向道は存在しないが、有向辺を全て無向辺に置き換えた後なら x から y までの無向道がたどれる場合は「弱連結」であると言う。それ以外の場合、その順序対は非連結と呼ばれる。 強連結グラフは、グラフにある任意の頂点の順序対が強連結している有向グラフである。それ以外で、グラフにある任意の頂点の順序対が弱連結している場合は、弱連結グラフという。それ以外のものは非連結グラフという。 k-頂点連結グラフやk-辺連結グラフは、取り除いた場合にグラフが非連結となる k−1 個の頂点（後者なら辺）集合が存在しないグラフである。k-頂点連結グラフは単に「k-連結グラフ」と言うことも多い。
※この「連結グラフ」の解説は、「グラフ (離散数学)」の解説の一部です。
「連結グラフ」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。
連結グラフと同じ種類の言葉
- 連結グラフのページへのリンク
