無結圖及其若干性質論文

時間：2021-04-27 14:13:35 論文我要投稿

無結圖及其若干性質論文

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

無結圖及其若干性質論文

　　1基本概念

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

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

　　兩色子圖（^，^/二^冶&山^^^彡的連通子圖數目記為？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，為相干點對，記為（認？ V）。若圖G的，巧，w3，w4，w5}中除和02；%）為不相干點對外，其余各點對均為相干點對，則稱它為仏。將圖Go嵌入一個平面，使 V4，^5均處在外區周界上，P4。5M兩色交錯路徑把非外區分為忒和A兩部分，設，Gd（t；3）C：A2。同樣，尸3。5W兩色交錯路徑把非外區分為私和B2兩部分，又設 Gac （v2）（=瓦，Gac （t；4） CZB2 ？

　　定義S結。若圖G。的兩色子圖山x=^y）中不含有，的，％}中任一點，則稱J巧為G。的結。允許在一個結中只含有一個點。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無結圖和有結圖。若圖G。中不存在任一結人，=：關30，則稱G。為無結圖。否則，G。稱為有結圖。

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

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

　　P1為W和％之間的準色交錯路徑。其中，所有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））

　　關于P3’P2和i34的涵義可以仿照尸1給予解釋，這里不再贅述。

　　2定理與證明

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

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

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

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

　　再證必要性。設G。為無結圖，即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設G。為無結圖，則G。中均為樹形圖。？

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

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

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

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

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

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

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

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

　　綜上分析，是一個沒有回路的連通圖，故是一個樹形圖。仿效G&可證明Gfc，GM，也都是樹形圖。證畢。

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

　　證明因為G0為無結圖，所以ODUG^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））

　　顯見，產=尸3。證畢。'

　　定理4設G。為無結圖，若G。中存在準色交錯路徑尸2和尸4，則尸2 =尸'

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

　　3實例

　　假設圖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} = 。故圖是一個無結圖。它的兩色子圖用圖2表示

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

　　再考察圖1的圖G。，可驗證定理3和定理4。因為在G。中尸^產，尸2 =產。具體情況如在圖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，

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

【無結圖及其若干性質論文】相關文章：

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

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

《技術及其性質》教案11-28

論文：論優先權性質的界定及其價值07-01