書記が数学やるだけ#608 道と閉路，連結性

道と閉路の性質についてみていく。

問題

説明

道に関する用語について整理しておく。

連結性は位数とサイズだけでわかることもある。

ここで連結に関する概念として切断点・橋について。

解答

歩道・小道・道・閉路について例を挙げておく。

2分グラフは奇閉路を含まないことを示す。

連結性の判定について，補題としてサイズに関する不等式を示す。

上限と下限について例を示しておく。

このことから連結性の判定法を得る。

本記事のもくじはこちら：