平面圖的多項(xiàng)式與著色

韓友發(fā)， 亢云鳳， 董 婷

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

平面圖的多項(xiàng)式與著色

韓友發(fā)， 亢云鳳， 董 婷

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

研究平面剖分圖的著色性質(zhì)，通過討論圖的色多項(xiàng)式的零點(diǎn)問題，分析對圖的著色保證相鄰的兩個(gè)區(qū)域著不同顏色的最少方法數(shù)目，進(jìn)而給出了平面剖分圖的著色方法數(shù)目的重要性質(zhì).主要研究方法是對平面圖的著色提供了一個(gè)新的研究渠道，即通過色多項(xiàng)式計(jì)算，得出平面剖分前后的著色數(shù)目，進(jìn)而再計(jì)算球面剖分圖的著色數(shù)目.首先，研究“具有一條公共邊的兩個(gè)區(qū)域Gn和Gm，及廣義剖分圖”的著色問題；其次，研究“簡單正多面體及球面的三角剖分圖”的著色問題.

平面圖；色多項(xiàng)式；廣義剖分；三角剖分

紐結(jié)理論是20世紀(jì)以來作為拓?fù)鋵W(xué)的一個(gè)重要部分而發(fā)展起來的.而且在很多領(lǐng)域得到了應(yīng)用，進(jìn)而紐結(jié)理論成了拓?fù)鋵W(xué)中引人入勝的一支，它在數(shù)學(xué)中的重要性日漸上升.1928年由美國數(shù)學(xué)家亞歷山大[1]發(fā)現(xiàn)了亞歷山大多項(xiàng)式，但是該多項(xiàng)式不能區(qū)分紐結(jié)和它的鏡面像，也就是它們相同的亞歷山大多項(xiàng)式.經(jīng)過50多年，1984年新西蘭數(shù)學(xué)家瓊斯[2]找到紐結(jié)新的一個(gè)多項(xiàng)式不變量能夠區(qū)分某些亞歷山大多項(xiàng)式不能區(qū)分的紐結(jié).很快，許多科學(xué)家發(fā)現(xiàn)紐結(jié)理論和許多科學(xué)領(lǐng)域都有聯(lián)系,數(shù)學(xué)家考夫曼[3]試圖用圖式方法來探究紐結(jié)不變量，而且發(fā)現(xiàn)紐結(jié)理論與圖論有密切的聯(lián)系，即紐結(jié)的投影圖與平面圖是一一對應(yīng)的.進(jìn)而在圖論上來探究紐結(jié)的交叉點(diǎn)的符號問題，這樣就涉及在平面圖上的著色問題.平面圖的著色問題的研究來源于圖論中的著色理論.塔特多項(xiàng)式和方括號多項(xiàng)式是紐結(jié)理論和圖論的基本關(guān)系的主要橋梁，尤其是塔特多項(xiàng)式及與色多項(xiàng)式之間的關(guān)系[4-5]對著色問題的研究具有重大的意義.同時(shí)，紐結(jié)理論在統(tǒng)計(jì)力學(xué)、生物DNA分子重組等領(lǐng)域都有著廣泛的應(yīng)用[6-8].筆者就是在分析研究這些成果的基礎(chǔ)上，重點(diǎn)研究圖及剖分圖的著色問題.

1 預(yù)備知識

1.1 圖論中的一些定義

定義1.1一個(gè)圖是一個(gè)偶對V,E:

(1)V是一個(gè)集合，其中的元素稱為頂點(diǎn).

(2)E是無序積V×V中的一個(gè)子集合，其中的元素稱為邊；集合V×V中的元素可在E中出現(xiàn)不止一次.

定義1.2起點(diǎn)和終點(diǎn)相同的路徑稱為閉路徑，閉路又稱為圈.長為k(k即是邊長的個(gè)數(shù))的圈稱為k-圈,k為偶數(shù)時(shí)稱為偶圈，k為奇數(shù)時(shí)，稱為奇圈.

定義1.3圖G稱為多重圖，如果G中有兩個(gè)頂點(diǎn)之間有多重邊或有一個(gè)頂點(diǎn)帶一個(gè)環(huán).

定義1.4平面圖G的對偶圖G*定義如下：G中每一個(gè)面f內(nèi)取一點(diǎn)作G*的一個(gè)頂點(diǎn)f*，G*中的f*、g*相連接e*的充要條件是f*，g*在G中對應(yīng)的面f,g含公共邊e，且使e和e*相交.

定義1.5平面圖G的k-面著色是k種顏色在G的面上的一個(gè)分配，稱面著色的平面圖為k-面可著色.使G為k-面可著色的最小的k稱為G的面色數(shù)，記為x*G.顯然，對任意平面圖G，都有x*G=xG*.

1.2 圖的雙色多項(xiàng)式

首先介紹圖的雙色多項(xiàng)式Z(G)[3]，它有兩個(gè)變量q和v，滿足下面3個(gè)條件：

(1)Z(?)=q;

例

(1)Z()=Z(?)+vZ(?)=q+vq;

P(G)有下列性質(zhì)：

引理1.1[5]在雙色多項(xiàng)式Z(q,v)中，當(dāng)v=-1時(shí)，雙色多項(xiàng)式特殊化為色多項(xiàng)式P(G).P(G)表示對圖G的頂點(diǎn)用q種顏色著色并保證相鄰的兩個(gè)頂點(diǎn)不同色的著色的方法數(shù)目.

引理1.2[5]如果圖G是子圖H和K的不交并，那么P(G)=P(H)P(K).

引理1.3[5]如果圖G是子圖H和K的并，滿足H∩K是一個(gè)頂點(diǎn)，那么

qP(G)=P(H)P(K).

1.3 廣義剖分和三角剖分

