徐肇鑾，郭秀山，楊文榮

（河北工業(yè)大學(xué) 電氣工程學(xué)院，天津 300130）

三角形平面圖的若干性質(zhì)探討

徐肇鑾，郭秀山，楊文榮

（河北工業(yè)大學(xué) 電氣工程學(xué)院，天津 300130）

首先敘述了三角形平面圖G的頂點V、邊E和面F的關(guān)系．因為G不會存在頂點數(shù)大于4的完備圖的子圖，所以如分成一個個由2個相鄰三角形面構(gòu)成的子圖，對比2個三角形面而言，其公共邊是唯一的．其次引入其對偶圖的邊與頂點的關(guān)系，并應(yīng)用了置換群的概念，對頂點做換位運算，可以導(dǎo)出對頂點所連接的3條邊可以分別屬于3個不相交的集合．因此對偶于原三角形平面圖的每個三角形面的3條邊，也分別屬于3個不相交的邊的集合．最后可以得出這樣的結(jié)論，只用4種顏色來對三角形平面圖的頂點正確著色的充要條件是：三角形平面圖中，不存在4個頂點以上的完備圖的子圖．

對偶圖；完備圖；結(jié)合矩陣；置換群；換位；四色定理

1 頂點、邊和面的關(guān)系

圖是包括許多個點和把這些點連接起來的線段，以及這些線段圍成的區(qū)域的總稱．這些點被稱為圖的頂點，頂點的集合用V表示．這些線段被稱為圖的邊，邊的集合用E表示．這些線段圍成的區(qū)域，被稱為面，它的集合用F表示．這點頂點和邊可以畫在1個平面上．除頂點之外，任何兩邊之間不許有交點，則稱為平面圖．因為現(xiàn)在要討論的圖，它的面都是由3條邊圍成，而且必須畫在1個平面上，所以稱為三角形平面圖[1]．本文用G V,E表示，或簡單用G表示．

由圖中某一頂點出發(fā)，又回到這一頂點的邊，稱為自環(huán)．那么它只是一條邊圍成1個面．如果在2個頂點之間，有2條或2條以上的邊，都接在這同2個頂點之間，這樣2條邊就圍成1個面，稱為多重邊．現(xiàn)在我們要討論的圖G，每個面都要用3條邊圍成，所以沒有自環(huán)和多重邊．圖G最外的邊，也應(yīng)只有3條邊．在這3條邊之外，直至無限的區(qū)域，也構(gòu)成了1個面，被稱為無界面，在討論平面圖時，必須包括它們在內(nèi)[2]．現(xiàn)在要討論的圖G，只有1個連通片在每一條邊上，也沒有指出方向，所以是簡單無向圖．

如圖G的頂點數(shù)用v表示，邊數(shù)用e表示，面數(shù)用f表示，連通片為l，那么根據(jù)著名的歐拉公式

由此得到

每個頂點所連接的邊數(shù)，稱為該頂點的結(jié)合度或簡稱度，用d vi表示．

因為每條邊都要有2個頂點連接，而一共有e=3v 6條邊．所以把所有每個頂點的結(jié)合度加起來的總和，應(yīng)該是2e=6v 12，因此它的平均值.

從上式可以看出，在G中總有某些頂點的結(jié)合度比6小，即某些頂點的結(jié)合度

如果1個圖Gi的頂點的集合和邊的集合是原圖G的子集合，那么Gi為原G的1個子圖．在三角形平面圖中，不會出現(xiàn)有4個以上頂點的完備圖的子圖，只能出現(xiàn)只有4個頂點的完備圖，即可以有4個頂點的度都為3的完備圖的子圖[3]．

例1任意給出1個圖G，如圖1所示，它的v=8， e=3v 6=18，f=2v 4=12，頂點1，6，8，5及 e8，e16，e6，e7，e13，e15構(gòu)成的1個子圖是1個v=4的完備圖．所有相鄰的2個三角形面結(jié)成一對，都可以形成1個子圖，例如f1與f2結(jié)成1個子圖，也可以f1與 f3，或 f1與 f12形成1個子圖．這樣的子圖應(yīng)包括4個頂點，5條邊，2個三角形面，中間一條邊為此2個三角形面的公共邊．2個相鄰三角形面，有且僅有此1條公共邊[4]．如圖2所示．

