グラフ理論の彩色問題

締切済

質問者：pee-ka-booooooo
質問日時：2011/07/19 20:56
回答数：3件

G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ．

この問題の証明が出来なくて困ってます。
誰かわかりやすく解説お願いします。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

最新から表示
回答順に表示

No.3

回答者： pori_boy
回答日時：2011/07/20 18:10

こんにちは．

色々な手順があるかもしれませんが，まず，以下の問題の証明は出来ますか？

G を単純平面的グラフとする．このとき，G が6-彩色可能であることを示せ．

この問題の証明が自分で出来る（もしくは証明を理解できる）のであれば，
質問の問題の証明も出来るのではないかなと思います．

- 0
- 件

通報する

No.2

回答者： Tacosan
回答日時：2011/07/20 14:39

「こういう丸投げ　が一番困る」の部分は #1 に同意.

そして, できないなら素直に「できない」って言ったほうがいいと思う.

少なくとも, 個人的には「どうすれば証明できるのか」が思いつかない. #1 の方針でいいのかもしれんけど, なんというか, 超大質量ブラックホール並みの落とし穴が掘ってあるように見えるんだよね....

- 0
- 件

通報する

No.1

回答者： B-juggler
回答日時：2011/07/19 21:24

こういう丸投げ　が一番困るね。

代数学の非常勤講師ね（病気療養だけど）。

「どこまで分かっているのか」が分からないから、

どっから書いていいのかわからないんですよ。

４色問題だから、「どういう状況のグラフであれば　４色でいい」というのが

分かっていないようです。

単純平面グラフ　って何かをまず見直して。

それを理解して、　「三角形を含まない　単純平面グラフ」が理解できれば

証明も何も必要のないくらいに簡単なんだよ？

う～ん、この頃、大学生も丸投げするなぁ～。

σ(・・*)が教えていた頃も、そうだったのかな？

ｍ（＿　＿）ｍ