無(wú)結圖及其若干性質(zhì)論文

　　從1840年由數學(xué)家茂比烏斯（M6bius）提出四色猜想以來(lái)，世界各國很多專(zhuān)家、學(xué)者為了 證明猜想為真，做了大量工作，作出了很多卓越貢獻。但至今尚未見(jiàn)過(guò)猜想的理論性證明？因而 本文將從理論上作些初步探索和研究，在文獻[4]的基礎上深入討論平面圖的著(zhù)色與它的拓樸 結構相互關(guān)系。建立了結、無(wú)結圖、有結圖、準色交錯路徑等概念，給出了無(wú)結圖的充分必要條 * 件以及它的一些性質(zhì)。這些概念和性質(zhì)對于從理論上證明四色定理將會(huì )起一定的推動(dòng)作用？

　　1基本概念

　　設平面圖G可4—著(zhù)色，G中分別著(zhù)a，a，b，c，d色。

　　定義1兩色子圖[4]？在圖G中，分別著(zhù)色的點(diǎn)以及它們之間的邊所構成的`子圖稱(chēng)為 G的d兩色子圖，記為Gab。顯然，G有六種兩色子圖，它們分別為

　　兩色子圖（^，^/二^冶&山^^^彡的連通子圖數目記為？KXG^）。

　　定義2兩色交錯路徑。G中任一兩色子圖可能是連通的，也可能是分離的？若G中任 意兩點(diǎn)V，和Vj在兩色子圖01，（：？：，>；=^，6<，山：1：尹3^）的同一連通子圖中，則w，和v，間至少存 在一條工，3/兩色交錯路徑，用表示？

　　。定義3不相千點(diǎn)對圖G中和％著(zhù)為同色，或通過(guò)Kempe法⑴交換可著(zhù)為同色，稱(chēng)Vi和V，為不相干點(diǎn)對，記為（奶；TO）。

　　定義4相干點(diǎn)對圖G中w，_和％著(zhù)為異色，通過(guò)Kempe法交換也不能著(zhù)為同色，稱(chēng) Vi和V，為相干點(diǎn)對，記為（認？ V）。若圖G的，巧，w3，w4，w5}中除和02；%）為 不相干點(diǎn)對外，其余各點(diǎn)對均為相干點(diǎn)對，則稱(chēng)它為仏。將圖Go嵌入一個(gè)平面，使 V4，^5均處在外區周界上，P4。5M兩色交錯路徑把非外區分為忒和A兩部分，設，Gd（t；3）C：A2。同樣，尸3。5W兩色交錯路徑把非外區分為私和B2兩部分，又設 Gac （v2）（=瓦，Gac （t；4） CZB2 ？

　　定義S結。若圖G。的兩色子圖山x=^y）中不含有，的，％}中任 一點(diǎn)，則稱(chēng)J巧為G。的結。允許在一個(gè)結中只含有一個(gè)點(diǎn)。Go中可有六種結= —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ú)結圖和有結圖。若圖G。中不存在任一結人，=：關(guān)30，則稱(chēng)G。為無(wú)結圖。否則，G。稱(chēng)為有結圖。

　　定義7準色交錯路徑設圖G。中隊和巧之間不存在兩色交 錯路徑，但存在帶有第三色的路徑，且通過(guò)<^（奶）（1，3/ = ^，6<，山：1：關(guān)3^ = 1，2，3，4，5，々六 夫_；？）中色交換它可以變成R和％之間的兩色交錯路徑，那末這種三色路徑被稱(chēng)為準色交錯路 徑。在G中可有四種準色交錯路徑，為了書(shū)寫(xiě)方便，將它們寫(xiě)成如下形式

　　Pl =P2，iiacbc，b^Gat{vi） ，fi^Go4（wi））

　　P1為W和％之間的準色交錯路徑。其中，所有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給予解釋?zhuān)�這里不再贅述。

　　2定理與證明

　　定理 1 當且僅當 G。中 KD = 2，KU = 2，KD = KD = KXG砧）=K（GrA： 1 時(shí)，則仏為無(wú)結圖。

　　證明先證充分性。由于G。中（％；%）為不相干點(diǎn)對，故G。中不存在尺。3仏因此，

　　門(mén) Gab（幻3） = 0？又因為 K{Gab） — 2，Gab（vi） （JGab（t/3） = Gab。由此得 Jab = Gab—Gab{vl） — Gab（v3） =0。同樣可證：當 iC（Gfl？） = 2 時(shí)，幾=0；當 K（Gad） = K（GO = K（Gbd） = K（Gcd） = 1 時(shí)山

　　=*，b，— ~ ？，bd ~Jcd= 0 ？？

　　再證必要性。設G。為無(wú)結圖，即G0中J ab — J ac==ZJad = J bc = J bd = Jcd = 0 ？因為由 人*定義知，UGfl*（t/3）==Ga*。又由于 G。中（Pi；t；3）為不相干點(diǎn)對 由此可見(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設G。為無(wú)結圖，則G。中均為樹(shù) 形圖。？

　　證明G0為無(wú)結圖，C。中兩色子圖按它們的連通子圖數目K可分為兩類(lèi)：和為一 類(lèi)；Gad，Gbc，Gbd，Gcd為另一類(lèi)。因此，可從，Gfl*（t；3） ’Gah），Ga<r（z；4）中任取一個(gè)作為代表 給予證明。不妨取Gab、xn在另一類(lèi)中不妨取Gw作為代表。

　　先證G^t^）是樹(shù)形圖。因為G。中^（GJt/O）—；！，所以是連通圖。下面用反證法' 證明G^（%）中不含任一回路。將G。嵌入一個(gè)平面，設G^（^）中有一個(gè)回路〇，==（%，如，…， %，tm），C，把4劃分成兩部分。在C。內側可分以下兩種情況：

　　1）若在C，內側至少有一個(gè)點(diǎn)。當其中只要有一個(gè)^或⑴色點(diǎn)時(shí)，則G。中至少有一個(gè) Jch。當其中只有a（或6，或a，6）色點(diǎn)時(shí)，則Go中至少有一個(gè)九（或人，或JaM人）和或 ？/&或和那末，上述情況均與G。為無(wú)結圖相矛盾。

　　2）若在C，內側不含任何點(diǎn)。不失一般性，設C，=（如，私2，奶3，認4，叫），它們分別著(zhù)a，6，a，6， a色。由于尺（G^） = l，故G。中存在一條p；1。i3W。由于7aGk） = l，故在G。中存在一條尸，2。，灰。 又由于C，內側不含任何點(diǎn)，所以P。u。iad和P‘ZMbc都在C，的外側，但它們兩者之間沒(méi)有同色 點(diǎn)，從而兩者相交叉，這與G。的平面性相矛盾。綜上分析，Ga4（A）是一個(gè)不含任何回路的連通 圖，故它是樹(shù)形圖。仿效上面，可證明Ga4U3），Gah2），〇？（%）也都是樹(shù)形圖。

　　再證是樹(shù)形圖。由于尺（0。，）= 1，故是一個(gè)連通圖。也用反證法證明中不含任一 回路。設中有一個(gè)回路（^—（^，？，^^，？，力山它們分別著(zhù)？^^“⑴色。C，把G。劃分 成兩部分。在C，內側可有以下兩種情況：

　　1）設C，內側至少有一個(gè)點(diǎn)。當其中只要有一個(gè)6（或c）色點(diǎn)時(shí)，則G。中至少有一個(gè)J&。 當其中只有a（或山或a和A色點(diǎn)時(shí)，則Gu中至少有一個(gè)人4（或？/？，或人4和D和人八或 人/，或九和那末，上述情況均與G。為無(wú)結圖相矛盾。

　　2）設C，內側不含任何點(diǎn)。由于G。中為相干點(diǎn)對，G。中存在一條P3。5W，又由于 Cy內側不含任何點(diǎn)，故P“bd在C，的外側。換言之，C，在中，或在B2中。又由于G。中 K（G^（v2））=K（G。Avi）） = l，^l： Go 中存在一條 Pn。^ac。由于 K（GM） = 1，故 G0 中存在一條

　　又由于C，內側不含任一點(diǎn)，所以乙和P，2。，M都在C，的外側，但它們間無(wú)同色 點(diǎn)，從而兩’者相交叉。這與Gu的平面性相矛盾。由此可見(jiàn)Gw中不含任一回路。

　　綜上分析，是一個(gè)沒(méi)有回路的連通圖，故是一個(gè)樹(shù)形圖。仿效G&可證明Gfc，GM， 也都是樹(shù)形圖。證畢。

　　定理3設G。為無(wú)結圖，若G。中存在準色交錯路徑P1和P3，則P^P3。

　　證明因為G0為無(wú)結圖，所以ODUG^G^G上）門(mén)O） = 0。因此，G。中 著(zhù)a色的點(diǎn)不是在<^（巧）中，就是在GJw）中，G？中著(zhù)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設G。為無(wú)結圖，若G。中存在準色交錯路徑尸2和尸4，則尸2 =尸'

　　可仿效定理3證明，這里不贅述了。

　　3實(shí)例

　　假設圖G。如圖1所示。在G。中％，t/2分別著(zhù)a，a，b，c，d色，它們之間有以下七

　　條兩色交錯路徑：尸（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 ？%），

　�。╰/2 ？ t/a），（t/3 ？ V4），（Vl ？ t/4） ， （1^3 ？ ”5）和（。4 ？。5）均為相干點(diǎn)對？在{。1 ，。2，。3 9^4 ^5 ）中（口1 fV2 ），

　�。�%；%）和（t；2；w4）均為不相干點(diǎn)對。由圖1可見(jiàn)，在Go中K⑴J = 2，K iG aJ = 2， K iG ad）= KiGbc）=K{Gbds>=Ki。Gcd} = 。故圖是一個(gè)無(wú)結圖。它的兩色子圖用圖2表示

　　由圖 2 顯見(jiàn)，Go 的兩色子圖 Gab （% ） ， （jab （D3），Gae （^2 ），Gac （W ） ， Gad，Gbc ， Gbd，均為樹(shù)形

　　再考察圖1的圖G。，可驗證定理3和定理4。因為在G。中尸^產(chǎn)，尸2 =產(chǎn)。具體情況如在圖G。中其中b色點(diǎn)％。屬于Ga*（Pi），a色點(diǎn)和如均 屬+GaA（t；3）。若在GJa）中色交換，會(huì )使尸1變成巧和％間％兩色交錯路徑P2，wo若在 GaA（i；3）中色交換，會(huì )使尸3變成和％間&兩色交錯路徑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兩色交錯路徑/V3M；若在G二（^）中色交換， 會(huì )使P4變成A和％間cb兩色交錯路徑1，

　　本文著(zhù)重研究了無(wú)結圖的充要條件和它的特征。事實(shí)上，無(wú)結圖還有一些性質(zhì)對研究平面圖的著(zhù)色十分重要，因篇幅所限，本文不宜將它們也展開(kāi)討論，留待以后再研究。

【無(wú)結圖及其若干性質(zhì)論文】相關(guān)文章：

二次函數及其圖象和性質(zhì)(學(xué)案)11-30

論文：利維坦 無(wú)支配自由及其限度06-14

《技術(shù)及其性質(zhì)》教案11-28

論文：論優(yōu)先權性質(zhì)的界定及其價(jià)值07-01

概念圖的制作及其教學(xué)價(jià)值的論文05-09

康德的圖型說(shuō)及其意義論文02-14

堿及其性質(zhì)教學(xué)反思05-18

《垂線(xiàn)及其性質(zhì)》教學(xué)總結12-09

膠體的性質(zhì)及其應用的教案08-12