10/05/16 19:29:21
プレイナーグラフ＝平面グラフ
サーフィス＝面
67:１３２人目の素数さん
10/05/22 17:39:32
任意に平面上の地図が与えられた時に、
それを４色（以下）で塗りわけるアルゴリズムが存在するか？
（「塗り別けられる」、というのと、
「塗り別けを具体的に構成できるアルゴリズムがある」、
というのは精密化のレベルが違うのだ。）
68:帰納と類比
10/06/03 00:35:25
>>63>>64>>65>>66
説明ありがとうございました。
>>67
任意の平面上の地図を４色で塗り分けるアルゴリズムはまだ存在しない。
あれば４色問題の解になるから。
69:１３２人目の素数さん
10/06/05 00:42:19
>>68
>任意の平面上の地図を４色で塗り分けるアルゴリズムはまだ存在しない。
>あれば４色問題の解になるから。
これは間違いなんじゃね？
４色彩色のアルゴリズムが存在しても、
アルゴリズムの収束性が証明できなければ
４色問題の解にならないのでは？
70:１３２人目の素数さん
10/06/05 09:40:13
アルゴリズムの収束性ってなに？
71:１３２人目の素数さん
10/06/05 21:30:00
４＾（地区の数）通りを調べるというアルゴリズムが存在する。
72:帰納と類比
10/06/07 00:00:26
>>71
調べるというアルゴリズムでは、４色問題の解にはならない。
73:１３２人目の素数さん
10/06/07 00:17:02
だから>>68は間違い。
74:帰納と類比
10/06/12 12:12:48
>>73
意味がよくわからない。
平面を４色で塗るアルゴリズムがあればどんな地図も４色で塗れることになり、
４色問題は解決される。
４色で塗れるか塗れないか調べるアルゴリズムがあっても５色の地図があれば、
４色で塗れるかどうか分からないから、調べ方でなく塗り方のアルゴリズムが
必要である。
75:１３２人目の素数さん
10/06/12 13:19:03
何を言っているのかよくわからないんだが
・４色問題は、既に肯定的に解決されている。
・４色で塗り分けられない地図（５色以上必要な地図）は通常の平面では存在しない。
・全ての国を全ての色に塗ってみて（最大４の国の数乗通り）
うまく塗り分けできるまで繰り返すアルゴリズムは必ず成功する。
どれかわからないところがあるか？
76:１３２人目の素数さん
10/06/12 13:43:10
>>74
＞ 平面を４色で塗るアルゴリズムがあればどんな地図も４色で塗れることになり、
＞ ４色問題は解決される。
されない。
どんな平面地図でも４色で塗り分ける簡単なアルゴリズムは存在するが
それは既に他の方法で４色で必ず塗り分けられることが保障されていることを利用しているので
そのアルゴリズムの存在そのものでは、４色問題は解決されたとは言えない。
77:帰納と類比
10/06/12 15:47:42
>>75
>・４色問題は、既に肯定的に解決されている。
だれが？
いつ？
どの国で？
アッペルとハーケンじゃないよね。？
78:１３２人目の素数さん
10/06/12 16:09:22
君が認めないのはもちろん自由だが
世間的には７６年のアッペル・ハーケンで解決。
79:１３２人目の素数さん
10/06/21 23:44:19
ｽﾚﾘﾝｸ(math板)
URLﾘﾝｸ(book.geocities.jp)
80:帰納と類比
10/06/23 20:18:36
>>all
ありがとうございました。
インターネット止めるのでこのスレは終了いたします。
永らくのご鑑賞・ご意見本当にご苦労さんでした。
またいつの日にか戻ってまいります。
この証明は正しいので、記念にコピペしておいてください。
以上。
81:１３２人目の素数さん
10/06/23 23:59:46
国の数が有限ではなくて，無限に国がありうるとなると、
４色では塗れない場合が出てくるかもしれない。
82:１３２人目の素数さん
10/06/24 07:27:55
to>>81
平面グラフであることの characterization とコンパクト定理で、
有限の場合に帰着することはよく知られている。
83:１３２人目の素数さん
10/06/24 23:29:59
どうしても５色以上必要としたいなら、トーラス表面などに地図を描けばよい。
84:１３２人目の素数さん
10/07/16 21:30:05
私はこの問題に関して素晴らしい証明を考えたが、
分かり易く説明するには図が沢山要るのでここには書けない
85:１３２人目の素数さん
10/07/17 00:15:15
>>84
フェルマー乙
86:１３２人目の素数さん
10/08/02 20:41:32
4色のドットでもてかるろしる