連結グラフ
出典: フリー百科事典『ウィキペディア（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-連結グラフ」と言うことも多い。
※この「連結グラフ」の解説は、「グラフ (離散数学)」の解説の一部です。
「連結グラフ」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。
連結グラフと同じ種類の言葉
Weblioに収録されているすべての辞書から連結グラフを検索する場合は、下記のリンクをクリックしてください。
全ての辞書から連結グラフ
を検索
- 連結グラフのページへのリンク
