gm learning

グラフの中のかたまり

　まず，下のアプレットの中で，グラフを描きましょう． ただし，適当に辺どうしが交差するように努めてください． それと，あまり辺を追加しないように．

　グラフができあがったところで， 連結成分のチェックボックスをチェックします． こうすると，頂点をクリックしても，辺の追加ができなくなります． その代わりに， 頂点や辺をクリックすると， それを含むある部分がマークされます．

　そのマークさらた部分をドラッグしてみると， その部分が他とは切り離された１つの塊になっていることがわかるでしょう． その塊のことを，グラフの連結成分と呼びます． その連結成分を移動して，残りの部分と分離してください．

もし，グラフの全体がマークされてしまったら， そのグラフは連結成分が１つだけというわけです． その場合には，グラフは連結であると言います．

　連結成分のチェックをはずして， 辺をダブルクリックして，削除していってください． いずれ連結成分が切り出せる状態になるでしょう． そのように，複数の連結成分に分離できるグラフは 非連結であると言います．

• 連結成分の判定の秘密を知りたい．