グラフの基礎グラフの連結性連結グラフ連結関係、同値関係、反射律、対称律、推移律

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第7章(グラフの基礎)、7.2(グラフの連結性)、7.2.2(連結グラフ)、問7.8の解答を求めてみる。

グラフの任意の頂点uに対して、uとuは連結している。

u \to u

よって、反射律が成り立つ。

グラつの任意の頂点u、 v に対して、

u \to v

ならば、 uとvの間に道が存在するので

v \to u

よって対称律が成り立つ。

グラフの任意の頂点u、v、 w に対して、

u \to v \land v \to w

ならば、 u から v への道、 v からwへの道が存在するので、2つの道をつなげれば、u から vv への道になる。

よって、

u \to w

すなわち推移律が成り立つ。

ゆえに、連結関係は同値関係である。

（証明終）