Next: 4.2 同値類の生成
Up: 4 例題：同値類の計算
Previous: 4 例題：同値類の計算
が集合S上の同値関係(equivalence relation)であるとは，Rが
反射的(reflexive)（任意の
について
がなりたつ）かつ
対称的(symmetric) (任意の 
について
ならば
で
ある）かつ推移的(transitive)（任意の
について，
かつ
ならば
である）であることをいいます．
同値類(Equivalent Classes)というのは，
の部分集合で，同値関係
によって関係付けられる要素の集合をいいます．集合は同値関係によっ
てが互いに素な同値類に分割することができます．
グラフにより同値類を表現するならば，グラフの頂点を集合の要素
とし，
グラフの辺により同値関係を表現するとした場合に，そのグラフの中の連結な
グラフがひとつの同値集合であり，グラフ全体が同値類を表現することになり
ます．
前回までに扱ってきたグラフでは連結なグラフを扱ってきましたが，連結でな
いグラフを扱う場合にはこのように連結性によりグラフを分割することが必要
になることもあります．
そこで，連結なグラフ（無向グラフ）に分解する手続き（同値類を求める手続
き）をここで考えておきます．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日