グラフとネットワーク (13) 演習問題 2016 年 7 月 25 日 岡本 吉央 提出締切： 2016 年 8 月 1 日 復習問題 13.1 任意の平面的グラフが 6 彩色可能で 追加問題 13.5 次の単純多角形を 3 人以下の監視員 あることを，以下の手順に従って証明せよ． で監視する方法を与えよ．なぜ監視できているのか ということも説明せよ． 1. 頂点数が 6 以下の (平面的であるとは限らない) 無向グラフが必ず 6 彩色可能であることを証 明せよ． 2. 平面的グラフには必ず次数が 5 以下の頂点が 存在することを証明せよ． 3. 頂点数に関する帰納法を用いて，任意の平面的 グラフが 6 彩色可能であることの証明を完結 させよ． 復習問題 13.2 次の単純多角形を 10 人以下の監視 員で監視する方法を与えよ．なぜ監視できているの かということも説明せよ． 補足問題 13.3 任意の外平面的グラフが 3 彩色可能 であることを証明せよ．(ヒント：四色定理を用いて もよい．) 追加問題 13.4 ブラジルの地図の 4 彩色を 1 つ見 つけよ．(地図は次のページにある．) 注意：Minas Gerais と Distrito Federal の境界は 1 次元的に接し ているので，異なる色で塗られなければならない． また，この地図は 3 彩色可能ではないが，その理 由を説明せよ．ヒント：頂点数 5 の閉路は 2 彩色可 能ではない． 1 2
© Copyright 2024 ExpyDoc
