徐肇鑾，郭秀山，楊文榮

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

三角形平面圖的若干性質探討

徐肇鑾，郭秀山，楊文榮

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

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

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

1 頂點、邊和面的關系

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

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

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

由此得到

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

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

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

如果1個圖Gi的頂點的集合和邊的集合是原圖G的子集合，那么Gi為原G的1個子圖．在三角形平面圖中，不會出現有4個以上頂點的完備圖的子圖，只能出現只有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構成的1個子圖是1個v=4的完備圖．所有相鄰的2個三角形面結成一對，都可以形成1個子圖，例如f1與f2結成1個子圖，也可以f1與 f3，或 f1與 f12形成1個子圖．這樣的子圖應包括4個頂點，5條邊，2個三角形面，中間一條邊為此2個三角形面的公共邊．2個相鄰三角形面，有且僅有此1條公共邊[4]．如圖2所示．

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

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

2 對偶圖

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

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

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

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

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

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

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

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

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

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

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

3 圖G的3個不相交邊集

三角形平面圖G的邊數e=3v 6，等于其對偶圖GD的邊數．因為GD中的每個頂點都置于原三角形平面圖G的每個三角形面之中．由這一頂點“發(fā)出”或“到達”的3條邊，都與該三角形面相鄰的3個三角形面中的對偶圖的頂點相連接．它們都具有b、g、r 3類不同顏色，而且所有這3條對偶圖的邊都“跨過”或者說都“切割”原圖G中該三角形面的3條邊，被哪一種顏色的對偶圖邊“切割”，那么就對應地也著該類顏色．因此圖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個相鄰三角形面結合在一起的子圖Gi，如圖2所示，無論這一頂點在原圖G中，它的結合度有多大，它在上述的子圖Gi中的結合度只能是3或2，而且任意1個三角形面可以與其相鄰的3個三角形面分別結合成3個不同的子圖Gi，于是每個三角形面的3條邊，都可以是這三個不同的子圖Gi的3條公共邊．做到這一要求的必要條件，就是因為G中沒有4個頂點以上的完備圖的子圖．如果有4個頂點以上的完備圖存在的話，那么可能G中有一條邊不是唯一的，而是2個三角形面的公共邊，有可能是3個三角形面的公共邊．每個三角形面中所置的頂點發(fā)出的邊，可能有4條，不是均為3條．而原圖G的邊，不是一一被切割，有可能被切割2次，即不能一一對應，不可能構成3個不相交的邊的集合．所以圖G中沒有4個頂點以上完備圖的子圖是必要條件．反過來說，圖G中不存在4個頂點以上的完備圖的子圖，那么無論是原圖G或者其對偶圖，它們的邊數相等，而且一一對應，都可以構成3個不相交的邊的集合．原圖G的所有三角形面的3條邊，都分屬于這3個不相交的邊的集合，用不到其他條件．所以圖G中不存在4個頂點以上的完備圖的子圖也是充分條件．證畢．

5 結束語

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

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

[1]龔光魯．有限數學引論 [M]．上海：上海科學技術出版社，1981．

[2]陳樹柏．網絡圖論及其應用 [M]．北京：科學出版社，1982．

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

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

[5]王艷麗，苗連英．圖的集合邊色數 [J]．山東大學學報（理學版），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)科學與數學，1993，13（4）：323-330．

[責任編輯 代俊秋 夏紅梅]

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-），男（漢族），副教授．