Flower snark图的书式嵌入页数及2-页交叉数问题

董晓媛，马登举

(1.南通师范高等专科学校初等教育学院，江苏 南通 226007；2.南通大学理学院，江苏 南通 226019)

1 预备知识

一本书是由一个书脊和k个书页组成的，这k个书页有一个共同的边界就是书脊.将一个图G嵌入书就是将G的顶点按照一定的顺序放在书脊上，而把G的边画在书页内，使得图G在同一页的边不相交.在所有的画法中，有一个最小的书页数，称之为图G的书式嵌入页数，记为PN(G).研究书式嵌入页数问题的动机之一是书式嵌入在VLSI电路板设计、互联网的容错阵列设计等问题中的应用[1-4].图的书式嵌入首先由Atneosen[5]提出，Kainen[6]正式给出定义.Ollmann[7]首先提出书页数问题.把完全图K4的所有顶点按一定的顺序放到虚线上也就是书脊上，得到完全图K4的一个书式嵌入，如图1所示.

图1 完全图K4的书式嵌入

研究交叉数的主要目的之一是图的交叉数在超大规模集成电路设计中的应用[8-10].一个图的画法满足下列条件：(1)相邻的2条边不交叉；(2)2条边相交叉不多于一次；(3)2条边不相切；(4)没有3条边交于同一个顶点.在图G的所有画法中交叉点数最少的画法所含的交叉点的数目称为图G的交叉数，记为cr(G).把图G嵌入一个2-页书，在这个2页书上的所有画法中，使得交叉点数最少的画法所含的交叉点的数目称为图G的2-页交叉数，记为cr2(G).Garey等[11]指出计算简单图的交叉数是NP-困难的.由于这两个问题都是NP-困难的，所以不太容易得到通用的简易算法.

图2 Fn的一个画法

snark图是源自3-边着色猜想而构造的图.若图是2边连通的3-正则图且不可3-边着色，同时围长至少为5，也无非平凡3-边割集，则称为snark图.广义Petersen图是最小的snark图.1975年以来，更多的snark图被发现，人们对snark图进行了很多研究，特别是Flower snark，Goldberg snark，Blanuša snark图.给出Flower snark图的定义：Gn是一个简单的非平凡的连通的3-正则图，点集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}，点的标号对n取模，Hn可以由Gn通过用边yn-1z0，zn-1y0替换yn-1y0，zn-1z0得到.如果n为奇数且n≥5，Hn被称为Flower snark图，其他的图被称为Flower snark图的相关图，把这些图统一用Fn来表示，见图2.显然，k0k1…kn-1k0为一个n圈，y0y1…yn-1z0z1…zn-1y0为一个2n圈，xi与yi，zi，ki(0≤i≤n-1)都有边相连.

本文将给出Flower snark图的书式嵌入页数的简单证明，以及Flower snark图的2-页交叉数结果.

2 主要结论

引理1PN(G)=1，当且仅当G为外平面图.

引理2PN(G)≤2，当且仅当G是平面Hamilton图的子图.

由引理2显然可以得到如下结论：

引理3 若G为非平面图，则PN(G)≥3.

引理4 完全二部图K3，3的书式嵌入页数PN(G)=3.

2008年，Zheng等[12]研究了Flower snark图的交叉数，由文献[12]可得到引理5：

引理5 当n≥6时，Flower snark图的交叉数cr(Fn)=n.

定理1 当n≥3时，Flower snark图的书式嵌入页数PN(Fn)=3.

图3 Flower snark图中包含了同构于K3，3的子图

证明观察Flower snark图，可发现Flower snark图中包含了同构于K3，3的子图，见图3.

由引理4可知，K3，3的书式嵌入页数PN(G)=3，所以Flower snark图的书式嵌入页数PN(Fn)≥3.

给出Flower snark图的一个书式嵌入画法：

图4 Flower snark图的一个书式嵌入画法

由Flower snark图Fn的定义，它包含了点集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}.显然，Flower snark图中包含了一个n圈k0k1…kn-1k0，一个2n圈y0y1…yn-1z0z1…zn-1y0，并且当0≤i≤n-1时xi与yi，zi，ki都有边相连.

在书脊上按照z0z1…zn-1y0y1…yn-1xn-1xn-2…x1x0k0k1…kn-1的顺序依次排列各顶点.

第一页：y0y1…yn-1z0z1…zn-1y0为一个2n圈，依次连接各顶点形成圈，不形成交叉点.k0k1…kn-1k0为一个n圈，先依次连接k0k1…kn-1，不形成交叉点，kn-1与k0的连线留到下一页.又因为xi与yi，zi，ki都有边相连，把xi与ki都相连，不产生交叉点.

第二页：把xi与zi都相连，不产生交叉点.同时kn-1与k0相连.

第三页：把xi与yi都相连，不产生交叉点.

由定义，把Flower snark图的每条边都相连了，共3页，完成Flower snark图的一个书式嵌入画法，见图4.

从给出的画法可以看出PN(Fn)≤3.

综上，当n≥3时，Flower snark图的书式嵌入页数PN(Fn)=3.

定理2 当n≥6时，Flower snark图的2-页交叉数cr2(Fn)=n.

图5 Flower snark图的一个2-页书画法

证明由引理5可知，当n≥6时，cr(Fn)=n.又因为cr2(Fn)≥cr(Fn).这样得到了当n≥6时，cr2(Fn)的下界，即cr2(Fn)≥n.

由Flower snark图Fn的定义可知它包含了一个n圈k0k1…kn-1k0，一个2n圈y0y1…yn-1z0z1…zn-1y0.并且当0≤i≤n-1时xi与yi，zi，ki都有边相连.由2-页书画法的定义可知，把一个图嵌入到这本书中，这个图的每个顶点都位于书脊上，每条边都位于同一页上.

在书脊上按照y0x0z0y1x1z1y2x2z2…yn-1xn-1zn-1kn-1kn-2…k1k0的顺序依次排列各顶点.首先，k0k1…kn-1k0为一个n圈，依次连接各点，不产生交叉点.y0y1…yn-1z0z1…zn-1y0为一个2n圈，依次连接各点，边zn-2zn-1与yn-1z0相交共产生1个交叉点.其次，xi分别与yi，zi相连，不产生交叉点.最后，xi与ki相连，当0≤i≤n-2时，每条边xiki都与yiyi+1产生一个交叉点，共n-1个交叉点.当i=n-1时，每条边xn-1kn-1不与其他边产生交叉点.综上，共产生n个交叉点.

因此得到一个Flower snark图的2-页画法，并发现共产生了n个交叉点，见图5.从而得到cr2(Fn)的一个上界：当n≥6时，cr2(Fn)≤n.

综上，当n≥6时，Flower snark图的2-页交叉数，cr2(Fn)=n.