gm learning

グラフを分断する

　コンピュータのネットワークを想像しましょう． コンピュータがケーブルで結ばれて，ネットワークを作っています． コンピュータを頂点，ケーブルを辺と思えば， ネットワークはグラフに対応します．

　そのネットワーク上のどのコンピュータも 自由に通信ができるためには， そのグラフは連結でなければなりませんね．

　でも，何かの自己でどこかのコンピュータが壊れたり， ケーブルが切れたりすると， ネットワークが分断されて，自由に通信ができなくなってしまいます．

　とはいえ，仮にそこが壊れても，適当に通信経路を変更して， 残りのコンピュータの間での通信を維持することが可能なところもあります． ということは，逆に，そこが壊れたら，通信が維持できなくなるコンピュータや ケーブルをきちんと認識しておく必要がありますね．

　そういう壊れてはいけないコンピュータに対応する頂点を切断点， 切れてはいけないケーブルに対応する辺を切断辺と呼ぶます． つまり，切断点，切断辺とは，それぞれそれを除去してしまうと， グラフの連結成分が増えてしまう頂点や辺のことです．

　下のアプレットでは，グラフを描いてから， 切断点と切断辺のチェックボックスをチェックして， [決定]ボタンをクリックすると， 切断点は赤，切断辺は青で着色されます．

　辺をたくさん追加して，全体に丸い感じのグラフには， 切断点も切断辺もありません． 逆に，もっともスレンダーな連結グラフである木は， そのすべての辺が切断辺になっています．

　木のほとんどの頂点も切断点ですが， いくつか切断点でない（赤くならない）頂点もあります． それはどういう頂点でしょうか？ それがわかれば，次の問題の答えもわかるでしょう．

問題　すべての頂点が切断点になっているグラフはあるでしょうか？

• 切断点，切断辺の判定の秘密を知りたい．