連結成分・距離・直径・内周

頂点 $u,v$ について、$u$ から $v$ への歩道があるとき $u\sim v$ と書く。長さ 0 の歩道、歩道の逆順、歩道の連結を考えれば、$\sim$ は同値関係である。同値類が誘導する部分グラフを $G$ の連結成分といい、その個数を $c(G)$ と書く。$c(G)=1$ のとき $G$ は連結であるという。

$u\sim v$ のとき、$u$ から $v$ への道の長さの最小値を距離 $d(u,v)$ という（補題 2.5 により、歩道の長さの最小値と言っても同じ）。連結グラフの距離の最大値を直径、$G$ に含まれる閉路の長さの最小値を内周という（閉路がなければ内周は $\infty$）。