連結グラフ
(連結度_(グラフ理論) から転送)
出典: フリー百科事典『ウィキペディア（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 を点連結度または連結度とよび、
カテゴリ / 
コモンズ
- 連結度_(グラフ理論)のページへのリンク
