無(wú)結(jié)圖及其若干性質(zhì)論文
從1840年由數(shù)學(xué)家茂比烏斯（M6bius）提出四色猜想以來(lái)，世界各國(guó)很多專家、學(xué)者為了 證明猜想為真，做了大量工作，作出了很多卓越貢獻(xiàn)。但至今尚未見(jiàn)過(guò)猜想的理論性證明？因而 本文將從理論上作些初步探索和研究，在文獻(xiàn)[4]的基礎(chǔ)上深入討論平面圖的著色與它的拓樸 結(jié)構(gòu)相互關(guān)系。建立了結(jié)、無(wú)結(jié)圖、有結(jié)圖、準(zhǔn)色交錯(cuò)路徑等概念，給出了無(wú)結(jié)圖的充分必要條 * 件以及它的一些性質(zhì)。這些概念和性質(zhì)對(duì)于從理論上證明四色定理將會(huì)起一定的推動(dòng)作用？
1基本概念
設(shè)平面圖G可4—著色，G中分別著a，a，b，c，d色。
定義1兩色子圖[4]？在圖G中，分別著色的點(diǎn)以及它們之間的邊所構(gòu)成的`子圖稱為 G的d兩色子圖，記為Gab。顯然，G有六種兩色子圖，它們分別為
兩色子圖（^，^/二^冶&山^^^彡的連通子圖數(shù)目記為？KXG^）。
定義2兩色交錯(cuò)路徑。G中任一兩色子圖可能是連通的，也可能是分離的？若G中任 意兩點(diǎn)V，和Vj在兩色子圖01，（：？：，>；=^，6<，山：1：尹3^）的同一連通子圖中，則w，和v，間至少存 在一條工，3/兩色交錯(cuò)路徑，用表示？
。定義3不相千點(diǎn)對(duì)圖G中和％著為同色，或通過(guò)Kempe法⑴交換可著為同色，稱Vi和V，為不相干點(diǎn)對(duì)，記為（奶；TO）。
定義4相干點(diǎn)對(duì)圖G中w，_和％著為異色，通過(guò)Kempe法交換也不能著為同色，稱 Vi和V，為相干點(diǎn)對(duì)，記為（認(rèn)？ V）。若圖G的，巧，w3，w4，w5}中除和02；%）為 不相干點(diǎn)對(duì)外，其余各點(diǎn)對(duì)均為相干點(diǎn)對(duì)，則稱它為仏。將圖Go嵌入一個(gè)平面，使 V4，^5均處在外區(qū)周界上，P4。5M兩色交錯(cuò)路徑把非外區(qū)分為忒和A兩部分，設(shè)，Gd（t；3）C：A2。同樣，尸3。5W兩色交錯(cuò)路徑把非外區(qū)分為私和B2兩部分，又設(shè) Gac （v2）（=瓦，Gac （t；4） CZB2 ？
定義S結(jié)。若圖G。的兩色子圖山x=^y）中不含有，的，％}中任 一點(diǎn)，則稱J巧為G。的結(jié)。允許在一個(gè)結(jié)中只含有一個(gè)點(diǎn)。Go中可有六種結(jié)= —Gdbi） — Gab（v^） ； Jac — Gac ~ Gac （v2 ） — Gac （，V 4。 ） ； J ad = Gad ~~ Gad （Vl ^V2 J VS） 9 J bc^ Gbc ~ （v^ ^ V 4） ； J bd ~ Gbd —Gtdiv3 ，v5） —，Jcd = Gcd一Gcd（^4，w5）。
定義6無(wú)結(jié)圖和有結(jié)圖。若圖G。中不存在任一結(jié)人，=：關(guān)30，則稱G。為無(wú)結(jié)圖。否則，G。稱為有結(jié)圖。
定義7準(zhǔn)色交錯(cuò)路徑設(shè)圖G。中隊(duì)和巧之間不存在兩色交 錯(cuò)路徑，但存在帶有第三色的路徑，且通過(guò)<^（奶）（1，3/ = ^，6<，山：1：關(guān)3^ = 1，2，3，4，5，々六 夫_；？）中色交換它可以變成R和％之間的兩色交錯(cuò)路徑，那末這種三色路徑被稱為準(zhǔn)色交錯(cuò)路 徑。在G中可有四種準(zhǔn)色交錯(cuò)路徑，為了書(shū)寫(xiě)方便，將它們寫(xiě)成如下形式
Pl =P2，iiacbc，b^Gat{vi） ，fi^Go4（wi））
P1為W和％之間的準(zhǔn)色交錯(cuò)路徑。其中，所有6色點(diǎn)均屬于Ca？（W|），所有《色點(diǎn)均不屬于 Go4Cvi）。
P3 = PlA{acbc，a G Gab（v3），b $ Gal。（v3））
P2 = puAabcb，c 6 G？c{v2） ，a $ G沉（t；2））
P* = Pu3（abcbta G Gae{vt） ，c $ G沉（w4））
關(guān)于P3’P2和i34的涵義可以仿照尸1給予解釋，這里不再贅述。
2定理與證明
定理 1 當(dāng)且僅當(dāng) G。中 KD = 2，KU = 2，KD = KD = KXG砧）=K（GrA： 1 時(shí)，則仏為無(wú)結(jié)圖。
證明先證充分性。由于G。中（％；%）為不相干點(diǎn)對(duì)，故G。中不存在尺。3仏因此，
門(mén) Gab（幻3） = 0？又因?yàn)?K{Gab） — 2，Gab（vi） （JGab（t/3） = Gab。由此得 Jab = Gab—Gab{vl） — Gab（v3） =0。同樣可證：當(dāng) iC（Gfl？） = 2 時(shí)，幾=0；當(dāng) K（Gad） = K（GO = K（Gbd） = K（Gcd） = 1 時(shí)山
=*，b，— ~ ？，bd ~Jcd= 0 ？？
再證必要性。設(shè)G。為無(wú)結(jié)圖，即G0中J ab — J ac==ZJad = J bc = J bd = Jcd = 0 ？因?yàn)橛?人*定義知，UGfl*（t/3）==Ga*。又由于 G。中（Pi；t；3）為不相干點(diǎn)對(duì) 由此可見(jiàn)Gd是由（^（^和G^（*c；3）兩個(gè)連通子圖組成，故K（GU） = 2。同樣，由于J？ = 0，所以 K{Gar） = 2。由于 4=*/如=。八/=二 = 0，所以 K{Gad、= K（Gbc） = K（Gb/）=KiGcd） = 。證畢。
定理2設(shè)G。為無(wú)結(jié)圖，則G。中均為樹(shù) 形圖。？
證明G0為無(wú)結(jié)圖，C。中兩色子圖按它們的連通子圖數(shù)目K可分為兩類：和為一 類；Gad，Gbc，Gbd，Gcd為另一類。因此，可從，Gfl*（t；3） ’Gah），Ga<r（z；4）中任取一個(gè)作為代表 給予證明。不妨取Gab、xn在另一類中不妨取Gw作為代表。
先證G^t^）是樹(shù)形圖。因?yàn)镚。中^（GJt/O）—；！，所以是連通圖。下面用反證法' 證明G^（%）中不含任一回路。將G。嵌入一個(gè)平面，設(shè)G^（^）中有一個(gè)回路〇，==（%，如，…， %，tm），C，把4劃分成兩部分。在C。內(nèi)側(cè)可分以下兩種情況：
1）若在C，內(nèi)側(cè)至少有一個(gè)點(diǎn)。當(dāng)其中只要有一個(gè)^或⑴色點(diǎn)時(shí)，則G。中至少有一個(gè) Jch。當(dāng)其中只有a（或6，或a，6）色點(diǎn)時(shí)，則Go中至少有一個(gè)九（或人，或JaM人）和或 ？/&或和那末，上述情況均與G。為無(wú)結(jié)圖相矛盾。
2）若在C，內(nèi)側(cè)不含任何點(diǎn)。不失一般性，設(shè)C，=（如，私2，奶3，認(rèn)4，叫），它們分別著a，6，a，6， a色。由于尺（G^） = l，故G。中存在一條p；1。i3W。由于7aGk） = l，故在G。中存在一條尸，2。，灰。 又由于C，內(nèi)側(cè)不含任何點(diǎn)，所以P。u。iad和P‘ZMbc都在C，的外側(cè)，但它們兩者之間沒(méi)有同色 點(diǎn)，從而兩者相交叉，這與G。的平面性相矛盾。綜上分析，Ga4（A）是一個(gè)不含任何回路的連通 圖，故它是樹(shù)形圖。仿效上面，可證明Ga4U3），Gah2），〇？（%）也都是樹(shù)形圖。
再證是樹(shù)形圖。由于尺（0。，）= 1，故是一個(gè)連通圖。也用反證法證明中不含任一 回路。設(shè)中有一個(gè)回路（^—（^，？，^^，？，力山它們分別著？^^“⑴色。C，把G。劃分 成兩部分。在C，內(nèi)側(cè)可有以下兩種情況：
1）設(shè)C，內(nèi)側(cè)至少有一個(gè)點(diǎn)。當(dāng)其中只要有一個(gè)6（或c）色點(diǎn)時(shí)，則G。中至少有一個(gè)J&。 當(dāng)其中只有a（或山或a和A色點(diǎn)時(shí)，則Gu中至少有一個(gè)人4（或？/？，或人4和D和人八或 人/，或九和那末，上述情況均與G。為無(wú)結(jié)圖相矛盾。
2）設(shè)C，內(nèi)側(cè)不含任何點(diǎn)。由于G。中為相干點(diǎn)對(duì)，G。中存在一條P3。5W，又由于 Cy內(nèi)側(cè)不含任何點(diǎn)，故P“bd在C，的外側(cè)。換言之，C，在中，或在B2中。又由于G。中 K（G^（v2））=K（G。Avi）） = l，^l： Go 中存在一條 Pn。^ac。由于 K（GM） = 1，故 G0 中存在一條
又由于C，內(nèi)側(cè)不含任一點(diǎn)，所以乙和P，2。，M都在C，的外側(cè)，但它們間無(wú)同色 點(diǎn)，從而兩’者相交叉。這與Gu的平面性相矛盾。由此可見(jiàn)Gw中不含任一回路。
綜上分析，是一個(gè)沒(méi)有回路的連通圖，故是一個(gè)樹(shù)形圖。仿效G&可證明Gfc，GM， 也都是樹(shù)形圖。證畢。
定理3設(shè)G。為無(wú)結(jié)圖，若G。中存在準(zhǔn)色交錯(cuò)路徑P1和P3，則P^P3。
證明因?yàn)镚0為無(wú)結(jié)圖，所以O(shè)DUG^G^G上）門(mén)O） = 0。因此，G。中 著a色的點(diǎn)不是在<^（巧）中，就是在GJw）中，G？中著6色的點(diǎn)不是在<^4（13）中，就是在 Ga4（%）中。換言之，a^Ga4（Wl）與aGGa4（%）等價(jià)，（巧）與等價(jià)。由此得
P1 = P2，i （acbc，b 6 G^iVi） ，a G Ga6^v3））
P3 = PiAkacbc，a 6 Gab{v3） ，b G G^C^i））
顯見(jiàn)，產(chǎn)=尸3。證畢。'
定理4設(shè)G。為無(wú)結(jié)圖，若G。中存在準(zhǔn)色交錯(cuò)路徑尸2和尸4，則尸2 =尸'
可仿效定理3證明，這里不贅述了。
3實(shí)例
假設(shè)圖G。如圖1所示。在G。中％，t/2分別著a，a，b，c，d色，它們之間有以下七
條兩色交錯(cuò)路徑：尸（t/i，取5），尸2，5“d= （口2，取5），尸 2，3 口=ivZyV3） itJ？C= iv39v^） 9P itiaC =ivi ，t；4）{v^^vi^vio^vs） ， P4t5cd= （vi9v6jv7 9v89v9 9v5）。所以（A ？%）， （^z ？%），
（t/2 ？ t/a），（t/3 ？ V4），（Vl ？ t/4） ， （1^3 ？ ”5）和（。4 ？。5）均為相干點(diǎn)對(duì)？在{。1 ，。2，。3 9^4 ^5 ）中（口1 fV2 ），
�。�%；%）和（t；2；w4）均為不相干點(diǎn)對(duì)。由圖1可見(jiàn)，在Go中K⑴J = 2，K iG aJ = 2， K iG ad）= KiGbc）=K{Gbds>=Ki。Gcd} = 。故圖是一個(gè)無(wú)結(jié)圖。它的兩色子圖用圖2表示
由圖 2 顯見(jiàn)，Go 的兩色子圖 Gab （% ） ， （jab （D3），Gae （^2 ），Gac （W ） ， Gad，Gbc ， Gbd，均為樹(shù)形
再考察圖1的圖G。，可驗(yàn)證定理3和定理4。因?yàn)樵贕。中尸^產(chǎn)，尸2 =產(chǎn)。具體情況如在圖G。中其中b色點(diǎn)％。屬于Ga*（Pi），a色點(diǎn)和如均 屬+GaA（t；3）。若在GJa）中色交換，會(huì)使尸1變成巧和％間％兩色交錯(cuò)路徑P2，wo若在 GaA（i；3）中色交換，會(huì)使尸3變成和％間&兩色交錯(cuò)路徑P2，J>c。
在圖G。中尸2=尸4=（t^，t/io，t^，t；3），其中c色點(diǎn)％屬于0^（1>2），<2色點(diǎn)％屬于Ga？：（t^）。若 在Ga，（z；2）中色交換，會(huì)使P2變成Vl和％間ab兩色交錯(cuò)路徑/V3M；若在G二（^）中色交換， 會(huì)使P4變成A和％間cb兩色交錯(cuò)路徑1，
本文著重研究了無(wú)結(jié)圖的充要條件和它的特征。事實(shí)上，無(wú)結(jié)圖還有一些性質(zhì)對(duì)研究平面圖的著色十分重要，因篇幅所限，本文不宜將它們也展開(kāi)討論，留待以后再研究。
【無(wú)結(jié)圖及其若干性質(zhì)論文】相關(guān)文章：
二次函數(shù)及其圖象和性質(zhì)(學(xué)案)11-30
論文：利維坦 無(wú)支配自由及其限度06-14
《技術(shù)及其性質(zhì)》教案11-28
論文：論優(yōu)先權(quán)性質(zhì)的界定及其價(jià)值07-01
概念圖的制作及其教學(xué)價(jià)值的論文05-09
康德的圖型說(shuō)及其意義論文02-14
堿及其性質(zhì)教學(xué)反思05-18