定義1.6對于一個(gè)單純復(fù)形K，找到其重心O，把重心O與單形的相應(yīng)的頂點(diǎn)連接起來的一種剖分，稱這種剖分為廣義剖分.重復(fù)上述過程k次得到的圖記為TkK(k≥1).

例單形K的一次廣義剖分.

定義1.7拓?fù)淇臻gX稱為多面體，如果存在單純復(fù)形K與同胚f:|K|?X.這時(shí)把單純復(fù)形K與同胚f組成的對偶(K,f)稱為空間的一個(gè)三角剖分.

2 討論圖和剖分圖的著色數(shù)目

對圖剖分后區(qū)域著色問題進(jìn)行研究，即計(jì)算圖的廣義剖分及三角剖分后的色多項(xiàng)式來進(jìn)一步觀察剖分后圖的著色數(shù)目，看一看剖分前后圖的著色數(shù)目是否有變化，通過前后圖形的著色數(shù)目的對比進(jìn)行一些題目的討論并得到一些結(jié)論.為了便于計(jì)算把區(qū)域圖G轉(zhuǎn)化為其頂點(diǎn)的對偶圖G*來研究.

(1)當(dāng)n是奇數(shù)時(shí)，如果q≥3，則P(G*)≠0.

(2)當(dāng)n是偶數(shù)時(shí)，如果q≥2，則P(G*)≠0.

圖1 Gn與其對偶圖Fig.1 Gn and its dual graph

注這說明n個(gè)區(qū)域圖的著色情況為：當(dāng)區(qū)域數(shù)為偶數(shù)時(shí)，可以用兩種或兩種以上的顏色著色就可以保證相鄰區(qū)域著不同的顏色；而當(dāng)區(qū)域數(shù)為奇數(shù)時(shí)，可以用3種或3種以上的顏色著色可以保證相鄰區(qū)域著不同的顏色.

定理2.1設(shè)G(見圖2)是由Gn和Gm構(gòu)成，且Gn和Gm有一條公共邊，則有

(1)當(dāng)n與m中有一個(gè)為奇數(shù)，且q≥3時(shí)，P(G*)≠0.

(2)當(dāng)n與m都為偶數(shù)，且q≥2時(shí)，P(G*)≠0.

圖2 有一個(gè)公共邊的平面圖和其對偶圖Fig.2 The plane graph with one common edge and its dual graph

證由引理1.2和引理1.3知道

當(dāng)v=-1時(shí),有

由引理2.1知：

n與m中有一個(gè)為奇數(shù)時(shí)，且當(dāng)q≥3時(shí)，P(G*)≠0.

n與m都為偶數(shù)時(shí)，且當(dāng)q≥2時(shí)，P(G*)≠0.

因此定理得證.

定理2.2設(shè)圖G(見圖2)是由Gn和Gm構(gòu)成，且Gn和Gm有一條公共邊，對G進(jìn)行一次廣義剖分后圖T1G(見圖3),則有：當(dāng)q≥3時(shí),P(T1G*)≠0.

圖3 廣義剖分的平面圖Fig.3 Generalized division plane graph

證由引理1.2與引理1.3有

令v=-1時(shí),有

注1定理說明有一個(gè)公共邊的兩個(gè)圓盤區(qū)域經(jīng)一次廣義剖分后可以用3種或3種以上的顏色著色能保證相鄰區(qū)域著不同的顏色.給出了研究平面圖著色的一種方法.

注2應(yīng)用本文的方法可以討論多面體及球面的三角剖分圖的著色數(shù)目的性質(zhì).

[1] ALEXANDER J W.Topological invariants of knots and links[J].Trans Amer Math Soci,1928,30(2):275-306.

[2] JONES V F R.Hecke algebra representations of braid groups and link polynomials[J].Annals of Maths,1987,126:335-388.

[3] KAUFFMAN L H.New invariants in the theory of knots[J].The American Mathematical Monthly,1988,95(3):195-242.

[4] BOLLOBA B.Modern graph theory[M].Berlin:Springer,1998:335-378.

[5] TUTTE W T.Graph theory[M].Addison-Wesley, Reading, MA, 1969:253-284.

[6] BAXTER R J.q colorings of the triangular lattice[J].J Phys A:Math Gen,1986,19:2821-2839.

[7] ERNST C,SUMMERS D W.A calculus for rational tangles:applications to DNA recombination[J].Math Proc Camb Phil Soc,1990,108：489-515.

[8] ERNST C,SUMNERS D W.Solving tangles equations arising in a DNA recombination model[J].Math Proc Camb Phil Soc,1999,126:23-36.

[9] 韓友發(fā)，王英姣，沙欣，等.某些平面圖著色的性質(zhì)[J].吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2016，37(1)：36-40.

PolynomialofcoloringtheGraph

HANYoufa,KANGYunfeng,DONGTing

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

In this paper, we study properties of division plane graph with coloring by discussing the zeros of chromatic polynomial of graphs. We analyze the minimum number of ways to faces by coloring the graph, so that no two adjacent faces receive the same color, giving the important properties of the number of ways to color plane division figure. This paper gives a new study method of coloring plane division figure.We compute the dichromatic polynomial of graphs, summarize the coloring properties of decomposing plane before and after,and discuss the coloring properties of sphere division figure.We discuss the coloring number of the regional figureGnandGmwith a public side and their generalized division figure, and also discuss the coloring number of the triangulation figure of simple polyhedron and sphere.

plane graph;chromatic polynomial;generalized division;triangulation

O189.3

:A

2017-04-05

國家自然科學(xué)基金資助項(xiàng)目(11471151)

韓友發(fā)(1962- )，男，吉林長春人，遼寧師范大學(xué)教授，博士.

1000-1735(2017)03-0289-04

10.11679/lsxblk2017030289