循環(huán)圖C(3k，k)的2-頁(yè)交叉數(shù)

董曉媛，馬登舉

(1.南通師范高等專(zhuān)科學(xué)校數(shù)理系，江蘇 南通 226007；2.南通大學(xué)理學(xué)院，江蘇 南通 226000)

1 預(yù)備知識(shí)

研究交叉數(shù)的主要?jiǎng)訖C(jī)之一是圖的交叉數(shù)在超大規(guī)模集成電路設(shè)計(jì)中的應(yīng)用.國(guó)內(nèi)外許多學(xué)者都研究過(guò)圖的交叉數(shù)問(wèn)題，但是到目前為止還沒(méi)有找到能確定任意圖的交叉數(shù)的算法.

圖的一個(gè)平面畫(huà)法是將圖的頂點(diǎn)用平面上的不同點(diǎn)表示，邊用簡(jiǎn)單曲線(xiàn)段表示，使得表示每條邊的曲線(xiàn)不經(jīng)過(guò)除他們的端點(diǎn)外的其他點(diǎn).同時(shí)，還要求一個(gè)圖的畫(huà)法滿(mǎn)足下列條件：(1)相鄰的兩條邊不交叉；(2)兩條邊相交叉不多于一次；(3)兩條邊不相切；(4)沒(méi)有3條邊交于同一個(gè)頂點(diǎn).在圖G的所有畫(huà)法中，交叉點(diǎn)數(shù)最少的畫(huà)法所含的交叉點(diǎn)的數(shù)目稱(chēng)為圖G的交叉數(shù)，記為cr(G).

一個(gè)k頁(yè)書(shū)是由一條直線(xiàn)l和k≥1個(gè)半平面組成，使得每個(gè)半平面的邊界都是直線(xiàn)l.將每個(gè)半平面稱(chēng)為頁(yè)，而直線(xiàn)l稱(chēng)為書(shū)脊.一個(gè)圖G在一個(gè)k頁(yè)書(shū)上的畫(huà)法是指將這個(gè)圖的每個(gè)頂點(diǎn)都位于書(shū)脊上，每條邊都畫(huà)在同一頁(yè)上.圖G在一個(gè)k頁(yè)書(shū)上的所有畫(huà)法的交叉點(diǎn)數(shù)最少的畫(huà)法所含的交叉點(diǎn)的數(shù)目稱(chēng)為圖G的2頁(yè)交叉數(shù)，記為cr2(G).由于一個(gè)2頁(yè)書(shū)就可以形成一個(gè)平面，容易得到cr(G)≤cr2(G).

1987年，Chung等[1]對(duì)一類(lèi)書(shū)圖進(jìn)行了研究.眾所周知，一本書(shū)是由一個(gè)書(shū)脊和k個(gè)書(shū)頁(yè)組成的，這k個(gè)書(shū)頁(yè)有一個(gè)共同的邊界就是書(shū)脊.把一個(gè)圖嵌入到這本書(shū)中，這個(gè)圖的每個(gè)頂點(diǎn)都位于書(shū)脊上，每條邊都位于同一頁(yè)上.最近，書(shū)圖已經(jīng)得到了廣泛的研究.[3-4]現(xiàn)在，如果這本書(shū)有k頁(yè)，并且允許邊之間有交叉，那么就可以研究這個(gè)圖的k-頁(yè)書(shū)交叉數(shù).1993年，Garey等[2]證明了確定圖的交叉數(shù)是一個(gè)NP-完全問(wèn)題.

循環(huán)圖C(n，k)是這樣一個(gè)圖，它的頂點(diǎn)集為V={ui|0≤i≤n-1}，它的邊集為

E={uiuj|0≤i≤n-1，0≤j≤n-1，i≡j(modk)}∪Cn(u0…un-1u0).

循環(huán)圖C(n，k)的2-頁(yè)交叉數(shù)cr2(C(n，k))是循環(huán)圖C(n，k)的所有2-頁(yè)書(shū)畫(huà)法中交叉點(diǎn)數(shù)最少的畫(huà)法所得到的交叉數(shù).

2005年，Liu等[5]研究了一類(lèi)循環(huán)圖C(3k，k)的交叉數(shù)，當(dāng)k≥3時(shí)，有cr(C(3k，k))=k.本文在此基礎(chǔ)上，研究這類(lèi)循環(huán)圖C(3k，k)的2-頁(yè)交叉數(shù)，并得到了其準(zhǔn)確值cr2(C(3k，k))=k(k≥3).

為了更清楚地陳述后面交叉數(shù)的結(jié)果，給出Jordan曲線(xiàn)定理的內(nèi)容如下：

