- ベストアンサー
グラフの臨界条件と連結性について
- グラフの臨界条件とは、連結であることを指します。
- もしグラフが連結でなければ、複数の連結部分グラフに分かれることになります。
- それにより、グラフの彩色数は連結部分グラフの中で最大のものになります。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
[1]「グラフGの彩色数」というのは、Gのノードを色分けするのに必要な最少限の色数のこと。 [2]「グラフGが臨界であるならば、グラフGは連結である」という命題は、「グラフGが連結でないならば、グラフGは臨界でない」という命題と同じ意味です。（論理学で言う「対偶」ってやつですね。） [3] グラフGが臨界であるってのは、「Gからどれかひとつでもノードを取り除いたグラフHの彩色数hは、Gの彩色数gよりも小さい(h＜g)」という性質をGが持っている、ということ。 [4] グラフGが連結でないってのは、要するに「Gは二つのグラフJ, Kをただ並べただけのもの」だということ。JとKのあいだに全く繋がりがない。当然、JとKは互いに無関係にそれぞれ色分けができる。なので、Jの彩色数をj、Kの彩色数をkとすると、Gの彩色数gは g =（ jかkの大きい方） である。（これはアキラカでしょ？） 以上を確認した上で、さて、グラフGが連結でないとしましょう。すなわち、Gは二つのグラフJ, Kをただ並べただけのものである、という場合を考える。そして、Gの彩色数をg、Jの彩色数をj、Kの彩色数をkとします。すると[4]より g =（ jかkの大きい方） である。 ここで、 (1) k=g である場合 Jのノードをどれかひとつ取り除いたグラフPを作り、その彩色数をpとする。そして、KとPからなるグラフHを考え、Hの彩色数をhとする。すると、Hは二つのグラフK, Pをただ並べただけのものだから、[4]により h = ( pかkの大きい方） である。なので、 h≧k である。ところがk=gなのだから、 h≧g である。だから[3]により、グラフGは臨界ではない。 (2) j=g である場合 この場合も、(1)のKとJ, kとjをそれぞれ入れ替えれば、全く同じ結論、すなわち、グラフGは臨界ではない、ということが出ます。 以上から、グラフGが連結でないならば、グラフGは臨界ではない。なので[2]により、「グラフGが臨界であるならば、グラフGは連結である」が言えます。
お礼
なるほど！ すごい分かりやすいです。 考え方ひとつでこんなにつじつまがぴったり合うなんて。 ありがとうございました！ もっとよく読んで自分のものにしたいと思います！