循環圖C(3k，k)的2-頁交叉數

董曉媛，馬登舉

(1.南通師范高等專科學校數理系，江蘇 南通 226007；2.南通大學理學院，江蘇 南通 226000)

1 預備知識

研究交叉數的主要動機之一是圖的交叉數在超大規模集成電路設計中的應用.國內外許多學者都研究過圖的交叉數問題，但是到目前為止還沒有找到能確定任意圖的交叉數的算法.

圖的一個平面畫法是將圖的頂點用平面上的不同點表示，邊用簡單曲線段表示，使得表示每條邊的曲線不經過除他們的端點外的其他點.同時，還要求一個圖的畫法滿足下列條件：(1)相鄰的兩條邊不交叉；(2)兩條邊相交叉不多于一次；(3)兩條邊不相切；(4)沒有3條邊交于同一個頂點.在圖G的所有畫法中，交叉點數最少的畫法所含的交叉點的數目稱為圖G的交叉數，記為cr(G).

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

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

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

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

循環圖C(n，k)的2-頁交叉數cr2(C(n，k))是循環圖C(n，k)的所有2-頁書畫法中交叉點數最少的畫法所得到的交叉數.

2005年，Liu等[5]研究了一類循環圖C(3k，k)的交叉數，當k≥3時，有cr(C(3k，k))=k.本文在此基礎上，研究這類循環圖C(3k，k)的2-頁交叉數，并得到了其準確值cr2(C(3k，k))=k(k≥3).

為了更清楚地陳述后面交叉數的結果，給出Jordan曲線定理的內容如下：

Jordan曲線定理設J是平面上的一條Jordan曲線，平面的剩余部分被分成兩個不相交的開集，稱為J的內部和外部，分別記為IntJ和ExtJ，則連接IntJ和ExtJ的點的任何連線必在某點和J相交.其中一條Jordan曲線是指一條連續的，自身不交的，起點和終點相重合的曲線.

2 主要結論

文獻[5]研究了一類循環圖C(3k，k)的交叉數，得到如下結論：

引理1[5]當k≥3時，循環圖C(3k，k)的交叉數為

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

定理1當k≥3時，循環圖C(3k，k)的2-頁交叉數為

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

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

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

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

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

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

當k=3時，給出C(9，3)的一個畫法，如圖1所示.

由循環圖C(9，3)的定義可知，循環圖C(9，3)是由3個互不相交的3-圈(u0u3u6u0)，(u1u4u7u1)，(u2u5u8u2)和一個9-圈C9=(u0…u8u0)組成的.為了減少交叉的點數，把頂點的順序進行調整.

首先按照3-圈的頂點順序把頂點分成3組

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

然后對每組的頂點進行組內微調，當每組下標最大的點在中間，每兩組交界處的頂點下標相連時，可以盡量減少交叉點的個數.從而得到一種循環圖C(9，3)的2-頁書的畫法，它的頂點順序為

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

顯然cr2(C(9，3))≤3.又因為

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

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

當k=4時，給出C(12，4)的一個畫法，如圖2所示.

圖1 循環圖C(9，3)的一種2-頁書的畫法

圖2 循環圖C(12，4)的一種2-頁書的畫法

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

首先按照3-圈的頂點順序把頂點分成4組

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

然后對每組的頂點進行組內微調，當每組下標最大的點在中間，每兩組交界處的頂點下標相連時，可以盡量減少交叉點的個數.從而得到一種循環圖C(12，4)的2-頁書的畫法，它的頂點順序為

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

顯然cr2(C(12，4))≤4.又因為

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

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

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

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

首先按照3-圈的頂點順序把頂點分成k組

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

然后對每組的頂點進行組內微調，可以發現，當每組下標最大的點在中間，每兩組交界處的頂點下標相連時，可以盡量減少交叉點的個數.從而得到一種循環圖C(3k，k)的2-頁書的畫法，它的頂點順序為

{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)的一個畫法，如圖3所示，u2k-1u2k與ukuk+1產生一個交叉點，uk-2uk-1與u3k-1u0產生一個交叉點，共產生2個交叉點.

再分別畫出k個3-圈，如圖4所示.第一個3-圈E0={u0uk，u0u2k，uku2k}與3k-圈的邊沒有產生交叉點.接下來的k-2個3-圈，每個圈與3k-圈的邊都產生一個交叉點，最后一個3-圈Ek={uk-1u2k-1，u2k-1u3k-1，uk-1u3k-1}與3k-圈的邊沒有產生交叉點.

綜上，共產生了k個交叉點.從而得到cr2(C(3k，k))的一個上界：當k≥3時，cr2(C(3k，k))≤k.

圖3 k為奇數時，C(3k，k)的2-頁書畫法(部分)

圖4 k為奇數時，C(3k，k)的2-頁書畫法

圖5 k為偶數時，C(3k，k)的2-頁書畫法

當k為偶數時.頂點與k為奇數時稍有差距，同樣把頂點的順序進行調整.

首先按照3-圈的頂點順序把頂點分成k組

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

然后對每組的頂點進行組內微調，當每組下標最大的點在中間，每兩組交界處的頂點下標相連時，可以盡量減少交叉點的個數.從而得到一種循環圖C(3k，k)的2-頁書的畫法，它的頂點順序為

{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}.

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

通過以上分析不難發現，不論k是奇數還是偶數，循環圖C(3k，k)的2-頁交叉數都為cr2(C(3k，k))=k.故當k≥3時，循環圖C(3k，k)的2-頁交叉數cr2(C(3k，k))=k.