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

徐肇鑾，郭秀山，楊文榮

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

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

徐肇鑾，郭秀山，楊文榮

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

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

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

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

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

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

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

由此得到

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

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

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

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

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

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

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

2 對(duì)偶圖

因?yàn)榉彩瞧矫鎴D都可以有其對(duì)應(yīng)的對(duì)偶圖．三角形平面圖也應(yīng)有其對(duì)偶圖，簡(jiǎn)單地說(shuō)：原圖G的邊與其對(duì)偶圖的邊一一對(duì)應(yīng)；原圖G的頂點(diǎn)與其對(duì)偶圖的面一一對(duì)應(yīng)；原圖G的面與其對(duì)偶圖的頂點(diǎn)一一對(duì)應(yīng)．

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

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

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

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

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

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

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

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

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

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

3 圖G的3個(gè)不相交邊集

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

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

4 圖G頂點(diǎn)的著色

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

如果取A、B、C、D 4種顏色中的3種來(lái)對(duì)三角形面的3個(gè)頂點(diǎn)著色，那么就有種取法，分別是ABC，ABD，CDA，CDB 4種．

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

[5]王艷麗，苗連英．圖的集合邊色數(shù) [J]．山東大學(xué)學(xué)報(bào)（理學(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]謝力同．極大平面圖的組合運(yùn)算 [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-），男（漢族），副教授．