圖1 三角形平面圖Fig.1 Triangular plan graph

圖2 由2個三角形面結(jié)對的子圖Fig.2 Pair consists of two triangular faces subgraph

2 對偶圖

因為凡是平面圖都可以有其對應(yīng)的對偶圖．三角形平面圖也應(yīng)有其對偶圖，簡單地說：原圖G的邊與其對偶圖的邊一一對應(yīng)；原圖G的頂點與其對偶圖的面一一對應(yīng)；原圖G的面與其對偶圖的頂點一一對應(yīng)．

可以在原圖G每個三角形面中畫置1個頂點，一共應(yīng)有2v 4個頂點，把這些頂點用邊都一一連接起來，就構(gòu)成了原圖G的相應(yīng)的對偶圖，用GD表示[5]．圖3畫出圖1中G的對偶圖．從圖可以看出對偶圖的邊都一一跨接或者說一一切割原圖G的邊，所以二者的邊數(shù)相等，而且對偶圖頂點的結(jié)合度都等于3．頂點數(shù)等于原圖G的面數(shù)f，對偶圖的面數(shù)等于原圖G的頂點數(shù)v．

把對偶圖GD的頂點用1，2，……，2n 4表示，然后列出1個2n 4×2n 4的正方形表格．如某2個頂點有邊連接，那么在表格中，相應(yīng)的行和列用1表示，否則為0，稱為GD的頂點結(jié)合矩陣．圖3中GD的頂點結(jié)合矩陣如圖4所示．

圖3 圖1三角形平面圖的對偶圖（實線所示）Fig.3 The dual graph of triangular planar graph in Fig.1

圖4 GD頂點結(jié)合矩陣Fiq.4 Vertex binding matrix of graph

從上面的矩陣中可以看出，這2v 4=12個對偶圖的頂點，都與這2v 4=12個頂點的全體中，相鄰3個頂點有邊連接．因為共有2v 4個頂點，所以這些連接的邊一共必須有條，分別連接這2v 4個頂點，相應(yīng)連接的頂點至少有3種不同，即這2v 4個頂點至少有3種不同的排列．

根據(jù)置換群的概念，n個元素應(yīng)有n!個排列．那么上述的3種排列一定包含在這n!個排列之中，而且僅是一種兩兩換位，有許多零元素，所以計算不是很大．從上面的例題可以看出，結(jié)合矩陣的對角線上是零元素，對角線上下的非零元素是對稱的，所以在寫出第1行的行編號和列編號后，從第2行起，要先寫出對角線以下的非零元素的行和列編號，它應(yīng)該在上面出現(xiàn)過，但行和列的編號互相換位，然后再寫出這一行中對應(yīng)于結(jié)合矩陣對角線上面出現(xiàn)的非零元素所應(yīng)有的行和列的編號．如此等等，把所有一對對的行和列的編號所代表的非零元素排成3排，手算即已完成．圖GD的3個不同的排列如表1所示[6]．

相應(yīng)也求得了3種連接在所有2v 4個頂點之間的邊．

這n=2v 4個頂點 (它一定是偶數(shù))，每個頂點都要“發(fā)出”3條邊，與其相鄰的3個頂點有3條邊各自連接．根據(jù)狄里克萊抽屜原則，這n個頂點中也一定是每個頂點都有3條來自不同的3個頂點的3條邊“到達”．“發(fā)出”和“到達”是可以視為一樣的，所以這共有的條邊一定可以分3類，分別為條邊，一類為藍色（b），一類為綠色（g），一類為紅色（r），而且是不相交的．

然后，利用置換群中換位的概念，依據(jù)結(jié)合矩陣中頂點與頂點的結(jié)合關(guān)系，對頂點的排列進行置換，即可以把所有條邊分出不同顏色的3類．每個頂點一定“發(fā)出”3條不同顏色的邊，每個頂點也一定有3條不同顏色的邊“到達”．任一類顏色的邊一定不會有2條或者2條以上連接起來．任一條邊不同具有2類或2類以上的顏色．

