連結グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/07/07 14:05 UTC 版)
連結グラフ（れんけつグラフ、英: connected graph）は、グラフ上の任意の2頂点間に道が存在するグラフのことである。連結でないグラフを非連結グラフ (disconnected graph) と呼ぶ。極大で連結な部分グラフは、連結成分 (connected component) という。
- ^ 点連結度の対応物と辺連結度の対応物についての用語の和訳は定訳が不明であるため直訳した。
- 1 連結グラフとは
- 2 連結グラフの概要
- 3 連結度の一般化
連結グラフ
出典: フリー百科事典『ウィキペディア（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-連結グラフ」と言うことも多い。
※この「連結グラフ」の解説は、「グラフ (離散数学)」の解説の一部です。
「連結グラフ」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。
連結グラフと同じ種類の言葉
- 連結グラフのページへのリンク