Jordan曲線(xiàn)定理設(shè)J是平面上的一條Jordan曲線(xiàn)，平面的剩余部分被分成兩個(gè)不相交的開(kāi)集，稱(chēng)為J的內(nèi)部和外部，分別記為IntJ和ExtJ，則連接IntJ和ExtJ的點(diǎn)的任何連線(xiàn)必在某點(diǎn)和J相交.其中一條Jordan曲線(xiàn)是指一條連續(xù)的，自身不交的，起點(diǎn)和終點(diǎn)相重合的曲線(xiàn).

2 主要結(jié)論

文獻(xiàn)[5]研究了一類(lèi)循環(huán)圖C(3k，k)的交叉數(shù)，得到如下結(jié)論：

引理1[5]當(dāng)k≥3時(shí)，循環(huán)圖C(3k，k)的交叉數(shù)為

cr(C(3k，k))=k.

定理1當(dāng)k≥3時(shí)，循環(huán)圖C(3k，k)的2-頁(yè)交叉數(shù)為

cr2(C(3k，k))=k.

證明由引理1可知，cr(C(3k，k))=k.又因?yàn)閏r2(C(3k，k))≥cr(C(3k，k))，從而得到了cr2(C(3k，k))的下界，即

cr2(C(3k，k))≥k.

由循環(huán)圖C(3k，k)的定義可知，循環(huán)圖C(3k，k)是由k個(gè)互不相交的3-圈

Ei={uiui+k，uiui+2k，ui+kui+2k，0≤i≤k-1}

和一個(gè)3k-圈C3k=(u0…u3k-1u0)組成的.由2-頁(yè)書(shū)畫(huà)法的定義可知，把一個(gè)圖嵌入到這本書(shū)中，這個(gè)圖的每個(gè)頂點(diǎn)都位于書(shū)脊上，每條邊都位于同一頁(yè)上.

當(dāng)k=3時(shí)，給出C(9，3)的一個(gè)畫(huà)法，如圖1所示.

由循環(huán)圖C(9，3)的定義可知，循環(huán)圖C(9，3)是由3個(gè)互不相交的3-圈(u0u3u6u0)，(u1u4u7u1)，(u2u5u8u2)和一個(gè)9-圈C9=(u0…u8u0)組成的.為了減少交叉的點(diǎn)數(shù)，把頂點(diǎn)的順序進(jìn)行調(diào)整.

首先按照3-圈的頂點(diǎn)順序把頂點(diǎn)分成3組

{u0，u3，u6}，{u1，u4，u7}，{u2，u5，u8}.

然后對(duì)每組的頂點(diǎn)進(jìn)行組內(nèi)微調(diào)，當(dāng)每組下標(biāo)最大的點(diǎn)在中間，每?jī)山M交界處的頂點(diǎn)下標(biāo)相連時(shí)，可以盡量減少交叉點(diǎn)的個(gè)數(shù).從而得到一種循環(huán)圖C(9，3)的2-頁(yè)書(shū)的畫(huà)法，它的頂點(diǎn)順序?yàn)?/p>

{u3，u6，u0，u1，u7，u4，u5，u8，u2}.

顯然cr2(C(9，3))≤3.又因?yàn)?/p>

cr2(C(9，3))≥cr(C(9，3))，cr(C(9，3))=3，

所以cr2(C(9，3))=3.

當(dāng)k=4時(shí)，給出C(12，4)的一個(gè)畫(huà)法，如圖2所示.

圖1 循環(huán)圖C(9，3)的一種2-頁(yè)書(shū)的畫(huà)法

圖2 循環(huán)圖C(12，4)的一種2-頁(yè)書(shū)的畫(huà)法

由循環(huán)圖C(12，4)的定義可知，循環(huán)圖C(12，4)是由4個(gè)互不相交的3-圈(u0u4u8u0)，(u1u5u9u1)，(u2u6u10u2)，(u3u7u11u3)和一個(gè)12-圈C12=(u0…u11u0)組成的.為了減少交叉的點(diǎn)數(shù)，把頂點(diǎn)的順序進(jìn)行調(diào)整.

首先按照3-圈的頂點(diǎn)順序把頂點(diǎn)分成4組

{u0，u4，u8}，{u1，u5，u9}，{u2，u6，u10}，{u3，u7，u11}.

然后對(duì)每組的頂點(diǎn)進(jìn)行組內(nèi)微調(diào)，當(dāng)每組下標(biāo)最大的點(diǎn)在中間，每?jī)山M交界處的頂點(diǎn)下標(biāo)相連時(shí)，可以盡量減少交叉點(diǎn)的個(gè)數(shù).從而得到一種循環(huán)圖C(12，4)的2-頁(yè)書(shū)的畫(huà)法，它的頂點(diǎn)順序?yàn)?/p>

{u4，u8，u0，u1，u9，u5，u6，u10，u2，u3，u11，u7}.

顯然cr2(C(12，4))≤4.又因?yàn)?/p>

cr2(C(12，4))≥cr(C(12，4))，cr(C(12，4))=4，

所以cr2(C(12，4))=4.

下面給出C(3k，k)的一個(gè)畫(huà)法.

