平環(huán)圖著色的性質(zhì)

韓友發(fā), 王 雪, 李丹丹

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

紐結(jié)理論是20世紀(jì)以來作為拓?fù)鋵W(xué)的一個(gè)重要部分而發(fā)展起來的，其核心工作之一就是研究紐結(jié)在連續(xù)變形下保持不變的特性.由于紐結(jié)與鏈環(huán)既直觀又奧妙，紐結(jié)理論成為拓?fù)鋵W(xué)中引人入勝的一個(gè)分支，被廣大的專家學(xué)者所重視，這些專家一直在尋找鑒別力強(qiáng)的紐結(jié)不變量.1928年，Alexander取得了重大突破，他將每個(gè)紐結(jié)聯(lián)系上一個(gè)多項(xiàng)式不變量，稱為Alexander多項(xiàng)式[1-2]. 1969年，Conway[3]研究了Alexander多項(xiàng)式的性質(zhì)時(shí)，發(fā)現(xiàn)了一個(gè)計(jì)算公式，進(jìn)而給出了Alexander多項(xiàng)式的遞推公式，但是這個(gè)多項(xiàng)式不能區(qū)分鏡面像.1984年，Jones[4]在研究泛函算子代數(shù)時(shí)給出了一個(gè)新的紐結(jié)不變量，后來稱為瓊斯多項(xiàng)式，它可以區(qū)別某型紐結(jié)及其鏡面像.到了1988年，Kauffman[5]一般化了Jones多項(xiàng)式，這些思想和方法在紐結(jié)理論的研究中發(fā)揮重要作用.同時(shí)，很多專家學(xué)者發(fā)現(xiàn)了紐結(jié)理論與圖論有著很多內(nèi)在的聯(lián)系，即紐結(jié)的平面投影圖與它的平面圖是建立了一一對應(yīng)的.由于這些發(fā)現(xiàn)極大促進(jìn)了紐結(jié)理論自身發(fā)展，為紐結(jié)理論在圖論的應(yīng)用提供有效的思想和方法.

1 預(yù)備知識

1.1 圖的相關(guān)定義

定義1.1一個(gè)圖是一個(gè)序偶〈V,E〉，記為G=(V,E),其中：

(1)V是一個(gè)有限的非空集合，稱為頂點(diǎn)集合，其元素稱為頂點(diǎn)或點(diǎn).用V(G)表示頂點(diǎn)集合；

(2)E是由V中的點(diǎn)組成的無序?qū)?gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對在E中可以重復(fù)出現(xiàn)多次.用E(G)表示邊的集合.

定義1.2如果V(G′)?V(G),E(G′)?E(G)，那么稱圖G′為圖G的子圖.

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

定義1.4圖G的k-著色是k種顏色在G的面上的分配，使得相鄰的兩個(gè)頂點(diǎn)涂不同的顏色，就稱面著色的圖為k-可著色.使G為k-可著色的最小k稱為G的著色數(shù)，記為x*(G).

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

注本文研究平面圖H著色的性質(zhì)，把H的各個(gè)區(qū)域涂上顏色，使其相鄰的面(有公共邊的面)有不同的顏色，從而可以轉(zhuǎn)化為研究對偶圖H*的著色性質(zhì).

1.2 圖的多項(xiàng)式

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

(1)Z(?)=q;

(2)Z(?G)=qZ(G);

引理1.1[6]在圖多項(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[7-8]如果圖G是子圖G1和G2的不交并，那么P(G)=P(G1)P(G2).

引理1.3[7-8]如果圖G是子圖G1和G2的并，滿足G1∩G2是一個(gè)頂點(diǎn)，那么

qP(G)=P(G1)P(G2).

1.3 廣義剖分

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

例單形K的一次廣義三角剖分(圖1).

圖1 三角形的一次廣義剖分

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

2 平環(huán)平面圖的著色性質(zhì)

圖2 帶有n區(qū)域的平環(huán)Gn和它的對偶圖

注該引理的結(jié)論從幾何直觀上也容易得到.主要是下面的定理證明時(shí)要用到引理證明中的思想和公式.

定理2.1設(shè)Gn是平環(huán)中含有n個(gè)區(qū)域的圖，對區(qū)域圖Gn進(jìn)行一次廣義剖分后，所得圖T1Gn的著色數(shù)目與Gn的著色數(shù)目一樣(圖3).

證

圖3 Gn的廣義剖分T1Gn和它的對偶圖

根據(jù)雙色多項(xiàng)式的計(jì)算法則有

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

因此，對帶有n區(qū)域圖Gn進(jìn)行一次廣義三角剖分后，這個(gè)圖的涂色數(shù)目與剖分前的涂色數(shù)目具有不變的性質(zhì). 從而定理得證.

定理2.2設(shè)圖G是由區(qū)域圖Gt和區(qū)域圖Gs組成，并且它們具有一條公共邊(圖4)，則有

(1)當(dāng)s，t中有一個(gè)為奇數(shù)時(shí)，若q≥3，則P(G*)≠0;

(2)當(dāng)s，t均為偶數(shù)時(shí)，若q≥2，則P(G*)≠0.

圖4 兩個(gè)帶有一個(gè)公共邊的平環(huán)區(qū)域的平面圖和它的對偶圖

證

由引理1.1和引理1.2可知:

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

討論情況如下：

①當(dāng)t為奇數(shù)，s為偶數(shù)時(shí)，

②當(dāng)t為偶數(shù)，s為奇數(shù)時(shí)，

③當(dāng)t，s均為奇數(shù)時(shí)，

④當(dāng)t，s均為偶數(shù)時(shí)，

從而定理得證.

定理2.3設(shè)圖G是由區(qū)域圖Gt和區(qū)域圖Gs組成，且具有一條公共邊，對G進(jìn)行一次廣義剖分后，所得圖為T1G(圖5),則有

(1)當(dāng)t，s中有一個(gè)為奇數(shù)時(shí)，若q≥3，則P(T1G*)≠0;

(2)當(dāng)t，s均為偶數(shù)時(shí)，若q≥2，則P(T1G*)≠0.

圖5 平面圖G的廣義剖分和它的對偶圖T1G

①當(dāng)t為偶數(shù)，s為奇數(shù)時(shí)

當(dāng)q≥3時(shí)，P(T1G*)≠0.

②同理可知，當(dāng)t為奇數(shù)，s為偶數(shù)時(shí)，當(dāng)q≥3時(shí)，P(T1G*)≠0.

③當(dāng)t,s均為奇數(shù)時(shí)

當(dāng)q≥3時(shí)，P(T1G*)≠0.

④當(dāng)t,s均為偶數(shù)時(shí)

當(dāng)q≥2時(shí)，P(T1G*)≠0.

從而定理得證.