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