當(dāng)k為奇數(shù)時(shí).由循環(huán)圖C(3k，k)的定義可知，循環(huán)圖C(3k，k)是由k個(gè)互不相交的3-圈Ei={uiui+k，uiui+2k，ui+kui+2k，0≤i≤k-1}，和一個(gè)3k-圈C3k=(u0…u3k-1u0)組成的.由2-頁(yè)書(shū)畫(huà)法的定義可知，把一個(gè)圖嵌入到這本書(shū)中，這個(gè)圖的每個(gè)頂點(diǎn)都位于書(shū)脊上，每條邊都位于同一頁(yè)上.為了減少交叉的點(diǎn)數(shù)，同樣把頂點(diǎn)的順序進(jìn)行調(diào)整.

首先按照3-圈的頂點(diǎn)順序把頂點(diǎn)分成k組

{ui，ui+k，ui+2k}，i=0，1，2，…，k-1.

然后對(duì)每組的頂點(diǎn)進(jìn)行組內(nèi)微調(diào)，可以發(fā)現(xiàn)，當(dāng)每組下標(biāo)最大的點(diǎn)在中間，每?jī)山M交界處的頂點(diǎn)下標(biāo)相連時(shí)，可以盡量減少交叉點(diǎn)的個(gè)數(shù).從而得到一種循環(huán)圖C(3k，k)的2-頁(yè)書(shū)的畫(huà)法，它的頂點(diǎn)順序?yàn)?/p>

{uk，u2k，u0，u1，u2k+1，uk+1，uk+2，u2k+2，u2，u3，u2k+3，uk+3，…，uk-2，u3k-2，u2k-2，u2k-1，u3k-1，uk-1}.

先給出3k-圈C3k=(u0…u3k-1u0)的一個(gè)畫(huà)法，如圖3所示，u2k-1u2k與ukuk+1產(chǎn)生一個(gè)交叉點(diǎn)，uk-2uk-1與u3k-1u0產(chǎn)生一個(gè)交叉點(diǎn)，共產(chǎn)生2個(gè)交叉點(diǎn).

再分別畫(huà)出k個(gè)3-圈，如圖4所示.第一個(gè)3-圈E0={u0uk，u0u2k，uku2k}與3k-圈的邊沒(méi)有產(chǎn)生交叉點(diǎn).接下來(lái)的k-2個(gè)3-圈，每個(gè)圈與3k-圈的邊都產(chǎn)生一個(gè)交叉點(diǎn)，最后一個(gè)3-圈Ek={uk-1u2k-1，u2k-1u3k-1，uk-1u3k-1}與3k-圈的邊沒(méi)有產(chǎn)生交叉點(diǎn).

綜上，共產(chǎn)生了k個(gè)交叉點(diǎn).從而得到cr2(C(3k，k))的一個(gè)上界：當(dāng)k≥3時(shí)，cr2(C(3k，k))≤k.

圖3 k為奇數(shù)時(shí)，C(3k，k)的2-頁(yè)書(shū)畫(huà)法(部分)

圖4 k為奇數(shù)時(shí)，C(3k，k)的2-頁(yè)書(shū)畫(huà)法

圖5 k為偶數(shù)時(shí)，C(3k，k)的2-頁(yè)書(shū)畫(huà)法

當(dāng)k為偶數(shù)時(shí).頂點(diǎn)與k為奇數(shù)時(shí)稍有差距，同樣把頂點(diǎn)的順序進(jìn)行調(diào)整.

首先按照3-圈的頂點(diǎn)順序把頂點(diǎn)分成k組

{ui，ui+k，ui+2k}，i=0，1，2，…，k-1.

然后對(duì)每組的頂點(diǎn)進(jìn)行組內(nèi)微調(diào)，當(dāng)每組下標(biāo)最大的點(diǎn)在中間，每?jī)山M交界處的頂點(diǎn)下標(biāo)相連時(shí)，可以盡量減少交叉點(diǎn)的個(gè)數(shù).從而得到一種循環(huán)圖C(3k，k)的2-頁(yè)書(shū)的畫(huà)法，它的頂點(diǎn)順序?yàn)?/p>

{uk，u2k，u0，u1，u2k+1，uk+1，uk+2，u2k+2，u2，u3，u2k+3，uk+3，…，u2k-2，u3k-2，uk-2，uk-1，u3k-1，u2k-1}.

類(lèi)似的方法，可得到它的一個(gè)上界cr2(C(3k，k))≤k.如圖5所示.

通過(guò)以上分析不難發(fā)現(xiàn)，不論k是奇數(shù)還是偶數(shù)，循環(huán)圖C(3k，k)的2-頁(yè)交叉數(shù)都為cr2(C(3k，k))=k.故當(dāng)k≥3時(shí)，循環(huán)圖C(3k，k)的2-頁(yè)交叉數(shù)cr2(C(3k，k))=k.