[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[nikomat 31936] Re: お騒がせしま した（Re: 走れぐずども）

In the message <20020628224301.07BDD3C3@ml.asahi-net.or.jp>,
    SATO Yoshiyuki writes:
> > 
> > ４色問題は、
> > 　地図を４色で塗り分ける。隣り合う領域は同色を使ってはいけない。
> > 　どんな形状の地図でも４色で塗りつぶせる。
> > というものでしょうか？

四色問題の簡単な解説↓
http://mathworld.wolfram.com/Four-ColorTheorem.html
結局はグラフ彩色問題(彩色数)に帰着します。

> 20数年前に、コンピュータを使った探索で、
> すべての基本図形（グラフ理論の言葉で表現）について
> 4色で十分、という証明は得られています。
> 当初、コンピュータを使ったということに反発があったようですが、
> 今はその証明は受け入れられているようです。

AppelとHaken [1977]ですので、もう25年前になりますね。
(学生の時はホットな話題だったのに ;-)

最近では、全く別なアプローチによる証明もあるそうです。

# Mathworldはこういう話の時に便利ですね。
# http://mathworld.wolfram.com/

-- 
    Shuichi ICHIKAWA <ichikawa@tutkie.tut.ac.jp>