人に聞けない痔の悩み、これでスッキリ >>

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

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

A 回答 (3件)

こんにちは.



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

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

この問題の証明が自分で出来る(もしくは証明を理解できる)のであれば,
質問の問題の証明も出来るのではないかなと思います.
    • good
    • 0

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


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

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

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



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

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

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

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

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

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

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

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

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

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

m(_ _)m
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qグラフ理論

Gが三角形を持たない単純平面的グラフとすると、Gが4-彩色可能であることを帰納法を用いて証明するんですけど、「m≦2n-4」と「次数3以下の頂点がある」の二つで帰納法のやり方を教えてください。

Aベストアンサー

三角形を持たない単純平面的グラフについて,
1.どの頂点を取り除いてもやはり三角形を持たない単純平面的グラフである
2.次数が高々 3 の頂点が必ず存在する
ことが言えれば, 頂点数に関する帰納法で終了じゃない? まあ, きちんと考えたわけじゃないけど.
でも, m ≦ 2n-4 って条件は必要なのかなぁ.... 2 を証明するためにはあった方がいいけど....


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング