[過去ﾛｸﾞ] ☆四色問題の簡単な証明その３☆ (779ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
28(1): 帰納と類比 2011/03/20(日) 00:42:34.59 AAS
>>25
>(P1, P2, P3, P4, P5） の色が、（A, B, A, C, D）だった場合、接合とは、
①具体的に、P1～P5 を、２枚目のP1～P4にどう対応させるのですか？
（Ｐ５、Ｐ１、Ｐ２、Ｐ３、Ｐ４）の色が（Ａ、Ｂ、Ａ、Ｃ、Ｄ）と置き換えればいい。
>②接合後の、（P1, P2, P3, P4）の色を教えてください。
（P1, P2, P3, P4）は（Ａ，Ｅ，Ａ，Ｃ）となります。（ＢＤチェーンが繋がってる場合）
この場合、５色目のＥが必要になります。Ｎ－１点以下は４配色可能という仮定と矛盾しますが。
29(1): 2011/03/20(日) 00:49:59.29 AAS
>>28
えーと、多分接合については理解できました。
ただ、一つ疑問点が出てきました。
接合を行うことで、５色目を使うことが必要になる（こともある）のですが、
この「５色目が必要」ということは、別に４配色可能であることと矛盾はしません。
接合するときは、
接合する２頂点の色以外の頂点の色は変えないこと…①を前提としております。
（>>27で言えば、P2とP5を、色Eにしただけで、他の全頂点の色は変えない事を前提としている。）
従って、上手く色を付け直せば、４色で塗り分けることが可能だとしても、
「①の前提では、５色必要になる」と言うことはありえます。
これについては、どのようにお考えなのでしょうか。
30(1): 帰納と類比 2011/03/20(日) 01:24:41.04 AAS
>>29
>従って、上手く色を付け直せば、４色で塗り分けることが可能だとしても、
「①の前提では、５色必要になる」と言うことはありえます。
チェーンの拘束があれば、５色必要になり、矛盾を生じる。
うまく色を付け直せば、チェーンは切れて、５点（P1，P2，P3，P4，P5）はＥを除く３配色可能となる。
ＢＣチェーンとＢＤチェーンが両方繋がっている場合しか存在しないと矛盾を生じる。
31(1): 2011/03/20(日) 01:32:33.61 AAS
>>30
いえ、だから、
「特定の条件下では５色以上必要な事がある」ことは、
「４配色可能である」という仮定に矛盾しません。
例えば、証明の１ページにある、５つの頂点のグラフだけを考えてみます。
（配置とかではなくて、単に５つの頂点のグラフです。）
この時、何の制約もなければ、４配色可能なグラフであることは明らかです。
ただし、「P1をA, P2をB, P3をC, P4をD とする」というような制約がある場合、
５色目が必要な事は明らかです。
ある特定の条件では５色以上必要なグラフでも、
全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
そのグラフは４配色可能であります。
言っていることは伝わっているでしょうか？
32(1): 帰納と類比 2011/03/20(日) 02:00:12.18 AAS
>>31
５色必要なグラフが１つでもあれば、４配色可能に矛盾します。
>全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
そのグラフは４配色可能であります。
うまく配色し直しても、ＢＣチェーンとＢＤチェーンの両方が切れないと反例が生じます。
その事が矛盾になります。
ここの部分の考え方が、異なるようですね。
33(1): 2011/03/20(日) 02:14:00.68 AAS
>>32
考え方の問題じゃない気が・・・
まぁ、貴方はあなたの信じる証明を
論文でもなんでもして、お出しになってはいかがでしょうか。
一応、あなたの証明の間違いだと思われる部分を、ハッキリと書いておきます。
――――――――――――
部分グラフの頂点の彩色に、一定の条件…①を課して
５色目が必要になったことをもって、
「４配色可能」であることと矛盾する。
という論法を、何の証明もなく使っているが、
実際は、①の条件下で５色目が必要だとしても、
「４配色可能」であることは有り得るわけで、
何も矛盾はしない。
――――――――――――
良く考えなおしてみてください。
34(2): 2011/03/20(日) 02:22:15.14 AAS
2年前のスレと同じ展開だったな
35(1): 2011/03/20(日) 10:56:44.20 AAS
独り善がりとはこの事だなｗ
36(2): 帰納と類比 2011/03/20(日) 11:16:43.21 AAS
>>33
１年前と同じ展開になりましたね。
>ある特定の条件では５色以上必要なグラフでも、
>全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
>そのグラフは４配色可能であります。
「そのグラフは４配色可能であります。」の根拠はどこにありますか。
まだ４配色可能と決まっているわけではありません。
５配色が可能ならわかりますが。
５配色が必要なグラフが存在するということを矛盾の根拠にしています。
そのグラフをうまく配色しなおしても、４配色可能ということは出来ません。
任意のグラフ全てが４配色可能だと言っているようなものです。
>>34 そうみたいですね。
37(3): 2011/03/20(日) 12:12:23.94 AAS
>>36
４色配色可能な根拠って・・・
貴方が、一番初めに、「N-1個の頂点は４配色可能であるとする」
と仮定したんでしょ。多分、帰納法したかったんでしょ。
その後、なんか「接合」とかいう訳の分からない操作をした結果、
一時的にでも５色目を使った。
そして、その結果として、始めに「４配色可能であるとした仮定に矛盾する」とした。
そもそも「矛盾したから何をいいたいのか？？仮定が偽であるといいたいの？」
等という根本的な疑問はおいておいて、
「接合という操作の結果」５色目が必要になることと、
４配色可能であることは別に何も矛盾しない。
これ以上言ってもわからないようだったら、もうあきらめろよ。
――――――――
ちなみに、>>34,35は私じゃないからね。
>>34,35に完全に同意はしてるがｗ
38(2): 帰納と類比 2011/03/21(月) 23:37:20.50 AAS
>その後、なんか「接合」とかいう訳の分からない操作をした結果、
>一時的にでも５色目を使った。
接合を使って５色目を使ったので、Ｎ－１点以下は４配色可能という仮定に反すると結論付けました。
反例を一時的発生させて、４配色可能という仮定に矛盾するから、別の配色があって仮定と矛盾しないと
結論を導きました。それがＡＣチェーンあるいはＡＤチェーンが切れているグラフが存在すると結論付けました。
これはＮ－１点でP1，P2，P3，P4，P5が３配色可能と結論付けました。
従って、５集点は可約と結論付けました。
接合を使ったのは反例を導き出したかったからです。
接合はグラフではコントラクト（縮約）で普通の操作です。
>>37 これ以上言ってもわからないようだったら、もうあきらめろよ。
諦められません。
この辺が理解できる人いませんか。
39(1): 2011/03/22(火) 00:05:17.37 AAS
いませんか、じゃなくてあんたが理解しなきゃならないんじゃないの？
>接合を使って５色目を使ったので、Ｎ－１点以下は４配色可能という仮定に反すると結論付けました。
>>37は、それが結論付けられないと言っている。
40(1): 2011/03/22(火) 06:33:49.04 AAS
>>38
最初 N-1点までの地図が塗りわけ可能と仮定して、矛盾を導いたと主張してるんだよね？
そうすると、たとえば N=10 とすると 、9点以下の地図の中に反例が存在するはず
これのおかしさは分かる？
41(2): 帰納と類比 2011/03/22(火) 18:03:36.84 AAS
>>40
Ｎが小さいときには、手作業で確認できるから、反例は存在しない。
Ｎが大きくなると確認のしようがないから、チェーンで確認する。
ＡＣチェーンとＡＤチェーンの片方が繋がってないと証明するには
両方が繋がっているとＮ－２点で５色目が必要になって、仮定と
矛盾すると言うしかない。この作業は数学的には当然のことと思います。
42: 2011/03/22(火) 18:19:40.01 AAS
数学以外の世界ではそうなの？
43(1): 2011/03/22(火) 18:23:30.86 AAS
>>41
そもそも、「背理法」なの？それとも、「帰納法」なの？
44(1): 帰納と類比 2011/03/22(火) 20:32:07.76 AAS
>>43
背理法を使った帰納法です。
５色目が必要になるが背理法で、全体は帰納法です。
45: 2011/03/22(火) 20:48:35.45 AAS
>>44
背理法の「５色目が必要になる」を先に仮定したの？
「頂点がN-1個のグラフを４配色可能とする」を先に仮定したの？
46: 帰納と類比 2011/03/22(火) 22:30:16.83 AAS
「頂点がN-1個以下のグラフを４配色可能とする」を先に仮定しました。
47(1): 2011/03/23(水) 22:50:25.14 AAS
>>41
つまり、手作業で確認できないくらい巨大な地図には反例が存在するわけね？
そうすると、4色定理を証明したんじゃなくて、
4色定理が正しくないってことを証明したわけだ
48(1): 帰納と類比 2011/03/24(木) 00:54:53.53 AAS
>>47
>巨大な地図には反例が存在するわけね？
Ｎ－１点以下では背理法で矛盾すると言ってる訳で
巨大な地図にも４配色可能だと言っています。
分からないかなこの論理。
49(1): 2011/03/24(木) 01:18:10.12 AAS
>>48
「N-1点以下の地図が塗りわけ可能と仮定して矛盾を導いた」
のなら、当然、N-1点以下の地図に塗りわけ不可能なものが存在する
つまり、反例が存在するということになる
50(1): 帰納と類比 2011/03/24(木) 02:00:57.81 AAS
>>49
矛盾するといっても最初のＮ－１点以下は４配色可能と仮定してるので
ＡＣチェーンあるいはＡＤチェーンのいずれか切れていて、矛盾は解消される
と言いたいんだが。分かりますか。背理法で矛盾は誤りであると結論付けています。
51(1): 2011/03/24(木) 02:21:59.35 AAS
>>50
A～CとA～Dが両方ケンペ鎖でつながってることなんて珍しくないと思わないか？
つながってる例はいくらでも構成できるんだけど
それとも、手作業で確認できないくらい巨大な地図だと絶対に切れてるの？
52(2): 帰納と類比 2011/03/24(木) 21:46:20.85 AAS
>>51
Ｎ－１点以下のグラフではＡＣチェーンかＡＤチェーンのいずれか一方は切れてる
配色が１つ以上存在することを述べている。
それが背理法で証明できた、と言っている。
両方繋がっているグラフも存在するかもしれないが、片方切れているグラフは
必ず存在すると証明している。
もし両方繋がっているグラフしかなければコントラクト（接合）して５色目が
必要になるが、背理法の仮定で４配色可能としているのでＡＣまたはＡＤチェーン
のいずれか一方のチェーンは切れている配色は１つは存在することになる。
53(1): 2011/03/25(金) 00:22:38.74 AAS
>>52
> 両方繋がっているグラフも存在するかもしれないが、
だから、両方つながってる場合は、それが4色定理の反例になるはずでしょって聞いてるんだけど
54(1): 帰納と類比 2011/03/25(金) 00:54:29.53 AAS
>>53
両方繋がっている場合は有るかも知れないが、Ｎ－２点で反例が生ずる
ことになるので、Ｎ－１点以下では４配色可能と言う仮定に反する。
Ｎ－２点で反例は無いので（仮定より）、全ての配色でＡＣまたはＡＤ
チェーンの片方または両方の繋がっていないグラフは１つは存在する。
55(1): 2011/03/25(金) 01:23:07.11 AAS
>>54
あるかもしれないが、仮定に反する とか言われても何言ってるか分からん
・両方つながってる場合はあるかもしれない(ないとは言えない)
・両方つながってるとしたら、仮定に反するので、両方つながってることはありえない
のどっちなのかはっきりして
56(2): 2011/03/25(金) 02:13:49.95 AAS
>>52
あるグラフが四彩色可能であるとき、そのグラフに「接合」という操作を行った
ものが常に四彩色可能であることが証明されていなければ、その矛盾は
導けないと思うが？
つか、「接合」すると五色必要になると言っているんだよな？
57: 2011/03/25(金) 02:30:08.10 AAS
>>56
> 四彩色可能であることが証明されていなければ、
N点より小さいグラフが4彩色可能なことは数学的帰納法の仮定だから、
そこは別にいいんじゃないか？
58(1): 帰納と類比 2011/03/25(金) 04:43:04.34 AAS
>>55
>・両方つながってる場合はあるかもしれない(ないとは言えない)
が正しい。
しかし、背理法により片方が切れているグラフは１つは存在する。
>>56
ＡＣまたはＡＤチェーンが両方繋がっている配色しか存在しないと
したら、５色目は必要であるが、帰納法の仮定でＮ－１点以下は
４配色可能だから、仮定と矛盾する。よってチェーンのどちらかが
切れている配色が１つは存在する。
59: 2011/03/25(金) 07:34:02.26 AAS
まだ頑張ってるの？（笑
60: 2011/03/25(金) 09:42:54.74 AAS
>>58
少なくとも一方が切れてる場合は、
ケンペと同じ論法でもとのN点のグラフが塗り分けられるからOK
こっちは問題にしてない
両方つながってる場合は、>>6 の理屈だと、「接合」を行ったN-2点のグラフは
塗りわけ不可能で、>>58 によればこの可能性は排除できない
つまり、塗り分けられる場合もあるけど、塗り分けられないグラフが存在する
可能性は排除できない
これじゃ証明になってないじゃん
61(1): 帰納と類比 2011/03/25(金) 18:49:25.92 AAS
ある任意のグラフでＮ－１点以下のグラフは４配色可能な配色が１つは
存在するということ。
>・両方つながってる場合はあるかもしれない(ないとは言えない)
は全ての配色を言っているのではない。片方切れている配色が必ず存在する。
62(1): 2011/03/25(金) 20:12:09.18 AAS
不可避集合って何？
グラフ理論のお勧めの数学書を教えてくだされ。
63(1): 帰納と類比 2011/03/25(金) 22:12:35.28 AAS
>>62
ロビン・ウィルソン著 茂木健一郎訳
「四色問題」
P176
不可避はその中の少なくとも１つが全ての地図に現れるような配置の集合。
64: 2011/03/25(金) 22:32:49.23 AAS
茂木健一郎って脳タレの人？
65: 帰納と類比 2011/03/25(金) 22:36:34.15 AAS
多分そう。
66(1): 2011/03/25(金) 23:32:30.37 AAS
>>63
誤解されても仕方ない表現だなそれ
67: 2011/03/25(金) 23:38:58.88 AAS
62ですが、数学書のほうではどれがお勧めでしょうか？
茂木のやつは読み物で、数学専門書ではないと思うのですが。
（今度読んでみますが）
グラフ理論入門 R.J. ウィルソン とかお薦め？
みなさんはどの本で勉強したのですか？
68: 2011/03/26(土) 13:03:59.24 AAS
>>66
確かに誤解されても仕方ない表現だね。
そもそも茂木健一郎って、数学者じゃないでしょ。
69: 2011/03/26(土) 14:56:10.77 AAS
いくらモギケンが馬鹿でもそんなこと書かないでしょと思って見たら、
本当に書いてあった…
70(1): 2011/03/26(土) 15:08:20.83 AAS
>>61
最初にN点未満の地図が塗りわけ可能として、A～C、A～D が両方ケンペ鎖でつながっているとしたら矛盾を生じる
って論理を仮に認めたとしても、ここから言えることは、
「N点未満の地図に反例が存在する」かまたは
「A～C、A～D のケンペ鎖は少なくとも一方が切れている」
ということでしかない
71(2): 帰納と類比 2011/03/26(土) 21:00:27.56 AAS
>>70
与えられた任意のグラフはＮ－１点以下で４配色するのに幾つかの塗り方があって
そのなかに反例のような配色もあるが、ＡＣあるいはＡＤチェーンの切れている
塗り方が１つは存在するということ言っている。
従って、「A～C、A～D のケンペ鎖は少なくとも一方が切れている」配色が必ず１つは
存在する。
72(1): 2011/03/26(土) 21:33:05.98 AAS
>>71
もし、A～C、A～D が両方ケンペ鎖でつながっているとしたら、
そのグラフで「接合」を行った N-2点のグラフは、4色で塗り分けられるのか、塗り分けられないのか、
yes か no かで答えてくれないか？
73(2): 帰納と類比 2011/03/26(土) 22:55:14.08 AAS
>>72
塗り分けられない。
がＮ－２点のグラフは４配色可能なので、仮定と矛盾し、別の塗り分けられる
配色が必ず存在する。この背理法は以前から何度も説明してきた。
74(2): 2011/03/26(土) 23:19:17.68 AAS
>>73
> 塗り分けられない。
> がＮ－２点のグラフは４配色可能なので、
N-2点のグラフは塗り分けられないが4配色可能、つまり塗り分けられるのか？
何言ってるか分からないんだが
75(1): 2011/03/26(土) 23:20:44.96 AAS
>>71
AからEまでの配色も任意という条件でA-C間がケンペ鎖で繋がっていない
配色なら当然存在し得るだろうが、それでは証明にならない。
一方で、何度も指摘されていることだけど、AおよびCに隣接する頂点の配色を
変更しないという条件で「接合」した結果5色目が必要になったとしても、N-1以下の
グラフが四彩色可能であることとは矛盾するとは言えない。
76(1): 帰納と類比 2011/03/26(土) 23:49:48.82 AAS
>>75
>AおよびCに隣接する頂点の配色を
>変更しないという条件で「接合」した結果5色目が必要になったとしても
変更してもよい。変更しても５色目が必要になる。
この辺は５集点をもとに再度考察してみてください。
少しややこしくなります。
77: 2011/03/26(土) 23:55:00.66 AAS
Mr．Shiraishi が大昔に解いてただろ
78(2): 2011/03/26(土) 23:59:40.34 AAS
考察してくださいも何も、なぜそうなるのかどこにも説明してないじゃん。
「AとCを接合すると5色になるので」って一言で済ませているけど、
それが無条件に成立すると言うのならそれを証明しないと。
79: 帰納と類比 2011/03/27(日) 00:15:22.95 AAS
>>78
その証明を追加すると別のグラフが必要で、うｐロダでもう１ページ追加
しなければうまく証明できない。言葉だけではうまく説明できない。
隣接する頂点の色を変えても、証明できる。
あなたにはそれを理解する能力が有りそうなので、考察してください。
80: 2011/03/27(日) 00:21:32.21 AAS
「すべての平面的グラフは四彩色可能です。考察してください。」ってんじゃ
証明したことにはならないぞ。
81(1): 2011/03/27(日) 00:23:58.65 AAS
>>74 に回答してもらいたいんだが
82(1): 2011/03/27(日) 00:28:58.03 AAS
>>76
変更してもよい？AとCだった頂点の配色を変更して同色にできるなら
5色目は必要ないが？
83(1): 2011/03/27(日) 00:40:18.19 AAS
>>81
このスレは、>>37-39で完了している。
帰納と類比が、論理を理解できないのが問題。
84: 2011/03/27(日) 00:50:37.25 AAS
>>83
間違ってることを本人に理解させようっていうゲームが進行している
85(1): 帰納と類比 2011/03/27(日) 00:50:38.59 AAS
>>74
ＡＣとＡＤチェーンが結ばれているときは塗りわけできない。
５色目が必要になる。しかし仮定に矛盾するので、配色の１つはチェーンが
切れているものが存在する。
>>82
スクリプトを付けてもらわないと、どの人がどのレベルかわからない。
>>78の人かな。もう少し熟慮をお願いします。
86: 2011/03/27(日) 01:20:24.27 AAS
自分の証明が正しいことを理解してもらいたい(か、あるいは間違いを正して欲しい)んじゃ
なかったのか？だったら説明が足りなくて他人に理解されない部分はちゃんと説明しないと。
それとも、単に「自分は正しい」と言いたいだけなのか？
87: 2011/03/27(日) 13:23:58.38 AAS
帰納と類比の主張は
１俺の証明は正しい
２間違ってると思ったら１を読め
ということで良い？
88: 2011/03/27(日) 13:50:23.75 AAS
無限ループ
89(1): 帰納と類比 2011/03/27(日) 21:42:34.84 AAS
どうして一人も証明を理解できないんだろう。
大学の数学科で助手以上の方居られましたらこの証明が正しいことを
理解できるだろう。学卒・現役学生じゃ無理みたい。
<<87 レスも含めて １，２でいい。
90(1): 2011/03/27(日) 21:59:50.11 AAS
グラフ理論以前に、論理に欠陥があるのだが…
91: 2011/03/27(日) 22:15:29.73 AAS
>>89
大学で教えてても間違いは間違い
92: 帰納と類比 2011/03/27(日) 22:31:12.32 AAS
>>90
欠陥は修復できそうなことか？
93: 2011/03/27(日) 22:55:59.77 AAS
「無理」って言っても (∩ﾟдﾟ)ｱｰｱｰｷｺｴﾅｲ なんだろ？意味のない質問すんなよ。
94: 2011/03/27(日) 23:53:20.48 AAS
>>どうして一人も証明を理解できないんだろう。
どうして間違っていることをあなた一人だけが
気づかないのか不思議だよ。
「特定の塗り方で5色必要になっても4色で塗れるという仮定に
反しない」
だからあなたの論法でACチェーンとADチェーンの両方が
つながっていても何の矛盾も生じない。
2年前から同じ部分の欠陥を指摘され続けているのにな。
95(3): 2011/03/28(月) 00:32:57.46 AAS
IQが20以上違うと会話が成立しないというのを読んだ事がある。
96: 2011/03/28(月) 00:39:01.49 AAS
>>95
蛸壺？
97: 帰納と類比 2011/03/28(月) 01:13:16.15 AAS
IQは１２０ですよ。普通のレベルなんだがな。
確かに会話が成立してないな。
98: 2011/03/28(月) 01:24:58.87 AAS
日本人の平均は100くらいだそうですから
ボンクラとは会話が成立しないのも無理ありませんね
こう思われたかったのかしら
99: 2011/03/28(月) 02:38:21.32 AAS
このスレの読者は一人を除くと140以上なのか
100: 猫は何も出来ない ◆MuKUnGPXAY [age] 2011/03/28(月) 03:27:29.30 AAS
いや、ワシは100以下や。安心せい。
猫
101: べ 2011/03/28(月) 05:18:16.73 AAS
俺180ぐらいあった気がする
まあ、神童と言われていたから妥当か…
102: 2011/03/28(月) 05:56:24.89 AAS
藤原一宏教授の虚偽申請は、日本の数学界に対する国民の信頼を裏切った、
無視することのできない重大な事件です。このような者がのうのうと責任ある教授職を
続けていることに、藤原氏がプロの学者であることを自覚しているのなら
なおさら疑問をかんじざるを得ません。今後二度とこのような事件が起きないように
するためにみなさんで建設的な議論をしましょう。
103(1): 2011/03/28(月) 06:05:35.27 AAS
帰納と類比の証明見て、別証明法考え付いたぜ！
【４色定理の証明】
①N-1個の頂点のグラフでは、４色塗り分け可能だと仮定する。
②全ての極大平面グラフは、３集点、４集点、５集点のグラフのいずれかを部分グラフとして含む。
③３集点を部分グラフとして含む場合、中央の点を除いたグラフを４色で塗り分けで、中央の頂点を
その３つの隣接点とは別の色で塗り分ければいい。
④４集点、５終点についても、③と同様に、中央の点を除いたグラフについて、４色を使って塗り分ける。
そして、中央の点を戻す際、その４つ、５つの隣接点と違う色で塗ることが出来れば、問題ない。
⑤④において、隣接点と違う色で塗ることが出来ないのは、①と矛盾する（笑。だから考えなくていい（爆
⑥よって、全てのグラフは、４色塗り分け可能である(｀・ω・´)キリッ
帰納と類比には、この証明法が正しいと理解できるはずだ！
104: 2011/03/28(月) 06:28:16.66 AAS
藤原一宏教授の虚偽申請は、日本の数学界に対する国民の信頼を裏切った、
無視することのできない重大な事件です。このような者がのうのうと責任ある教授職を
続けていることに、藤原氏がプロの学者であることを自覚しているのなら
なおさら疑問をかんじざるを得ません。今後二度とこのような事件が起きないように
するためにみなさんで建設的な議論をしましょう。
105(1): 2011/03/28(月) 13:15:26.26 AAS
>>36
>そのグラフをうまく配色しなおしても、４配色可能ということは出来ません。
↑
「うまく配色しなおせば４配色可能である」ことが「４配色可能」の定義そのものなんだよ。
グラフ理論の基本事項を完全に誤解してるじゃないか。
>任意のグラフ全てが４配色可能だと言っているようなものです。
↑
だからそれを証明しろってのが四色問題の定義だろ。
問題そのものを否定してることに気づいてるか。
自分の「証明もどき」に都合のいいように勝手に定義を変える。
これはトンデモ系によくあること。
これでよくハーバードだのIQ120だの言えるな。
世界中どこの機関に送ってもこんな論文は即却下だよ。
おそらく返事すら貰えないレベル。
106(6): 2011/03/28(月) 16:23:58.85 AAS
>>1
あなたの証明の大まかな方針は細部を以下のようなもので
あっている?
(1) N-1 個の頂点の任意のグラフは4色で塗り分け可能と仮定する.
このとき N 個の頂点を持つグラフも4色で塗りわけ可能であることを
示す. そうすれば帰納法により目的達成.
(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.
元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
この N-1 点のグラフの4色での塗り分けで以下のようなものが
存在することを示す:
「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
塗り分けられるようになっている」
単に4色で塗り分け可能であることは帰納法の仮定から分かる
ので, 塗り分けられないような都合の悪い配色はそもそも
存在しないことを背理法で示す.
(3) そのような配色になっていたとせよ. するとそこからある操作をして得られる
N-2 個の頂点のグラフの塗り分けには5色が必要になり帰納法の仮定に
矛盾する. よってそのような配色はありえない.
107(1): 2011/03/28(月) 18:51:04.57 AAS
失礼, >>106 の出だしの文章, 変だね.
誤: 細部を以下のようなもので～
正: 細部は別として, 以下のようなもので～
108(2): 帰納と類比 2011/03/28(月) 20:33:49.62 AAS
>>106
>(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
>真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.
>元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
>この N-1 点のグラフの4色での塗り分けで以下のようなものが
>存在することを示す:
>「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
>【4色で】塗り分けられるようになっている」
とは限らない。
>Ｎ－１点で>単に4色で塗り分け可能であることは帰納法の仮定から分かる
>ので, 【(a)～(e)を３色で】塗り分けられないような都合の悪い配色はそもそも
>存在しないことを背理法で示す
上記のように修正したいです。
(1)(3)はそのままでよい。
109(1): 帰納と類比 2011/03/28(月) 20:35:51.68 AAS
>>106
>(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
>真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.
>元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
>この N-1 点のグラフの4色での塗り分けで以下のようなものが
>存在することを示す:
>「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
>【4色で】塗り分けられるようになっている」
とは限らない。
>Ｎ－１点で>単に4色で塗り分け可能であることは帰納法の仮定から分かる
>ので, 【(a)～(e)を３色で】塗り分けられないような都合の悪い配色はそもそも
>存在しないことを背理法で示す
上記のように修正したいです。
(1)(3)はそのままでよい。
110(1): 帰納と類比 2011/03/28(月) 20:46:13.24 AAS
>>103
Ｎ点を戻すと仮定から反する。Ｎ－１点なら４配色可能。
111(1): 2011/03/28(月) 22:52:20.53 AAS
だったらこれならどう？
隣合う2頂点とそれを囲むサイクルを考える。
このサイクルが4彩色されている場合、この2頂点を縮約すると5色目が必要になる。
これはN-1のグラフが4彩色可能であるという仮定に反するので、隣合う2頂点を囲むサイクルは
高々3彩色であることがわかる。
3彩色のサイクルに囲まれる2頂点は、残る1色を割り当てた1頂点に縮約することができる。
以上より、隣合う2頂点は可約であることが証明できた。
112(1): 2011/03/28(月) 23:12:26.35 AAS
>>73,85
「N-2点のグラフは塗り分けられないが、4配色可能」と言ってると理解していいのか？
「塗り分けられる」と「4配色可能」ってのはどう違う？
113: 帰納と類比 2011/03/28(月) 23:23:14.82 AAS
>>111
>3彩色のサイクルに囲まれる2頂点
を縮約するのではなく、2頂点のまま3彩色のサイクルの中で４彩色
できなければ、隣合う2頂点は可約であると言えない。
縮約してしまうと、Ｎ－１点のグラフになってしまう。
114(1): 帰納と類比 2011/03/28(月) 23:32:35.18 AAS
>>112
>N-2点のグラフは塗り分けられないが、背理法後4配色可能となる
「塗り分けられる」＝「4配色可能」
115: 2011/03/28(月) 23:47:06.35 AAS
しまった、詰めが甘かったか(///)
しかしあくまでも、前段の「隣合う2頂点を囲むサイクルは高々3彩色」って
ところには突っ込まないんだなｗ
116(1): 2011/03/29(火) 01:20:30.93 AAS
>>114
背理法によって塗り分けられることを示したのは最初の N点のグラフじゃないのか？
N-2点のグラフも「背理法後」塗り分けられるようになるのか？
117(1): 帰納と類比 2011/03/29(火) 01:37:11.49 AAS
>>116
はいそうです。
118(1): 2011/03/29(火) 01:47:21.61 AAS
>>117
N-2点のグラフは塗り分けられないが、「背理法後」はその同じグラフが塗り分けられるようになるのか？
119(1): 帰納と類比 2011/03/29(火) 01:52:30.94 AAS
>>118
配色を変えて、同じグラフが４配色可能となる塗り方が１つは存在します。
120(1): 2011/03/29(火) 06:07:35.96 AAS
>>108
結局、どう修正したいの？
【4色で】 と 【(a)～(e)を３色で】 を補えばOK?
それとも下から6行目の「とは限らない」も補うの？
121: 帰納と類比 2011/03/29(火) 07:34:15.49 AAS
>>105-110
過去レスを見るにはどうしたらいいですか。
もう一回見て回答したい。
122(1): 帰納と類比 2011/03/29(火) 07:58:46.24 AAS
>>120
【4色で】 と 【(a)～(e)を３色で】
下から7行目の【とは限らない】も補う
と>「都合の悪い配色はそもそも存在しないことを背理法で示す」を削除
123: 【東電 86.0 %】 2011/03/29(火) 10:21:36.26 AAS
あ
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彩色可能である。
内部ってのはどこのこと？
上下前次1-新書関写板覧索設栞歴
あと 625 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.068s