表1 圖GD的3個不同排列Tab.1 Three arrangements of gragh GD

3 圖G的3個不相交邊集

三角形平面圖G的邊數(shù)e=3v 6，等于其對偶圖GD的邊數(shù)．因為GD中的每個頂點都置于原三角形平面圖G的每個三角形面之中．由這一頂點“發(fā)出”或“到達”的3條邊，都與該三角形面相鄰的3個三角形面中的對偶圖的頂點相連接．它們都具有b、g、r 3類不同顏色，而且所有這3條對偶圖的邊都“跨過”或者說都“切割”原圖G中該三角形面的3條邊，被哪一種顏色的對偶圖邊“切割”，那么就對應(yīng)地也著該類顏色．因此圖G的每個三角形面的3條邊也都各具有3類不同顏色，因此G的所有3v 6條邊可分成3個不相交的邊集：Eb、Eg、Er．那么．

因此，G的每個三角形面的3條邊都必須是各有且僅有此b、g、r3類顏色．

4 圖G頂點的著色

所謂正確著色，就是要使圖G中每條邊的兩端頂點具有2種不同的顏色．因此是必須使每個三角形面的3個頂點具有3種不同顏色．

如果取A、B、C、D 4種顏色中的3種來對三角形面的3個頂點著色，那么就有種取法，分別是ABC，ABD，CDA，CDB 4種．

如果把三角形面的3條邊分別著以b(藍)，g(綠)，r(紅)3類顏色．若邊的顏色為r，則其兩端頂點顏色為A、B或C、D．若邊的顏色為g，則其兩端頂點著以A、C或B、D．若邊的顏色為b，則其兩端頂點著以B、C或A、D．

按照上述規(guī)定之后，那么三角形面的3條邊都是b、g、r 3種顏色的情況下，每個三角形面的3個頂點的顏色就一定可以是上述4種取法的一種．反過來說，如果三角形面的頂點顏色為上述4種取法的任一種，那么這三角形面的3條邊都是具有b、g、r3種顏色，所以二者是等價的．

圖G中任何1個三角形面都可以做到用b、g、r3類顏色來對3條邊著色，因此每個三角形面的3個頂點也一定可以用4種取法的任一種來著色．

四色定理：三角形平面圖的頂點可以只用4種顏色來正確著色的充分必要條件是三角形平面圖中不可能有4個頂點以上的完備圖的子圖[7]．

證明：因為三角形平面圖可以分為v 2個2個相鄰三角形面結(jié)合在一起的子圖Gi，如圖2所示，無論這一頂點在原圖G中，它的結(jié)合度有多大，它在上述的子圖Gi中的結(jié)合度只能是3或2，而且任意1個三角形面可以與其相鄰的3個三角形面分別結(jié)合成3個不同的子圖Gi，于是每個三角形面的3條邊，都可以是這三個不同的子圖Gi的3條公共邊．做到這一要求的必要條件，就是因為G中沒有4個頂點以上的完備圖的子圖．如果有4個頂點以上的完備圖存在的話，那么可能G中有一條邊不是唯一的，而是2個三角形面的公共邊，有可能是3個三角形面的公共邊．每個三角形面中所置的頂點發(fā)出的邊，可能有4條，不是均為3條．而原圖G的邊，不是一一被切割，有可能被切割2次，即不能一一對應(yīng)，不可能構(gòu)成3個不相交的邊的集合．所以圖G中沒有4個頂點以上完備圖的子圖是必要條件．反過來說，圖G中不存在4個頂點以上的完備圖的子圖，那么無論是原圖G或者其對偶圖，它們的邊數(shù)相等，而且一一對應(yīng)，都可以構(gòu)成3個不相交的邊的集合．原圖G的所有三角形面的3條邊，都分屬于這3個不相交的邊的集合，用不到其他條件．所以圖G中不存在4個頂點以上的完備圖的子圖也是充分條件．證畢．

