Flower snark圖的書式嵌入頁數(shù)及2-頁交叉數(shù)問題

董曉媛，馬登舉

(1.南通師范高等專科學(xué)校初等教育學(xué)院，江蘇 南通 226007；2.南通大學(xué)理學(xué)院，江蘇 南通 226019)

1 預(yù)備知識

一本書是由一個書脊和k個書頁組成的，這k個書頁有一個共同的邊界就是書脊.將一個圖G嵌入書就是將G的頂點(diǎn)按照一定的順序放在書脊上，而把G的邊畫在書頁內(nèi)，使得圖G在同一頁的邊不相交.在所有的畫法中，有一個最小的書頁數(shù)，稱之為圖G的書式嵌入頁數(shù)，記為PN(G).研究書式嵌入頁數(shù)問題的動機(jī)之一是書式嵌入在VLSI電路板設(shè)計、互聯(lián)網(wǎng)的容錯陣列設(shè)計等問題中的應(yīng)用[1-4].圖的書式嵌入首先由Atneosen[5]提出，Kainen[6]正式給出定義.Ollmann[7]首先提出書頁數(shù)問題.把完全圖K4的所有頂點(diǎn)按一定的順序放到虛線上也就是書脊上，得到完全圖K4的一個書式嵌入，如圖1所示.

圖1 完全圖K4的書式嵌入

研究交叉數(shù)的主要目的之一是圖的交叉數(shù)在超大規(guī)模集成電路設(shè)計中的應(yīng)用[8-10].一個圖的畫法滿足下列條件：(1)相鄰的2條邊不交叉；(2)2條邊相交叉不多于一次；(3)2條邊不相切；(4)沒有3條邊交于同一個頂點(diǎn).在圖G的所有畫法中交叉點(diǎn)數(shù)最少的畫法所含的交叉點(diǎn)的數(shù)目稱為圖G的交叉數(shù)，記為cr(G).把圖G嵌入一個2-頁書，在這個2頁書上的所有畫法中，使得交叉點(diǎn)數(shù)最少的畫法所含的交叉點(diǎn)的數(shù)目稱為圖G的2-頁交叉數(shù)，記為cr2(G).Garey等[11]指出計算簡單圖的交叉數(shù)是NP-困難的.由于這兩個問題都是NP-困難的，所以不太容易得到通用的簡易算法.

圖2 Fn的一個畫法

snark圖是源自3-邊著色猜想而構(gòu)造的圖.若圖是2邊連通的3-正則圖且不可3-邊著色，同時圍長至少為5，也無非平凡3-邊割集，則稱為snark圖.廣義Petersen圖是最小的snark圖.1975年以來，更多的snark圖被發(fā)現(xiàn)，人們對snark圖進(jìn)行了很多研究，特別是Flower snark，Goldberg snark，Blanu?a snark圖.給出Flower snark圖的定義：Gn是一個簡單的非平凡的連通的3-正則圖，點(diǎn)集V(G)={ki，yi，zi，xi|0≤i≤n-1}，邊集E(G)={kiki+1，yiyi+1，zizi+1，xiki，xiyi，xizi|0≤i≤n-1}，點(diǎn)的標(biāo)號對n取模，Hn可以由Gn通過用邊yn-1z0，zn-1y0替換yn-1y0，zn-1z0得到.如果n為奇數(shù)且n≥5，Hn被稱為Flower snark圖，其他的圖被稱為Flower snark圖的相關(guān)圖，把這些圖統(tǒng)一用Fn來表示，見圖2.顯然，k0k1…kn-1k0為一個n圈，y0y1…yn-1z0z1…zn-1y0為一個2n圈，xi與yi，zi，ki(0≤i≤n-1)都有邊相連.

本文將給出Flower snark圖的書式嵌入頁數(shù)的簡單證明，以及Flower snark圖的2-頁交叉數(shù)結(jié)果.

2 主要結(jié)論

引理1PN(G)=1，當(dāng)且僅當(dāng)G為外平面圖.

引理2PN(G)≤2，當(dāng)且僅當(dāng)G是平面Hamilton圖的子圖.

由引理2顯然可以得到如下結(jié)論：

引理3 若G為非平面圖，則PN(G)≥3.

引理4 完全二部圖K3，3的書式嵌入頁數(shù)PN(G)=3.

2008年，Zheng等[12]研究了Flower snark圖的交叉數(shù)，由文獻(xiàn)[12]可得到引理5：

引理5 當(dāng)n≥6時，F(xiàn)lower snark圖的交叉數(shù)cr(Fn)=n.

