[過去ﾛｸﾞ] ☆四色問題の簡単な証明その３☆ (779ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
124: 2011/03/29(火) 13:30:26.75 AAS
>>122
[(a)〜(e)を３色で] を補う先の 「都合の悪い配色は〜」という
一文を削除するの？
指示通りに書き直すと文章にならないんだけど？
中途半端な「加える」とか「削除する」とかいう指示じゃなくて
>>106 の (2) にあたる部分を自分なりに
書き直した完全な文章を提示してもらえませんか?
125: 2011/03/29(火) 15:47:13.18 AAS
>>106
パッと見(3)で証明として論理破綻してるよなｗｗ
126: 2011/03/29(火) 20:34:57.77 AAS
俺一人が正しいって思っている奴を説得するのは無理だよ
127: 2011/03/29(火) 20:56:01.76 AAS
帰納と類比vs猫はまだ？
128(5): 帰納と類比 2011/03/29(火) 21:42:34.45 AAS
5集点は不可避集合である。
Ｎ−１点までのグラフは４配色可能であると仮定する。
Ｎ点の任意のグラフにある５集点に着目する。
５集点の中央の頂点P0とその辺を仮に削除する。
このＮ−１点のグラフは仮定より４配色が可能である。
P0の周りの頂点をP1〜P5とする。
P1〜P5の頂点は４色で塗られている。
５つ頂点の内同じ色のものを色Ｂとする。
色Ｂと色Ｂに囲まれた一個の頂点をP1とする。
P1の色をＡとしP2，P5を色Ｂにする。
残った色ＣをP3，色ＤをP4とする。
仮にP1〜P5が３色で塗られていれば、P0を戻してＮ点で４配色可能となる。
上記P1〜P5が４色でＣをＡに変えられない、ＤをＡに変えられないとする。
ケンペ鎖ではＡＣチェーン、ＡＤチェーンが繋がっているとする。
ＡとＣをコントラクトしてＮ−２点のグラフを得る。
このとき頂点Ａは頂点Ｃと結合するのでＡ，Ｃ以外の色で、頂点ＡはＢに
辺で接しているので、Ｂ以外の色、頂点ＣはＤに接しているのでＤ以外の色
を要求される。５色目のＥが必要となる。
同様にＡとＤをコントラクトしてＮ−２点のグラフを得た場合
５色目のＥが必要になる。
Ｎ−１点以下のグラフは４配色可能なのでＮ−２点でも４配色可能となる。
しかし仮定に反し５色目が必要になった。
これはＮ−１点以下のグラフが４配色可能と言うことに矛盾する。
従ってＡＣチェーンまたはＡＤチェーンが切れているグラフが１つは存在
しなければならない。
よってP1〜P5を３色で配色することができる。
よってＮ−１点のグラフが４配色可能であればＮ点のグラフも４配色可能である。
よって帰納法が成立し、平面状のグラフは４配色可能である。
129: 2011/03/29(火) 22:11:04.78 AAS
>同様にＡとＤをコントラクトしてＮ−２点のグラフを得た場合
>５色目のＥが必要になる。
>Ｎ−１点以下のグラフは４配色可能なのでＮ−２点でも４配色可能となる。
よって５色目のＥが必要になると思ったのは間違いだった。
130(5): 2011/03/29(火) 22:51:36.16 AA×
>>128
131(5): 2011/03/29(火) 22:53:35.68 AA×
>>130
132(1): 2011/03/29(火) 23:13:35.01 AAS
言葉が通じないのであくまでも推測だけど、上の2つの塗り分けでは
(A)-(C)のケンペ鎖が繋がっているが、最後の図のような塗り分けは存在して
そのときそのケンペ鎖は繋がっていない、という主張じゃないかと思う。
133(1): 帰納と類比 2011/03/29(火) 23:35:13.30 AA×
>>131>>130
134(1): 2011/03/29(火) 23:55:46.11 AAS
>>130と>>131は同じ人じゃねえの？
135(3): 2011/03/29(火) 23:58:46.27 AAS
>>132
なるほど.
ようやく証明の流れが分かったような気がする.
「考えている N-1 点のグラフの『任意の』 4色塗り分けに対して,
P1〜P5 を塗るのに4色使われていて, かつ AC チェーン, AD チェーンが
繋がっているとせよ.
そうすると, A と C, あるいは Aと D を「接合」して得られる N-2 点の
グラフの塗り分けに5色必要」
となるから矛盾, といいたいわけか. すると多分,
命題: 「N-2 点のグラフの『全ての』4色での塗り分けは,
元のN-1点グラフの4色を用いた『ある』塗り分けから上記の
操作で得られる」
ということが成立すると思っているのね.
これは自明じゃないから、これを示さないと何も証明したことに
ならないよ.
>>134
うん, 同じ人. 改行多すぎると怒られたから分けただけ.
136(3): 帰納と類比 2011/03/30(水) 08:49:55.87 AAS
>>135
>命題: 「N-2 点のグラフの『全ての』4色での塗り分けは,
>元のN-1点グラフの4色を用いた『ある』塗り分けから上記の
>操作で得られる」
>ということが成立すると思っているのね.
>これは自明じゃないから、これを示さないと何も証明したことに
>ならないよ.
これは自明なんだがな。Ｎ−２点のグラフはＮ−１点の接合で得られる。
137: 2011/03/30(水) 09:04:35.15 AAS
>>136
自明だというなら, 証明してください.
138: 2011/03/30(水) 15:36:37.18 AAS
ここって、帰納と類比の頭の中を暴くスレですか？
139: 2011/03/30(水) 20:49:40.90 AAS
>>119
色を全部チャラにして白紙の状態から塗りなおせば、塗り分けられるってこと？
140(1): 帰納と類比 2011/03/30(水) 22:53:01.35 AAS
>>135
上記の操作ではなく、３集点を追加してＮ−１点のグラフにすればいい。
上記の操作にこだわる理由はどこにあるの？
上記の操作では５色目が必要になる場合があり、矛盾を生じる。
訂正：>>136
与えられた命題は正しくはない。
141(1): 2011/03/30(水) 23:51:44.91 AAS
>>140
>上記の操作では５色目が必要になる場合があり、矛盾を生じる。
え?
単に「5色目が必要になる場合がある」っていうのが,
「4色で塗り分け可能」という仮定と反すると, この期に及んでも
本気で思ってたの?
>訂正：>>136
>与えられた命題は正しくはない。
そうですか.
正しくないと断言するなら, 反例を示していただけ
ますか?
その反例が, あなたの4色問題の証明の不備を
明らかにするはずですから.
142(1): 帰納と類比 2011/03/31(木) 20:27:06.17 AAS
>>141
今までのレスをしっかり読んでください。
>>128 >>130
143: 2011/03/31(木) 20:42:41.09 AAS
>>142
えっ？
私は 141 だけど, >>128 を読んだ上で
>>130 を書いた本人だよ？
(ついでに >>131 135 もね)
ひょっとして >>130 をあなたの応援演説のように
でも思ってるの？
あなたこそしっかりと今までのレスを読みなよ.
>>130 131 は一続きで, >>128 の書き込みが
とんでもない間違いを言っているとしか思えない、
というのがその主張だよ.
144(1): 帰納と類比 2011/03/31(木) 22:46:45.20 AAS
>>131は間違いだよ。
そのような塗り方は存在しない。
だからＡＣとＡＤチェーンが結ばれていれば、５色目が必要になる。
何度も言ってるんだが分からないかな。
もし塗れるとしたら>>131の配色の手順を述べて欲しいものだ。
145(5): 2011/03/31(木) 23:09:20.70 AA×
>>144>>131>>133
146(1): 帰納と類比 2011/03/31(木) 23:55:09.40 AAS
>>145
ちょっと時間をください。
よく検討してみます。
1週間くらいかかるかな。
上記図は特殊な場合に成立する。一般的でない。ある条件が必要。
この場ではここまでにして保留にする。
147(2): 2011/04/01(金) 22:44:57.12 AAS
前スレとか読んでなくって、場違いな質問になりますが、
何かご存知のことがあれば教えてください。
以下の命題が正しいとすれば、グラフ理論におけるテイト定理(3正則な平面グラフの辺彩色は3彩色的である)を直接的に証明できます。
テイト定理⇔四色定理なので、逆に四色定理から、下記の正しさを導き出すことができないか?
そして、もし、四色定理に帰着できるならば、次数を限定化した四色定理(つまり、次数N以下の平面グラフ)に帰着させることはできないか？
（例えば、次数5以下の平面グラフで四色定理が成り立つことは、五色定理から簡単に導かれますよね？）
などと言うことを考えています。
反例や未解決であることのソースなんでもいいので情報をください。
以下は命題です。
-----------------------------------------------------------
命題※
頂点彩色が3彩色可能な平面グラフGについて
3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点の集合を「同色点集合」と定義する。
※明らかに同色点集合であることの必要条件は独立点集合(安定集合)であることである。
このとき、以下の命題は常に真か?
3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、それら3点を
結ぶ辺を追加したグラフG'が平面的ならば、平面グラフGには次数6以上の点が存在する。
148(1): 2011/04/01(金) 22:45:39.84 AAS
テイト定理証明の流れ(上記を正しいと仮定した上で)
1.次数3,4,5の点の双対グラフを考える。
これらは、3正則な平面グラフにおいて不可避集合である。
(3正則な平面グラフの双対グラフは極大平面グラフだから)
2.次数4の点の双対グラフについて
これは、周り4本の辺をどのように彩色しても
内部は3彩色可能である。ところで、3正則な平面グラフにおいて
3彩色不可能であるようなグラフのうち最も小さいグラフを
最小反例と定義する。最小反例は1つでも点を除去すれば、
3彩色可能である。次数4の点の双対グラフを除いたグラフが
3彩色的ならば、加えたグラフも3彩色的であるため、
次数4の点の双対グラフは 最小反例には含まれない。
このような配置を可約配置と定義する。
149(1): 2011/04/01(金) 22:46:00.49 AAS
3.次数3の点の双対グラフ(a)について
これは、周り3本の辺が全て同色の時のみ3彩色できない(証明略)
ここで、3正則な平面グラフのライングラフを考える。
このグラフは、4正則な平面グラフ(*)である(証明略)
最小反例に(a)が存在すると仮定し、そのライングラフを考える。
最小反例から(a)除いたグラフは、3彩色可能である。
このとき、(a)に接合していた3点に着目すれば同色点集合である
ことがわかる。再び(a)をもどし、適当に縮約と削除を行えば、
それら3点を結ぶ3角形ができる(証明略)。平面グラフのマイナーは
平面グラフである。3点全てが同一の同色点集合に含まれるならば
命題※より次数6を含むことになるが、これは(*)と矛盾する。
よって、少なくとも1つは同色点集合に含まれない。
このことから、周り3本の辺が全て同色になる以外の塗りわけが
少なくとも1つ存在するため、3正則な平面グラフに配置(a)が
存在する時、配置(a)は可約配置である。
4.次数5の点の双対グラフについて
上記とほぼ同様の方法で可約配置であることが証明できる。
5.締め
このことより、3正則な平面グラフには少なくとも1つは可約配置を
含むため、最小反例は存在しない。よって、3正則な平面グラフの
辺彩色は3彩色的である。
6.さらに
正則な平面グラフの辺彩色が3彩色的ならば、あらゆる平面グラフは
２つのサイクルの合併である。
よって、あらゆる平面グラフは4 彩色的である。
150: 2011/04/01(金) 22:46:46.75 AAS
正確には「どんなブリッジをもたない」が必要だと思いますが
その辺は読み替えてください。
上記のアプローチはあまりにもシンプルで四色定理の証明について
テイト彩色からのアプローチは19世紀から主流だったことから、
このアプローチはかなり昔に既に考えられていてもおかしくないの
ではないかとおもっています。
だとすると、
1.今まで誰も考えたことなかった発想(・・・それはないだろ?)
2.命題※の証明は未解決で四色定理と同等以上に難しい。
3.そもそも命題※は間違っている(そうでないことを祈りたい)
4.そもそも命題※は証明できない(そうでないことを祈りたい)
になるので、2.であると信じて近年証明された定理や予想を
探して考えているのですが、命題※が証明できる気がしません。
(私が証明したいのは命題※であって四色定理ではない)
なにかご存知のことがあれば教えてください。
でも、ここまで言って簡単に(しかも否定的)に解決されたら・・・
私は自分の間抜けさに絶望して、スフィンクスに倣うしかなくなるかも知れません。
151(1): 2011/04/02(土) 00:16:42.83 AAS
>>147
> 3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点
こういう点は存在しないと思うが？
152: 2011/04/02(土) 00:29:14.03 AAS
> 3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点
ポイントは平面グラフの『4彩色』ではなく平面グラフの『3彩色』である点
例えば、1つの辺を共有する隣り合う3角形を考えた場合、次数2の点同士は常に同じ色でしか塗りわけできない(異なる色で塗るとグラフが4彩色されるため)。
153: 2011/04/02(土) 00:48:04.07 AAS
>>151
同色点集合の定義を変えてみた。
頂点彩色が3彩色可能な平面グラフGについて
どのような塗り分けを行っても全ての要素が同一色になる独立点集合を
「同色点集合」と定義する(なんか記号使った方がいい?)。
154(1): 2011/04/02(土) 01:11:06.99 AAS
>>148
> 1.次数3,4,5の点の双対グラフを考える。
双対グラフってのは点に対して定義されるものじゃなくて、グラフに対して定義されるものでしょ？
> これは、周り4本の辺をどのように彩色しても
> 内部は3彩色可能である。
内部ってのはどこのこと？
155: 2011/04/02(土) 01:14:19.43 AAS
スマン。流石にあいまいすぎるな。
＼ ／
口
／ ＼
の口の部分
156: 2011/04/02(土) 01:18:52.26 AAS
>154
双対グラフってのは点に対して定義されるものじゃなくて、グラフに対して定義されるものでしょ？
それは思ったが文章で手っ取り早く流れ(要点)だけを説明したかったので。
この辺は図を使えばいくらでも正確に定義できるし、証明もできる
(言ってる意味は理解してもらえてると思う)。
157(1): 2011/04/02(土) 01:26:30.39 AAS
３枝地図において三辺国，四辺国，五辺国は不可避非集合であるといった方が
文章的には分かりやすいだろうか?
158(1): 2011/04/02(土) 01:56:40.44 AAS
もとのグラフ(地図)とその双対グラフが出てくるから、どっちを指してるのか分かりにくいんだよね
例えば
> 1.次数3,4,5の点の双対グラフを考える。
こういう書き方をしたら、「次数3,4,5の点」ってのはもとの地図の頂点みたいに読めるけど、
>>157 を見ると、実際は双対グラフでの頂点を指してるわけでしょ？
159: 2011/04/02(土) 02:02:29.46 AAS
>>158
その通りです。この辺はもうちょっと整理すべきですね。
図をつければもうちょっと改善すると思う。
160: 2011/04/02(土) 10:31:41.17 AAS
言い忘れてたけど、
3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、それら3点を
結ぶ辺を追加したグラフG'が平面的ならば、平面グラフGには次数6以上の点が存在する。
上記からオイラー公式を使って以下に言い換えることができる(むしろ上は下からの帰着)。
3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、新たに
点vを追加し、選び出した3点とそれぞれ辺で接合したグラフG'が平面的ならば、
平面グラフGには次数6以上の点が存在する。
言い換えれば(むしろ上は下からの帰着)
3彩色可能な平面グラフGについて、平面グラフGが次数5以下の点のみで構成される場合、
次数3の点に着目したとき、隣接する3点のうち少なくとも一つは同一の同色点集合に
属さない。
つまり、次数4以下の平面グラフの3彩色問題を考える上で有効だと思っています。
テイト定理の証明は上記の証明を考える過程で発見しました。なので、個人的に
あまり重要ではありません。
161(1): 2011/04/02(土) 18:45:29.23 AAS
>>149
自己レスです。
>>このグラフは、4正則な平面グラフ(*)である(証明略)
4正則であることはほぼ自明だが、平面的であることは
自明だとは言えないので一応証明しておく。
3正則な平面グラフにおいて
点数を n, 辺数を mとすると
3正則なので、m=3n/2
生成されるライングラフにおいて
点数を n', 辺数を m'とすると、
n'=m=3n/2
m'=3n
n≧4の時、3n ≦ 9n/2 -6
ところで平面グラフの辺数の上限は
m'≦3n'-6
3正則グラフは、n≧4なので、3正則の平面グラフの
ライングラフは平面的である。
以上
162: 2011/04/02(土) 19:33:46.63 AAS
スマン・・・上の証明間違っている。
ところで平面グラフの辺数の上限は平万グラフであることの
十分条件であって必要条件ではない。
K3,3を考えてもらうと分かるが、
n=6,m=9
3n-6=18-6=12
よって、m<3n-6だが、平面的ではない。
・・・なぜこれに気がついたかと言うと、上記証明が正しいとすると
ピーターセングラフ(辺彩色が4彩色的)のライングラフも平面的になり、
テイト定理の証明と命題※が正しいこと自体が根本的に間違っている
ことになってしまうため、かなり焦って考え直しました。
・・・平面的であることの証明は考え直して見ます。
163: 2011/04/02(土) 22:03:46.44 AAS
>>161
3正則な平面グラフのライングラフが平面的であることの証明
3正則な平面グラフにおいて
点数を n, 辺数を m, 面数をfとすると
n+f=m+2
m=3n/2
n+f=3n/2 +2
一方、生成されるライングラフにおいて
点数を n', 辺数を m'，面数をf'とすると
n'=m=3n/2
m'=3n
f'=f+n=3n/2 +2
n'+h'=3n/2 +3n/2 +2=3n+2=m'+2
∴n'+h'=m'+2
よって、3正則な平面グラフのライングラフは
平面的である。
以上
・・・マジで焦った。4正則であることは、3正則グラフは
1つの辺に4つの辺が隣接してることから明らか。
164: 2011/04/02(土) 22:07:26.03 AAS
ちなみに、ピーターセングラフではn+f≠m+2なので、上記と同様の方法で
3正則な非平面グラフのライングラフは非平面的であることの証明もできます。
165(3): 帰納と類比 2011/04/03(日) 01:32:17.63 AA×
>>147-164>>135>>145
166(2): 2011/04/03(日) 02:26:39.60 AAS
>>165
もういいや.
さすがに, ここまでのアホの相手は時間の無駄だね.
あなたは「4色定理」を示そうとしてるんでしょ?
「4色定理」が正しければ, 塗り分けられないはずないじゃない.
--(C) (D)------
| ＼ ／ |
| C---B ---C |
| | ／ ＼ ／ |
--(A) D--(A)--
ほーら, 塗り分けられた.
それにね, たとえ「特殊な場合を除いて５色目が
必要となる」ことが示せたとしても(示せてないけどね),
それに何の意味もないよ.
あなたの証明が正しいためには, その推論が
「全ての場合」にうまくいかなければならない,
うまくいく例を一つ見せても無意味.
他方, あなたの証明が正しくないことを示すためには
うまくいかない例を「たった一つ」示せばいい,
この程度の論理も分からないんじゃ, 数学はやめて
おいたほうがいいよ.
167(1): 2011/04/03(日) 02:43:13.67 AAS
>>165
過去ログ読みました。
疑問に感じたことを書きます。
まず、彩色数が5の平面グラフを仮定し、そのうち最も
小さいものを最小反例と呼ぶことにします。最小反例は
可約配置を含まないため、バーコフのダイヤモンドや
次数4以下の点などの可約配置を含みません。
最小反例の頂点の数をnとおくと、明らかに頂点数がn未満の場合、
4彩色可能である。
ここで、最小反例よりも大きいグラフを考える。明らかに
彩色数が5の平面グラフは最小反例をマイナーに持つ。
また、最小反例をマイナーに持たない頂点数が多い
平面グラフは存在することは明らか。
よって、あなたの証明は最小反例の頂点数以下では成り立つ
のかも知れませんが、最小反例の頂点数を超えると成り立た
ないと考えられます。つまり、最小反例の頂点数をnとすると
n→∞であることの証明が必要だと思いますがどう考えられ
ていますか?
168: 2011/04/03(日) 03:16:35.53 AAS
あとは最小反例について、次数5の点を5色目で塗り分けるだけで全体が
5彩色できることの証明ですね。つまり、最小反例内に存在する次数5の
点がnあるとし、5色目でしか塗りわけられない点の数がnを超えないことと
次数5の点に5色目を移動させる手順を教えてください。
169(1): 2011/04/03(日) 03:24:03.07 AAS
>>167
> 明らかに
> 彩色数が5の平面グラフは最小反例をマイナーに持つ。
横から悪いけど、これは何故？
170(4): 帰納と類比 2011/04/03(日) 03:32:47.47 AAS
>>166
--(C) (D)------
| | ＼ ／ |
| C---B ---C |
| | ／ ＼ ／ |
--(A) D--(A)--
ほうら、塗りわけられない。
特殊な条件のもとでしか４配色できない。
どうして分かってくれないの？
171: 2011/04/03(日) 03:36:53.03 AAS
>>169
自分で書いといてなんだが・・・・私も思った。
それがいえるんだったら、Hadwiger予想(k＝5)を証明して終わりだよね。
172: 2011/04/03(日) 04:47:35.47 AAS
あとやっぱり、最後の手順で5色目が必要になる理由が分かりません。
「色の拘束」と言う概念は分かますし、そこで5色目が必要になることも
わかります。ですが、点数がN-1以下だと「色の拘束」を行っても
4彩色可能であることは何故いえるのでしょうか？仮定では単純に
点数がN-1以下は4彩色可能だとしか言ってないので・・・・よく分かりません。
でも、この方法の面白さは感じました。AとCの接合と言う概念を用いれば、
ケンペ鎖を使わなくても次数4の点が可約配置であることの証明ができますから
便利だと思います。
173(2): 2011/04/03(日) 12:33:10.68 AAS
>>170
かわいそうになってきた.
辺をいくら増やしたって無駄なんだから.
--(C) (D)------
| | ＼ ／ |
| D---B ---D |
| | ／ ＼ ／ |
--(A) C--(A)--
ほら, ね.
それよりも >>166 の後半をよーく
読んでよ.
私は >>145 であなたの推論が正しくない例を
示した. それに反論したければ, 自分の推論どおりの
結果が出る例をいくら提示しても無意味
(提示すらできてないけど).
あなたのやるべきことは4色問題の
自称「証明」を修正することだよ.
174(3): 2011/04/03(日) 13:39:40.93 AA×
>>170>>128>>128
175: 2011/04/03(日) 14:16:58.22 AAS
>>174
予言しよう。
その例をみて帰納と類比は
「やっぱり5色目が必要だ。俺は正しい。
俺の理解者が現れた」
と言う。
176(2): 帰納と類比 2011/04/03(日) 14:24:36.79 AAS
>>173
--(C) (D)------
| | ＼ ／＼ |
| D---B ---D |
| | ／ ＼ ／ |
--(A) C--(A)--
ほらね、５色目が必要でしょ。
177: 2011/04/03(日) 16:37:24.77 AAS
>>174
直感的に反例があるのは分かっていたが、そういう示し方があったのね。
>>128の方法と同様の方法で、ケンプ鎖を使わずに5色定理が示せるので
最後の部分を除いて気に入っています(ケンプ鎖は個人的に嫌いなので)。
よければ、>>147-163も見てやってくださいな・・・・
178(1): 2011/04/03(日) 17:34:22.05 AAS
>>176
何度も言っているけど, たとえ >>176 のグラフを
塗り分けるのに5色目が必要であるとしても,
だから何だというの?
例えると
(1) あなたが, ある推論の下に
「このグループのメンバーは全員が男である」
と主張をした.
(2) 私はグループから一人選んで「でも, この人は女ですよ.
あなたの主張は間違いです」といった.
(3) あなたは (2) とは別のメンバーを連れてきて
「女性であるのは特殊な場合のみ. この人は男だ」
といっている.
(2) で選んだメンバーを「女じゃない, 男でしょ」というなら
反論になるけどそうじゃなけりゃ, いくらメンバーから男を探して
連れてきても, (2) の段階で残念ながらあなたの推論と主張の
誤りは確定なんだよ.
179: 2011/04/03(日) 19:29:48.06 AAS
>>178
中学生でもわかる論理を、何度言っても理解できない人に対して、
何度言っても無駄な事かと。
>>95 はある意味真実なので。
180: 帰納と類比 2011/04/03(日) 22:22:10.31 AAS
>>125-179
過去レス確認。
みんなケンペ鎖のことをよく理解してないな。
>>145
ＡＢチェーンの入れ替えＢＡチェーンにし、ＡＣがＢＣチェーンとなり
ＣのところにＢを置いて矛盾
>>170
ＢＣチェーンの入れ替えＣＢチェーンにし、ＡＣがＢＣチェーンになり
ＡのところにＢを置いて矛盾
>>173
ＡＤチェーンにＡのところにＤを置いて矛盾
接合の反対＝展開をしてメモでも取って図に書いて確認してください。
181(1): 2011/04/03(日) 23:27:17.62 AAS
どういう理屈で何が何に矛盾してるのか書けよ
182(1): 2011/04/04(月) 09:46:05.59 AAS
帰納と類比には論理的思考力がない典型例ってゆーか、
∃(ある)と∀(すべて)が絡むと理解不能に陥るようだね。
Ｐ「ある塗分け方で４彩色不可能」
Ｑ「すべての塗分け方で４彩色不可能」
Ｑは反例を一つ示せば主張は崩れるのであって、
それに対抗してＰの例をいくら挙げてもＱの不成立には変わりない。
帰納と類比の脳内では∃と∀がゴッチャになってるから、
いつまでも基本的な誤解に気付かず、周りの話が飲み込めない。
こんなの論理学の初歩なんだけどね。
「∃と∀の区別なんかはどうでもいい」って思ってるだろ？
それが致命的欠陥なんだよ。
183: 2011/04/04(月) 20:51:05.52 AAS
>>181
たしかに、帰納と類比に、「どういう理屈で」「何が」「何に」矛盾しているのか
書かせてみると面白そう。
184: 2011/04/04(月) 23:11:44.08 AAS
そんなの聞いてもどうせ、「>>6を読んでください」「考察してください」しか言わないだろ。
185: 2011/04/04(月) 23:52:00.74 AA×
>>174
186(3): 帰納と類比 2011/04/05(火) 05:26:40.60 AAS
>>182
Ｎ−２点の相対グラフである塗分け方で４彩色不可能
であるが、帰納法の仮定に矛盾するので矛盾を引き起こす
配色は存在しないと結論付けている。
このある塗り分け方を矛盾としたら、Ｎ点の相対グラフは
全て４配色可能であると結論付けられる。
この反例を矛盾としたことに帰納法の証明になんの問題もないと思うが。
ごく一般的な証明であると思う。
187(3): 2011/04/05(火) 10:58:56.75 AAS
>>186
2行目の「帰納法の仮定」は何？
1行目とどう矛盾する？
具体的に書けよ
188(4): 2011/04/05(火) 21:11:37.47 AAS
>>186
簡単に答えられる質問です。
「Ｎ−１点までのグラフは４配色可能であると仮定する。」
1. この仮定したグラフを四色で塗り分ける方法は何通り(以上 or 以下)あるか？
2. この仮定したグラフを五色で塗り分ける方法は何通り(以上 or 以下)あるか？
3. この仮定したグラフのいくつかの頂点の彩色を指定することで、
四色で塗り分けられないようにできるか？
4. 「接合」して得られたグラフを四色で塗り分ける方法は何通り(以上 or 以下)あるか？
5. 「接合」して得られたグラフを五色で塗り分ける方法は何通り(以上 or 以下)あるか？
6. 「接合」して得られたグラフのいくつかの頂点の彩色を指定することで、
四色で塗り分けられないようにできるか？
7. 1〜3の答えと4〜6の答えで矛盾することがあるか？
189(1): 帰納と類比 2011/04/05(火) 21:59:10.50 AAS
>>188
Ｎ−１点以下の相対グラフはわかるが、Ｎ，Ｎ−１，Ｎ-２，Ｎ−３・・・・
点のどの相対グラフか分からないので答えようがない。
１〜３はＮ−１点か
４〜６はＮ−２点か
よく分かりません。
190: 2011/04/05(火) 22:24:48.96 AAS
>>187 にも答えてもらえませんか？ > 帰納と類比
191(1): 188 2011/04/05(火) 22:56:32.17 AAS
>>189
Ｎに具体的な値を与えて、適当な大きさのグラフを想定してくれれば良いです。
1. 一通り以上。というのは良いですよね？
3.と6.は できる or できない で答えてください。
192(4): 帰納と類比 2011/04/05(火) 23:40:48.36 AAS
>>187
帰納法の仮定：Ｎ-１点までは４配色可能である。
Ｎ−２で５色目が必要になる。これが仮定と反する。
>>188>>191
1.１つ以上
2．１２個以上
3．できない
4．１つ以上
5．１２個以上
6．最終的に帰納法の仮定から言って、できない
7．最終的に矛盾はない
193: 2011/04/05(火) 23:45:42.90 AAS
>>146で「検討してみます」と言った結果が>>165>>170>>176なのかな？
自分で考える気になったのはすごい進歩だと思ったのだが…
194(1): 2011/04/06(水) 00:18:26.94 AAS
>>192
とりあえず >>187 に答えてくれてありがとう。
では、「Ｎ−２点の相対グラフがある塗分け方で
４彩色不可能」であることが、
「Ｎ-１点までは４配色可能である」に矛盾すると
あなたは考えてるんだね。
ちなみに 「N-1 点までの(任意の)グラフは4配色可能である」
の否定は
「N-1 点までの点をもつ、あるグラフは頂点をどのように
4色で塗っても塗り分けられない」
であることには同意してもらえるかな？
195(3): 帰納と類比 2011/04/06(水) 00:30:40.56 AAS
>>194
同意します。
196(1): 2011/04/06(水) 01:21:41.03 AAS
>>195
そこは同意してもらえるんだね。
では、あなたの証明とかその状況は忘れてください。
以下を全く一般の話として読んで下さい:
あるグラフが与えられたとしよう。
(1) 「そのグラフは、ある塗り方で頂点を 4色で塗ると塗り分けられない」
(2) 「そのグラフは、どのように頂点を 4色で塗っても塗り分けられない」
一般には (2) ⇒ (1) が成立するが, (1) ⇒ (2) は成立しない。
(1) と (2) は異なる主張である。
以上、同意してもらえますか？
197: 2011/04/06(水) 06:02:37.31 AAS
帰納と類比さー
>>192
で、「N-1 で 5色目が必要になる。」って書いているけど、
四色定理によれば、そんなことは起こり得ないんだけどｗｗｗ
つまり、特殊な条件のもとでは N-2 （？帰納と類比の話によれば、N-1の筈だが・・・（苦笑））
で 5色目が必要になるって言いたいんでしょ。
で、「帰納法の仮定：N-1点まではどんなグラフでも4配色可能である。」
と、どこがどう反するのさｗｗ
ちゃんと高校卒業したか？
198(1): 帰納と類比 2011/04/06(水) 06:07:57.11 AAS
>>196
同意します。
199(1): 2011/04/06(水) 10:38:05.34 AAS
>>198
そこも同意していただけますか。
では、>>192 によれば
>>帰納法の仮定：Ｎ-１点までは４配色可能である。
ですね。この「帰納法の仮定」の否定は
(a) 「N-1点までのあるグラフは どのように 頂点を塗っても4色で
塗り分けられない」
です (>>195 で同意済)。
(b) 「N-2点の双対グラフが ある 塗り方で頂点を 4色で塗ると塗り分けられない」
ことから、上で述べた(帰納法の仮定の否定である) (a) は「一般には」導かれません
(>>198 で同意済)。
いいかえると、(b) は帰納法の仮定と、「一般には」矛盾しません。
ですから >>186 の冒頭2行を読んで考えられるのは次の二つです。
(A) 説明不十分。「帰納法の仮定と矛盾する」根拠が他にある
(B) 冒頭2行の推論が間違っている
どちらですか？
(A) ならば、説明不十分なのだから追加説明もお願いします。
200: 188 2011/04/06(水) 21:25:26.63 AAS
>>192
解答ありがとうございます。
4〜6の所では背理法を適用せず、7.の所で背理法を使うようにすると
6．最終的に帰納法の仮定から言って、できない、
7．最終的に矛盾はない。
を以下のように書き換えるのは納得してもらえますか？
6. できる、
7. (3.と6.の答えが異なるので)矛盾する。(この後矛盾を解消する。)
3.はできないとの解答ですが、2.の解答と矛盾します。
2.の解答より五色で塗り分ける方法が存在すると言ってます。
「5集点は不可避集合である」ことから、五色で塗り分ける方法のどれかを選んで
いくつかの頂点の彩色を指定すれば、3.の場合も四色で塗り分けられないように
できるのは理解できますよね？
6.の場合に同様の考え方をしているはずです。
用意していた解答は、1〜2と4〜5は 一通り以上、
3.と6.は できる、
7. (1〜3の答えと4〜6の答えは同じなので)矛盾しない、
(よって、多くの人も書き込んでいたように帰納法の仮定と矛盾しない。)
でした。
201(2): 2011/04/06(水) 21:27:48.81 AAS
そもそも数学的帰納法の使い方も完全に間違ってるんだけどね＞キノウトルイヒ
「N-1で命題成立を仮定して」「Nを証明する」のが本来の帰納法でしょ。
ところが
「N-1で命題成立を仮定して」「N-2で矛盾する」とキノウトルイヒは主張している。
ということは、帰納法の仮定そのものが自己崩壊したので
帰納法による証明も成立しなくなったということになる。
(注：もちろんこれは、キノウトルイヒのおかしな主張を真に受ければ、の話だ)
202(1): 2011/04/07(木) 06:23:06.68 AAS
結局、帰納と類比が示そうとしたことは、
「N-1点までのグラフが4彩色可能」ならば「N-1点のグラフから任意の
5点を選んだとき、その5点は3色以下で塗られているような、その
グラフの4色での塗り分けが存在する」ってことでしょ。
(結果としてその5頂点と繋がっているような点を追加しても4色で
塗り分けられることが従う)
帰納法っぽく見えるから本人も錯覚してるんだろうけど、こう書くと
相当、無茶なことを示そうとしてるのが分かるよな。
(もちろん結論自体は4色定理から従うので正しいけどね)
203: 2011/04/07(木) 14:26:52.49 AAS
帰納と類比にノイキルヒが含まれていることに>>201を見て気がついた
204(2): 帰納と類比 2011/04/07(木) 18:21:55.85 AAS
>>199
>この「帰納法の仮定」の否定は
>(a) 「N-1点までのあるグラフは どのように 頂点を塗っても4色で
>塗り分けられない」
>です (>>195 で同意済)。
Ｎ−２点のあるグラフは どのように 頂点を塗っても4色で
塗り分けられない、と言ってるつもりです。
よって(a)の命題と同一と捉えています。
ケンペ鎖が塗りわけ手法の全てをカバーするなら、です。
>>201
言ってる意味が良く分かりません。Ｎ−１点からＮ点に帰納してます。
>>202
>帰納法っぽく見えるから本人も錯覚してるんだろうけど
錯覚とはどこをどの様に錯覚しているんでしょうか？
205(2): 2011/04/07(木) 19:33:25.35 AAS
>>204
Ａ「N-1点までのすべてのグラフで四色定理が成立する」
Ｂ「N-2点のあるグラフで四色定理の反例がある」
・ＡとＢは矛盾するので、どちらか一方は必ず間違いです。
・帰納と類比はＢの成立を主張しています。
・もし主張が正しいとすれば、背理法によりＡが否定されます。
・Ａは帰納法の仮定なので、これを否定してしまうと[N-1]→[N]の帰納法が使えなくなります。
・ということは本来の四色定理の帰納法による証明(N以降)もすべて無効になります。THE END
206: 2011/04/07(木) 19:35:50.93 AAS
球の中に立方体が内接している
その立方体の中にも球が内接している
立方体の外側の球と内側の球の体積比を文字を使い求めよ
ただし外側の球の半径をa、内側の球の半径をb、立方体の1辺の長さをcとする
207: 2011/04/07(木) 21:21:51.19 AA×
208(1): [age] 2011/04/07(木) 21:23:26.79 AA×
209(2): 帰納と類比 2011/04/07(木) 21:55:08.92 AAS
>>205
Ｂの成立は矛盾するからＡとなり、帰納法は成立します。
Ｂの成立はαパターンで成立するが、βパターンで不成立となる。
αパターンはＡＣ、ＡＤチェーンが繋がっているとき。
βパターンはＡＣ、ＡＤチェーンのいずれか一方が切れているとき。
Ａが成立するためβパターンが存在すると結論付けてます。
210: 2011/04/07(木) 22:35:23.77 AAS
「どのように塗っても」じゃねえじゃん。
言葉の使い方が不正確すぎる。
211(2): 2011/04/08(金) 00:16:32.06 AAS
>>209
> Ｂの成立はαパターンで成立するが、βパターンで不成立となる。
Ｂが成立するパターンがたった一例でもあれば、
それがＡへの反例になりますのでＡは成立しません。
> Ａが成立するためβパターンが存在すると結論付けてます。
すべてのパターンでＡが成立してくれなければ、帰納法の仮定になりません。
帰納法は一般的証明の土台なので、例外があってはならない。
もし例外があれば、例外パターンについての四色定理の別証明が必要になります。
あなたの主張を要約すれば、
「四色定理が成立しないグラフは存在する(αパターン)が、
しかし四色定理はすべてのグラフで成立する(帰納法による結論)」
ということになるのですが、これは自己矛盾命題になります。
212: 2011/04/08(金) 02:44:57.62 AAS
ようするにαパターンとβパターンの２つの道を作ることで、
うまく「逃げ道」を作ったつもりなんでしょ。帰納と類比さんは。
ところがαやβによって作られたグラフはどちらもN-1以内のグラフですから、
これら双方が四色定理を満たさなければ帰納法の仮定Ａに反します。
Ｂがαパターンで成立すると>>209で明言したので、
結果的にαで仮定Ａは成立せず、帰納法も崩壊しました。
213: 2011/04/08(金) 14:11:54.90 AAS
>>204
>ケンペ鎖が塗りわけ手法の全てをカバーするなら、です。
私にはこの表現は曖昧で理解が出来ません。
「ケンペ鎖が塗りわけ手法の全てをカバーする」が意味することを厳密に述べ、
何故それが成立するのかを証明し、そのことを用いて
(b)「N-2点の双対グラフが ある 塗り方で頂点を 4色で塗ると塗り分けられない」
ことから、どのような根拠で
「N-2点のあるグラフは どのように 頂点を塗っても4色で塗り分けられない」
ことが従うのかを説明してください。
214(3): 帰納と類比 2011/04/08(金) 20:13:02.78 AAS
>>205>>211
Ａが成立すると仮定する。
Ｂ＝αパターンが成立しない。（Ａに矛盾するため）
よって
βパターンが成立し、Ａが成立する。（αとβで全ての配色を示す）
では駄目ですか？
215(1): 2011/04/08(金) 21:14:04.41 AAS
>>214
そんなの駄目に決まってます。
Ａ「N-1点までのすべてのグラフで四色定理が成立する」
「N-1点までのすべてのグラフ」の中には当然αパターンは存在します。
(なぜならαパターンはN-1点以内のグラフなので、定義から明らか)
αパターンを除外したければ、それが
「N-1点以内のグラフでないこと」を示す必要があります。
(それはαパターンの作り方に反する)
何度も言うようですが、仮定Ａか主張Ｂのどちらかは必ず間違いです。
主張Ｂが矛盾すると言いながら、しっかり主張なさってるのはあなたですよ。
216(1): 2011/04/08(金) 21:15:38.38 AA×
>>214
217: 2011/04/08(金) 22:22:06.01 AAS
未だ意思の疎通がとれてないようですな
218: 2011/04/08(金) 23:56:04.63 AAS
帰納と類比さん、
あなたには以下の「証明」が正しいと思われますか。
-------------------------------------
[定理]
任意の地図は四色以内で塗分け可能である。
[証明]
五色必要な地図は存在するかも知れないが、
そんな地図は四色定理に矛盾するので成立しない。(証明終わり)
-------------------------------------
>>214の主張はこれと似たようなものです。
どうしてこれが奇妙だと思えないのでしょうか。
219(1): 2011/04/09(土) 00:21:16.93 AAS
どうでもいいことだけど、
なんで MIT じゃなくて、ハーバードから数学論文だそうとしたんだろ？
別に出せないことはないんだけどね。
220(2): 帰納と類比 2011/04/09(土) 00:51:56.54 AA×
>>215>>216
221: 2011/04/09(土) 01:48:22.49 AAS
[>>95定理]IQが20以上違うと会話が成立しない
[>>95定理の派生]どのように易しく解説しても、論理を理解出来ない人が存在する。
222: 2011/04/09(土) 01:48:44.88 AAS
帰納と類比さん、あなたは「グラフ」といったとき、
頂点と辺の形だけを言ってるの？
それとも各頂点に色が付随したものを言っているの?
その二つをごちゃごちゃにして自分でも混乱してませんか?
「N-1点のグラフが4色で塗り分けられる」というときのグラフは
形だけだよね。
「ACチェーンがつながっている」とかいうのは、形だけの話じゃなくて
各頂点に色も付随して初めて決まる概念だよね。
頂点に色が付随して決まる概念でαパターン、βパターンとか分けて
形だけで決まる「4色で塗り分けられる」という概念の成立不成立を
述べている段階で根本から間違っていると思うんだけど。
223: 2011/04/09(土) 02:10:18.01 AAS
ddd
224: 2011/04/09(土) 02:42:36.99 AAS
「かれこれ３０年以上の努力が無駄に…」
という現実を認めたくないから意地になってるんだろうが、
何年かかろうと間違いは間違いだからな。
そもそも３０年以上も勉強した成果がまったく感じられない…(笑)
グラフ理論のテキストの「グラフ彩色」の章で
つまづいたまま老化しちゃったんでしょうね。なむ〜。
225: 2011/04/09(土) 09:57:58.80 AAS
カルト宗教からの脱会を説得するのが難しいのと同じだな。
一種のマインドコントロールにかかっているのかも。
226: 2011/04/09(土) 10:39:46.28 AAS
30年かかってこれだと、誤りに気づくのも30年かかるんじゃないか
227: 2011/04/09(土) 10:43:35.10 AAS
帰納と類比さんは、自分のやり方とケンプの証明を比べてみれば
問題点が分かるのでは？
ケンプは、５辺国(５集点)の周囲の塗り方を４つに分類した
1) A、C、Dいずれのケンプ鎖も繋がっていない場合
2) A-Cのケンプ鎖のみ繋がっている場合
3) A-Dのケンプ鎖のみ繋がっている場合
4) A-C、A-Dのケンプ鎖が共に繋がっている場合
ケンプは、如何なる塗り分け方であっても、ケンプ鎖を用いた色の置き換えを行えば、
４色で塗り分けられることを証明した(そして間違えた)
帰納と類比さんは、4)の場合は2),3)いずれかに変換可能だから、
(A-CもしくはA-Dのケンプ鎖が切れている彩色が存在するから)
考察する必要がないと言っているんですよね？
228: 2011/04/09(土) 13:17:35.54 AAS
ケンペの手法というのは、基本的には
「白地図の形状を保ったまま」
色の塗り替えだけを考えているわけですよね。
ところが帰納と類比の手法(笑)は
接合によって「白地図の形状を変えてしまった」
形状を変えたら以前とは全く別の白地図なのだから、
色の塗り方は全部リセットして考えてないと一般性を失う。
…と、何度も指摘されたはずですが。
ケンペの手法が解れば、証明ミスにはすぐに気が付くはず。
229: 2011/04/09(土) 14:10:17.65 AAS
馬鹿の考え休むに似たり
230: 2011/04/09(土) 16:32:40.29 AAS
>>219
どうでもいい話に付き合うのもなんだけど、
逆になぜ >>219 さんは数学論文を出すのに MIT なら
妥当と思ったの?
Studies in Applied Mathematics という雑誌は出している
みたいだけど・・・
231(2): 2011/04/09(土) 19:27:57.40 AAS
>>220
「接合」を行う条件が述べられていませんのでいくつか質問したいのですが、
220のグラフの場合だと6集点になっていますが、不可避集合をそうでない集合に
変換しても良いのですか？
220のグラフの場合でA, C, D国が細長い国でAとCおよびAとDが直接隣り合って
いる場合はACチェーン、ADチェーンがつながっていますが、AとCあるいはAとDを
くっつけた時にチェーンがなくなるので5色は必要になりません。
逆に「接合」を行うことでチェーンがつながる場合がありますが、
この時「接合」の前に色の塗り替えを行うと4色で塗ることができるのに、
塗り替えをしないで「接合」をするとつながったチェーンで制限が生じて
5色必要になる場合があります。
ACチェーンだけがつながっている5集点のAとCでの「接合」が可能だと仮定すると、
十分に長いACチェーンがつながっている5集点があって、ACチェーンの途中のAに
ADチェーンがつながっている場合にAとCでの「接合」を一回以上繰り返すと
ACチェーン、ADチェーンがつながっている5集点をつくることができます。
これらの場合をどのように考えますか？
232: 231 2011/04/09(土) 19:35:19.89 AAS
>>220
上の書き込みに関連して追加です。
ACチェーンだけがつながっている5集点のAとCでの「接合」が可能だと仮定すると、
この場合の「接合」はACチェーンを短くしているだけです。
このことを拡張して「亜接合」を定義します。
「亜接合」は5集点における以下のような操作のことを言う。
1. ACチェーンがつながっている場合は、AとCの2点をくっつける。
ADチェーンがつながっている場合は、AとDの2点をくっつける。
2. ACチェーン、ADチェーンが共につながっている場合は、A, C, Dの3点をくっつける。
更に2つのAを1つにくっつける。
「亜接合」だと220のグラフのように6集点にならないので繰り返し適用できます。
よって、「亜接合」をACチェーン、ADチェーンが共につながっている場合に繰り返し
適用するとどちらかのチェーンを切断することができ4色で塗ることが可能になります。
しかし、チェーンを短くしていったら切断できたので証明完了といった主張が
認められないのは明らかです。
「亜接合」の場合はチェーンを切断しない限りはグラフの色とチェーンの配置に
影響を与えないことは簡単に確認できます。
チェーンを切断しない限り「亜接合」を使っても塗りわけに必要な色の数が
変化することはないので、この場合は使ってもよいことが分かります。
「接合」を使ってもよいという根拠を教えてください。
233: 2011/04/09(土) 21:12:07.02 AAS
＞「∃と∀の区別なんかはどうでもいい」って思ってるだろ？
「確かに、文字をひっくり返すのに
左右をひっくり返すか上下をひっくり返すかは
些細なことだね。」
なんてマジで返しそうだｗ
234: 2011/04/09(土) 21:13:43.10 AAS
＞「かれこれ３０年以上の努力が無駄に…」
そもそも「努力すれば報われる」という考えが間違ってるわけだがｗ
235(4): 帰納と類比 2011/04/09(土) 21:16:47.33 AAS
Ｎ-１点以下のグラフは４配色可能であると仮定する。（仮定は真に正しい）
その中の任意の５集点の中央の頂点と辺を削除し、配色する。
ＡＣ、ＡＤチェーンが繋がったグラフでＡとＣまたはＡとＤを接合する。
このＮ−２点の相対グラフでこの塗分け方で５色目が必要であるが、
帰納法の仮定に矛盾するので矛盾しない４配色が１つは存在する。
このとき５集点の周りの５頂点は３色に配色できて
中心の頂点を戻してＮ点P0を４色目に配色できる。
よってＮ−１点まで４配色可能ならＮ点も４配色可能である。
よって平面上のグラフは４配色可能である。
詳細は>>1による。
以下、否定的な人も肯定的に見てください。
236: 2011/04/09(土) 21:18:25.60 AAS
＞ケンペ鎖が塗りわけ手法の全てをカバーするなら
実際にはケンペ鎖で塗りわけられない地図が塗りわけられるから、
ケンペ鎖ではカバーされない塗りわけ手法がある。
237: 2011/04/09(土) 21:22:37.00 AAS
>>235
＞否定的な人も肯定的に見てください。
数学に求められるのは
「肯定的な人も否定的に見る」
ということ。
自分の証明が間違ってると思って読める
マゾヒストになれない人には数学は無理
238: 2011/04/09(土) 22:18:17.45 AAS
>>235
>このとき５集点の周りの５頂点は３色に配色できて
P2,P4,P5とP1-P3で4色使うだろ。最初のP2とP5が同色という仮定は
>帰納法の仮定に矛盾するので矛盾しない４配色が１つは存在する。
この時点で捨てなきゃならん。
逆に言えば、上記の仮定を満たす4彩色が存在することは証明されていない。
239: 2011/04/09(土) 22:56:19.33 AAS
>>1こんな駄論文より
まだ力ずくで検査したほうが断然マシ。
「少なくともＮ国までの地図は確実に四色塗分け可能」とは言えるから。
帰納＆類比は四色塗分け可能とも不可能とも取れる主張してるから
意味が分からなくなるだけだ。
精神病院であうーあうー言ってるのと同じだ。
240(2): 1/3 2011/04/10(日) 05:12:54.19 AAS
>>235
論点を明確にするために「肯定的」に読んで、曖昧なところを
自分なりの理解で可能な限り明確にしてみたよ。
一応、先に書いておくけど帰納と類比の「証明」なるものは
証明になっていないと思っているけどね。
第1部:
(a) N-1点までの頂点をもつ任意のグラフは(色 A, B, C, D
の4色を用いて)4配色可能
と仮定する。
N点の頂点を持つグラフ G で5集点をもつようなものを考える。
(b) G が4配色可能である
ことを示したい。
G の(任意に選んだ)5集点の中央の頂点と辺を削除して
得られるN-1 点のグラフを G_1とする。
また中央の点とつながっていた頂点を p1〜p5 と名付ける。
(a) より G_1 は4配色可能である。そこで
(c) G_1 の4配色のうち, p1〜p5を3色以下で塗るものが
存在する
ことを背理法を用いて示す。もし (c) が成り立てば
(b) は容易に従う。
241(3): 2/3 2011/04/10(日) 05:14:53.09 AAS
第2部:
(c) が成り立たない, すなわち
(d) G_1 の任意の4配色は p1〜p5 を塗るのに4色を用いる
と仮定し, 矛盾を導く。
言葉をひとつ用意する。
グラフ G_1 の4配色がひとつ与えられたとき, A色で塗られていた
頂点をB色で, B色で塗られていた頂点をA色で塗り替えても、
やはり G1 の4配色になる。
このようにグラフG_1 の4配色 f_1 と f_2 があったとき、
f_1 のA,B,C,D を入れ替えて f_2 が得られるなら、f_1 と f_2 は
「同値な4配色」と呼ぶ。
(d) は次と同値である:
(e) G_1 の任意の4配色 f に対して, それと同値な4配色で p1〜p5
を塗るのに4色を使い, さらにB色を2回用い, ACチェーンと
ADチェーンがつながっているものが存在する
実際 (e) ならば (d) は明らか。
(e) が成り立たなければ, Kempe の手法に従えば, p1〜p5 を3色以下
で塗る方法が得られる。すなわち (d) が成り立たない。対偶をとれば
(d) ならば (e) が示された。
なお「ACチェーンがつながっている」とは, 例えば p1 が A色, p3が
D色で塗られているとき, p1 から出発して A--> D--> A--> D のように
頂点を辿っていって p3 に到達できることをいう
242(2): 3/3 2011/04/10(日) 05:17:51.21 AAS
第3部:
さて (e) から矛盾を導く。
f を G_1 の任意の4配色とする。このとき(e)より f と同値な
G_1 の4配色 g で p1〜p5を塗るのにBを2回用い, さらに
ACチェーンとADチェーンがつながったものが存在する。
4配色 g でG_1を塗ったとき p1〜p5 のうちA色とC色が塗られた
2頂点を同一視して得られるN-2点のグラフを
G_2とし, 同一視して得られた頂点を p6 と名付ける.
(一般に G_2 は4配色 g に依存して別のグラフとなることに
注意)
G_2 のp6以外の頂点は g を用いて配色する。すると p6 と
辺でつながった頂点を塗るのにすでに4色が用いられている。
したがってこのように塗った場合, p6 を塗り分けるのに
5色目が必要となる。
(巨大なギャップ)
したがって G_2 の塗り分けには常に5色必要である。
G_2は(a)より4配色可能なのでこれは矛盾である。
(証明終わり)
さて、帰納と類比さん、巨大なギャップを埋めてよ。
243(2): 2011/04/10(日) 05:25:30.93 AAS
>>241
>なお「ACチェーンがつながっている」とは, 例えば p1 が A色, p3が
>D色で塗られているとき, p1 から出発して A--> D--> A--> D のように
>頂点を辿っていって p3 に到達できることをいう
誤) 「ACチェーンがつながっている」
正) 「ADチェーンがつながっている」
失礼。
244(2): 2011/04/10(日) 12:46:01.39 AAS
五色必要を回避するためには少なくとも片方のチェーンは切れるという主張だが
チェーンを切らずに>>145のように塗り替えられる可能性もないわけではない。
>>145では
B---○---B を A---○---A に替えたが、今度は
B---○---B を D---○---C に替えることを考えてみる
この塗り替えは「絶対に」できることが保証される。
なぜなら、塗り替え前の左のB色はACチェーンに囲まれているので、
左のB色から始まるBDチェーンはDBチェーンに替えられる。
同様に、塗り替え前の右のB色はADチェーンに囲まれているので、
右のB色から始まるBCチェーンはCBチェーンに替えられる。すると、
B---○---B を D---○---C に替えることをができて、
真ん中の○にB色を置けば、周囲の色と衝突しない。
よってチェーンを切らずに四色塗り分け可能が示された。THE END
245: 2011/04/10(日) 13:29:31.39 AAS
>>244
それって、ケンペがこけたのと同じところでこけてないか？
246(4): 帰納と類比 2011/04/10(日) 14:03:11.28 AAS
>>244
ケンペの誤りと同じミスをしています。
>>240-243
私の頭脳では分かりません。
247: 2011/04/10(日) 14:38:07.14 AAS
>>246
＞私の頭脳では分かりません。
なら、4色問題は証明できないな。
論理が分からないんだから。
248(1): 2011/04/10(日) 15:34:02.61 AAS
>>246
ここで敗北宣言か、残念。
あと700レス以上あるし、自分の「証明」がどう間違っていたかを
考察するのもいいんじゃないだろうか。
249(1): 2011/04/10(日) 16:01:02.96 AAS
とりあえず帰納と類比さんは放置しておいて>>147さんへのレス
証明そのものは検証していないのですが、
1)3正則な平面地図
2)5辺国以下の組み合わせ
は「数え上げの公式」から有限しかないので、
総当りで調べられるのでは？と思います。
250(1): 帰納と類比 2011/04/10(日) 18:44:51.19 AAS
>>248>>all
５色目が存在しても矛盾じゃないと、指摘されればお手上げです。
白紙から塗りなおせば４配色できると指摘を受けたし。
ここでこの証明は誤りでしたと言っておこう。
残念でした。
上下前次1-新書関写板覧索設栞歴
あと 529 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.932s*