5 結(jié)束語

四色問題是1852年英國F.Guthrie提出的，直到1976年，美國K.oppel，W.Hahen，J.Koch宣布他們借助計算機，證明了四色問題，但有的學(xué)者持不同看法．本文提出，利用對偶圖中頂點與邊的關(guān)系，根據(jù)狄里克萊抽屜原則，就可以說明對偶圖的邊完全可以分成3個不相交的集合，再根據(jù)置換群中的一種換位置換，得到3個頂點的3個不同的排列，即可求出，對偶圖的邊的3個不相交集合．因它與原圖的邊一一對應(yīng)，所以也得到了3個不相交的邊的3個集合，這里完全不需要計算機的幫助．

我們知道1個圖（包括非平面圖）的頂點的正確著色數(shù)，可以是10頂點中最大結(jié)合度．而對偶圖頂點結(jié)合度均為3，所以對偶圖的頂點是可以只用4種顏色來正確著色．但由此我們絕不可以認為三角形平面圖的頂點（或由此即可導(dǎo)出）也只需4種顏色來正確著色．因為原圖與對偶圖，是面與頂點，或頂點與面一一對應(yīng)．頂點與頂點，面與面不能一一對應(yīng)．只有邊與邊是一一對應(yīng)．本文就是利用邊與邊的對應(yīng)關(guān)系，來導(dǎo)出邊可以只用3種顏色，才導(dǎo)出其頂點可以用4種顏色來正確著色．

[1]龔光魯．有限數(shù)學(xué)引論 [M]．上海：上?？茖W(xué)技術(shù)出版社，1981．

[2]陳樹柏．網(wǎng)絡(luò)圖論及其應(yīng)用 [M]．北京：科學(xué)出版社，1982．

[3]盧開澄．組合數(shù)學(xué)算法和分析 [M]．北京：清華大學(xué)出版社，1983．

[4]祁忠斌，葉東，張和平．3-正則圖的環(huán)邊連通性和環(huán)連通性之間的關(guān)系 [J]．山東大學(xué)學(xué)報（理學(xué)版），2009，44（12）：22-24．

[5]王艷麗，苗連英．圖的集合邊色數(shù) [J]．山東大學(xué)學(xué)報（理學(xué)版），2012，47（6）：67-70．

[6]Oleg V Borodin，Anna O Ivanova．Precise upper bound for the strong edge chromatic number of sparse planar graphs[J]．Discussiones Mathematicae Graph Theory，2013，4（4）：759-770．

[7]謝力同．極大平面圖的組合運算 [J]．系統(tǒng)科學(xué)與數(shù)學(xué)，1993，13（4）：323-330．

[責(zé)任編輯 代俊秋 夏紅梅]

Several property of triangular planar graph

XU Zhaoluan，GUO Xiushan，YANG Wenrong

(School of Electrical Engineering,Hebei University of Technology,Tianjin 300130，China)

In this paper,firstly,the relationship of edges,vertexes and faces of Triangular Planar Graph G is explained. Because G does not have a complete subgraph with vertex number more than 4,it is divided into several subgraphs Gi, which are composed of two adjacent triangles.The every common edge of two triangles is unique.Secondly,relationship between edges and vertices of the dual graph of G is proposed.And the concept of permutation group is applied to do commuting operations on vertexes of dual graph.It can be deduced that the three edges which are connected by a vertex can be respectively belong to three disjoint sets.Therefore,the three edges of each triangle of the dual graph are respectively belong to the set of three disjoint edges.At last,the conclusion is obtained.The necessary and sufficient condition for the correct coloring with only four colors to vertexes of the triangular planar graph is that there is no complete subgraph with 4 vertices or more in the triangular planar graph.

dual graph;complete graph;adjacency matrix;permutation group;commutation;Four Color Theorem

O157.0

A

1007-2373(2016)05-0023-05

10.14081/j.cnki.hgdxb.2016.05.004

2016-09-06

徐肇鑾（1928-），男（漢族），副教授．