无结图及其若干性质论文

无结图及其若干性质论文

　　从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 ？%），

　　（t/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，

　　本文着重研究了无结图的充要条件和它的特征。事实上，无结图还有一些性质对研究平面图的着色十分重要，因篇幅所限，本文不宜将它们也展开讨论，留待以后再研究。