- 相關(guān)推薦
四色定理證明題目
為尊重“聘才職業(yè)圈”這個(gè)平臺上眾多給予幫助的專家，引用此文時(shí)，請注明“來自聘才職業(yè)圈”
為了打擊我根深蒂固的愚昧和狂妄，特懸賞：第一個(gè)發(fā)現(xiàn)證明0或證明2本質(zhì)錯(cuò)誤的人，可獲得小米手機(jī)一臺，略表謝意。證明1中，有一個(gè)錯(cuò)誤，但可以彌補(bǔ)，不會(huì)影響結(jié)論。(我用的是WPS軟件，所以選擇小米。)
Hello, world!
I am becoming a machine.
本文所說的圖都是指平面圖。
方法0：
方法1：
數(shù)學(xué)歸納法：
最小4色圖是K4，含4個(gè)區(qū)域，4個(gè)點(diǎn)。
設(shè)圖含N(大于3)個(gè)點(diǎn)時(shí)，4色可染。若圖3色不可染，圖必然含至少2個(gè)區(qū)域，沒有一個(gè)固定區(qū)域必須4色染。(即允許有4色染的區(qū)域存在，但在圖上是可以流動(dòng)的。類似于給圖4色染的時(shí)候，因?yàn)闆]有精心的配置，會(huì)出現(xiàn)某個(gè)區(qū)域4色染的情況。)
增加1個(gè)點(diǎn)A,它必然第4色可染，圖4色可染。
若圖只有1個(gè)區(qū)域，則2色可染。所以，若圖3色不可染，圖必然含至少2個(gè)區(qū)域。
此時(shí)，含N+1個(gè)點(diǎn)的圖若存在一個(gè)固定區(qū)域必須4色染，則必然是A所在(或不在)的區(qū)域。
如果A所在的區(qū)域包含了所有點(diǎn)，則要么圖3色可染，要么A是N個(gè)點(diǎn)的環(huán)的中心點(diǎn)，無4色染的區(qū)域。
如果A所在的區(qū)域沒有包含所有點(diǎn)，因?yàn)槲覀兛梢匀我庵付ㄕl是A,所以沒有一個(gè)固定區(qū)域必須4色染。
【另一種表述：因?yàn)楸仨?色染的圖必然含K3子圖，所以必然有1個(gè)3色染的區(qū)域。令3色染的區(qū)域含A(或者不含A)。而A卻是可以任意流動(dòng)的,所以沒有一個(gè)固定區(qū)域必須4色染�！�
根據(jù)歸納法可知，平面圖4色可染。
證畢。
方法2：
證明：
數(shù)學(xué)歸納法：
先觀察一下4色圖有什么特征：
最小的4色圖是K4，可以看作是C3加上一個(gè)中心點(diǎn)。
5個(gè)點(diǎn)的圖4色可染,當(dāng)它必須4色染時(shí),必有2個(gè)點(diǎn)，分別處于一個(gè)環(huán)的內(nèi)外。
6個(gè)點(diǎn)的圖4色可染,當(dāng)它必須4色染時(shí),要么是C5加上一個(gè)中心點(diǎn)，要么是必有2個(gè)點(diǎn)，分別處于一個(gè)環(huán)的內(nèi)外。
根據(jù)觀察，我們大膽假設(shè)：當(dāng)圖含N個(gè)點(diǎn)時(shí)，4色可染，當(dāng)它必須4色染時(shí)，要么含有子圖C(N-1)加上一個(gè)中心點(diǎn)，要么有2個(gè)點(diǎn)，分別處于一個(gè)環(huán)的內(nèi)外。
我們先證明當(dāng)圖含N+1個(gè)點(diǎn)時(shí)，圖4色可染：
去除N+1個(gè)點(diǎn)中任意一點(diǎn)A, 新圖含N個(gè)點(diǎn)。
如果新圖3色可染，則A第4色可染。圖4色可染。
如果新圖必須4色染，根據(jù)假設(shè)可知，要么新圖含有子圖C(N-1)加上一個(gè)中心點(diǎn)(此時(shí)，顯然A第4色可染)，要么有2個(gè)點(diǎn)(B和C)，分別處于一個(gè)環(huán)的內(nèi)外。
不失一般性，我們可以假設(shè)A 和B處在同一個(gè)區(qū)域。
考察區(qū)域B所在點(diǎn)的染色情況：
若3色可染，則必有A第4色可染。
若必須4色染，根據(jù)假設(shè)可知，區(qū)域B要么有子圖C(N-X)加上一個(gè)中心點(diǎn),
(X是某個(gè)自然數(shù)。此時(shí)，顯然A第4色可染)，要么含有兩個(gè)點(diǎn)E,F分別處于某個(gè)環(huán)的內(nèi)外。
不失一般性，我們可以假設(shè)A 和E處在同一個(gè)區(qū)域......
因?yàn)閳D是有限圖，所以A必然是第4色可染的。
所以N+1個(gè)點(diǎn)的圖4色可染。
命題得證。
待續(xù)，貼不下......為尊重“聘才職業(yè)圈”這個(gè)平臺上眾多給予幫助的專家，引用此文時(shí)，請注明“來自聘才職業(yè)圈”
為了打擊我根深蒂固的愚昧和狂妄，特懸賞：第一個(gè)發(fā)現(xiàn)證明0或證明2本質(zhì)錯(cuò)誤的人，可獲得小米手機(jī)一臺，略表謝意。證明1中，有一個(gè)錯(cuò)誤，但可以彌補(bǔ)，不會(huì)影響結(jié)論。(我用的是WPS軟件，所以選擇小米。)
Hello, world!
I am becoming a machine.
本文所說的圖都是指平面圖。
方法0：