定理1 當(dāng)n≥3時，F(xiàn)lower snark圖的書式嵌入頁數(shù)PN(Fn)=3.

圖3 Flower snark圖中包含了同構(gòu)于K3，3的子圖

證明觀察Flower snark圖，可發(fā)現(xiàn)Flower snark圖中包含了同構(gòu)于K3，3的子圖，見圖3.

由引理4可知，K3，3的書式嵌入頁數(shù)PN(G)=3，所以Flower snark圖的書式嵌入頁數(shù)PN(Fn)≥3.

給出Flower snark圖的一個書式嵌入畫法：

圖4 Flower snark圖的一個書式嵌入畫法

由Flower snark圖Fn的定義，它包含了點(diǎn)集V(G)={ki，yi，zi，xi|0≤i≤n-1}，邊集E(G)={kiki+1，yiyi+1，zizi+1，xiki，xiyi，xizi|0≤i≤n-1}.顯然，F(xiàn)lower snark圖中包含了一個n圈k0k1…kn-1k0，一個2n圈y0y1…yn-1z0z1…zn-1y0，并且當(dāng)0≤i≤n-1時xi與yi，zi，ki都有邊相連.

在書脊上按照z0z1…zn-1y0y1…yn-1xn-1xn-2…x1x0k0k1…kn-1的順序依次排列各頂點(diǎn).

第一頁：y0y1…yn-1z0z1…zn-1y0為一個2n圈，依次連接各頂點(diǎn)形成圈，不形成交叉點(diǎn).k0k1…kn-1k0為一個n圈，先依次連接k0k1…kn-1，不形成交叉點(diǎn)，kn-1與k0的連線留到下一頁.又因?yàn)閤i與yi，zi，ki都有邊相連，把xi與ki都相連，不產(chǎn)生交叉點(diǎn).

第二頁：把xi與zi都相連，不產(chǎn)生交叉點(diǎn).同時kn-1與k0相連.

第三頁：把xi與yi都相連，不產(chǎn)生交叉點(diǎn).

由定義，把Flower snark圖的每條邊都相連了，共3頁，完成Flower snark圖的一個書式嵌入畫法，見圖4.

從給出的畫法可以看出PN(Fn)≤3.

綜上，當(dāng)n≥3時，F(xiàn)lower snark圖的書式嵌入頁數(shù)PN(Fn)=3.

定理2 當(dāng)n≥6時，F(xiàn)lower snark圖的2-頁交叉數(shù)cr2(Fn)=n.

圖5 Flower snark圖的一個2-頁書畫法

證明由引理5可知，當(dāng)n≥6時，cr(Fn)=n.又因?yàn)閏r2(Fn)≥cr(Fn).這樣得到了當(dāng)n≥6時，cr2(Fn)的下界，即cr2(Fn)≥n.

由Flower snark圖Fn的定義可知它包含了一個n圈k0k1…kn-1k0，一個2n圈y0y1…yn-1z0z1…zn-1y0.并且當(dāng)0≤i≤n-1時xi與yi，zi，ki都有邊相連.由2-頁書畫法的定義可知，把一個圖嵌入到這本書中，這個圖的每個頂點(diǎn)都位于書脊上，每條邊都位于同一頁上.

在書脊上按照y0x0z0y1x1z1y2x2z2…yn-1xn-1zn-1kn-1kn-2…k1k0的順序依次排列各頂點(diǎn).首先，k0k1…kn-1k0為一個n圈，依次連接各點(diǎn)，不產(chǎn)生交叉點(diǎn).y0y1…yn-1z0z1…zn-1y0為一個2n圈，依次連接各點(diǎn)，邊zn-2zn-1與yn-1z0相交共產(chǎn)生1個交叉點(diǎn).其次，xi分別與yi，zi相連，不產(chǎn)生交叉點(diǎn).最后，xi與ki相連，當(dāng)0≤i≤n-2時，每條邊xiki都與yiyi+1產(chǎn)生一個交叉點(diǎn)，共n-1個交叉點(diǎn).當(dāng)i=n-1時，每條邊xn-1kn-1不與其他邊產(chǎn)生交叉點(diǎn).綜上，共產(chǎn)生n個交叉點(diǎn).

因此得到一個Flower snark圖的2-頁畫法，并發(fā)現(xiàn)共產(chǎn)生了n個交叉點(diǎn)，見圖5.從而得到cr2(Fn)的一個上界：當(dāng)n≥6時，cr2(Fn)≤n.

綜上，當(dāng)n≥6時，F(xiàn)lower snark圖的2-頁交叉數(shù)，cr2(Fn)=n.