T₁₁的不可定向亏格的计算

The Computation of the Nonorientable Genus of T₁₁

摘要: 一个图G的亏格g(G)(或不可定向亏格，也称叉冒数)是最小的整数g (或k)，使得G可以嵌入到曲面S_g (或N_k)上，且边为两两不交的简单闭曲线。借助于曲面嵌入图理论中的剪开和粘合的技巧，得到了11-圈的立方体图T₁₁的不可定向亏格。

Abstract: The genus g(G) (or nonorientable genus , is also called crosscap number) of a graph Gis the smallest number g (or k) such that Ghas an embedding in S_g (or N_k) and the edges are simple closed curves which do not intersect except at a common vertex. We obtained the nonorientable genus of the cubic graph of 11-cycle, T₁₁, using the technique of cut and identification in the theory of embedded graphs surfaces.

1. 引言

曲面S是一个无边界的、紧致的、连通的2-维流形。曲面分类定理 [1] 告诉我们：每个曲面或者同胚于 $S_g$ ，添加了g个手柄的球，或者同胚于 $N_k$ ，添加了k个叉帽的球。一个图G的亏格 $g\left(G\right)$ (或不可定向亏格 $\tilde{g}\left(G\right)$ ，也称叉帽数)是最小的整数g (或k)，使得G可以嵌入到 $S_g$ (或 $N_k$ )上，且边为两两不交的简单闭曲线。记n，e，f分别为图G的边数、点数和面数，经典的Euler公式告诉我们： $n-e+f=2-\gamma$ ，其中 $\gamma$ 为图G的Euler亏格。

曲面S上的一个嵌入图是将一个图嵌入到曲面S上，使得对图中所有的边，除去一个公共点，都是边不交的多边形的边。一个三角剖分是指一个嵌入图的每个面都是一个三角形。一个平面的近三角剖分图是指嵌入到平面上的一个图，除了可能的一个外面，都以一个三角形为边界。外面以一个圈为边界。

在这里，我们计算了由11-圈添加距离不大于3的所有两个点之间的边得到的图，即T₁₁的亏格。C. Thomassen [2] 已经注意到亏格的计算是NP问题中的一类，所以是非常困难的一件事。在这里我们借助于嵌入的技巧，计算出了T₁₁的不可定向亏格为3。

本文研究的图都是简单连通无向图，所有的专业术语均可参考文献 [3] 。

2. 主要定理及证明

M. O. Albertson和J. P. Hutchinson [4] 在研究图的独立数和点数的比值时发现了一个6-正则，6-色临界的可以嵌入到环面上的图，并把它命名为J，后来知道到这个图同构于 $C_{11}^3$ ，也就是11-圈的立方图。 C. Thomassen [5] 称这个图为T₁₁，在这里，我们采用C. Thomassen的命名。图1给出了T₁₁在环面S₁上的一种嵌入方法。我们将证明T₁₁不能嵌入在克莱因瓶N₂上，也就是说，T₁₁的不可定亏格为3。

Figure 1. A method of embedding T₁₁ on a torus S₁

图1. T₁₁在环面S₁上的一种嵌入方法

若G是简单的平面图，由Euler公式 $n-e+f=2$ ，可以推出 $e\le 3n-6$ ，等号成立当且仅当G是一个平面三角剖分图。由于T₁₁有11个点，33条边，所以它不能嵌入到平面上。图1给出了它在环面上的一种嵌入方法，所以下述的命题成立。

命题1.1 $g\left(T_{11}\right)=1$ 。

下面的一个简单的观察表明了一个任意给定的图的亏格与不可定向亏格之间的关系。如果知道图的可定向亏格，在计算图的不可定向亏格的过程中，借助于这个公式，我们可以得到图的不可定向亏格的一个上界。

命题1.2 对于不是树的每个连通图G，有 $\tilde{g}\left(G\right)\le 2g\left(G\right)+1$ 。

证明令 $\text{Π}$ 是有正的符号的G的一个最小亏格嵌入。选择属于G中的一个圈的任意一条边 $e_0\in E\left(G\right)$ ，并改变它的符号。这决定了G的一个不可定向嵌入Π'。不包含 $e_0$ 的Π-面迹同时也是Π'-面迹。记 $n,e,f$ 和 $n^{\prime },e^{\prime },f^{\prime }$ ，分别为嵌入Π和Π'的点数、边数和面迹数。改变这条边的符号以后，嵌入Π'的点数和边数不会发生变化，面迹数最多增加1，所以 $f^{\prime }\le f+1$ 。 $\tilde{g}\left(G\right)=2-\left(n^{\prime }-e^{\prime }+f^{\prime }\right)\le 2-\left(n-e+f-1\right)=2-\left(2-2g-1\right)=2g+1$ ，即 $\tilde{g}\left(G\right)\le 2g\left(G\right)+1$ 。

设边 $e=uv$ ，它在 ${\pi }_u$ 和 ${\pi }_v$ 中的旋转方向可能一致，也可能不一致。若e旋转方向一致，则e对应于1，反之e对应于−1。由面迹的定义，我们可以得到下面的命题。

命题1.3 如果W是一个Π-面迹，那么W以负号出现的边的数目是偶数。

称Π-嵌入图G的一个圈C是Π-单侧圈，如果它有奇数条有负号的边。否则C是Π-双侧圈。令 $C=v_0{e}_1{v}_1{e}_2\cdots v_{l-1}{e}_l{v}_l$ 是一个Π-嵌入图G的Π-双侧圈。假设 $\text{Π}$ 的符号在C上是正的。我们定义左子图和右子图如下：对 $i=1,\cdots ,l$ ，如果 $e_{i+1}={\pi }_{v_i}^{k_i}\left(e_i\right)$ ，那么称所有的边 ${\pi }_{v_i}\left(e_i\right),{\pi }_{v_i}^2\left(e_i\right),\cdots ,{\pi }_{v_i}^{k_i-1}\left(e_i\right)$ 在C的左侧。C的左子图，记作 $G_l\left(C,\Pi \right)$ (或仅记作 $G_l\left(C\right)$ )，定义为所有包含C的左侧的一条边的C-桥的并。右子图 $G_r\left(C,\Pi \right)$ (或仅记作 $G_r\left(C\right)$ )可以类似地定义。称 $\text{Π}$ -嵌入图G的一个圈C是 $\text{Π}$ h> -可分离的(或曲面可分离的)，如果C是Π-双侧的且 $G_l\left(C\right)$ 和 $G_r\left(C\right)$ 没有公共边。

现在假定C是Π-嵌入图G的一个曲面不可分离圈。如果C是Π-双侧圈，令 $\bar{G}$ 是将图G的一个圈C换成C的两个拷贝，使得C的左侧的所有的边和C的一个拷贝关联，C的右侧的所有的边和C的另一个拷贝相关联。我们说 $\bar{G}$ 是由G沿着C剪开(或Π-剪开)得到的图。嵌入Π定义了 $\bar{G}$ 的一个嵌入(我们仍记作Π)。

类似地，我们可以定义沿着一个Π-单侧圈剪开。如果 $C=v_0{e}_1{v}_1{e}_2\cdots e_k{v}_0$ 是这样一个圈，我们首先和双侧圈的情形一样定义C的每个点处的左侧的边(和右侧的边)：如果需要的话，我们可以取一个等价嵌入，我们可以假定Π的符号 $\lambda$ 满足：对 $1\le i<k$ ，有 $\lambda \left(e_i\right)=1$ ，和 $\lambda \left(e_k\right)=-1$ 。然后我们使用C上的连续边对 $e_i,e_{i+1}\left(i=1,\cdots ,k-1\right)$ 来定义与 $v_i$ 和 $e_i$ 与 $e_{i+1}$ 相关联的C的左侧的边。然后将G中的C换成圈 $\bar{C}=v_0{e}_1{v}_1\cdots e_k{\bar{v}}_0{\bar{e}}_1{\bar{v}}_1\cdots {\bar{e}}_k{v}_0$ 来构造图 $\bar{G}$ ，这个圈的长度是C的两倍。C的左侧的边与 $v_0,v_1,\cdots ,v_{k-1}$ 关联，C的右侧的边与 ${\bar{v}}_0,{\bar{v}}_1,\cdots ,{\bar{v}}_{k-1}$ 相关联。我们扩展 $\lambda$ ，置 $\lambda \left({\bar{e}}_1\right)=\cdots =\lambda \left({\bar{e}}_{k-1}\right)=1$ 和 $\lambda \left({\bar{e}}_k\right)=-1$ ，因此得到 $\bar{G}$ 的一个嵌入 $\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}$ 。

命题1.4 假定C是一个Π-嵌入图G的一个Π-曲面不可分离圈。令 $\bar{G}$ 是沿着C剪开得到的图， $\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}$ 为它的嵌入。那么所有的 $\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}$ -面迹都是G中的Π'-面迹，其中C的边被它在 $\bar{G}$ 中的边所替代。如果C是Π-双侧圈，那么 $\text{eg}\left(\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}\right)=\text{eg}\left(\text{Π}\right)-2$ ，且C的两个拷贝是新的 $\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}$ -面圈。如果C是 $\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}$ -单侧圈，那么 $\text{eg}\left(\text{<mover accent="true"> Π <mo> ¯ </mo> </mover>}\right)=\text{eg}\left(\text{Π}\right)-1$ ，且 $\bar{C}$ 是 $\bar{G}$ 中的一个面圈。

命题1.5 T₁₁是局部Hamilton的，也就是说，对T₁₁的每个点，由v的邻点诱导的G的子图 $N\left(v,G\right)$ 有一个Hamilton圈。

定理1.6 $\tilde{g}\left(T_{11}\right)=3$ 。

证明由命题1.1和命题1.2知， $\tilde{g}\left(T_{11}\right)=3$ 。所以仅需证明T₁₁不能嵌入到克莱因瓶N₂上。

假设 $\Pi =\left(\pi ,\lambda \right)$ 是T₁₁在克莱因瓶N₂上的一个嵌入。选择一个点 $x\in T_{11}$ 。我们可以假定对x的每个邻点 $x^{\prime }$ ，有 $\lambda \left(x{x}^{\prime }\right)=1$ 。记 $n,e,f$ 分别为T₁₁为在克莱因瓶N₂上的嵌入的点数、边数和面数，由克菜因瓶N₂上的Enler公式 $n-e+f=0$ ，知道这个嵌入有22条面迹，且所有的面迹均为三角形。这意味着有一个与包含x的六个面三角形边不交的3-面圈 $T=wyz$ 。由命题1.3知，T中有一条边有正的符号，不妨说 $\lambda \left(yz\right)=1$ 。从而3-圆 $C=xyz$ 是Π-双侧的非面圈。假设C是面圈，那么C的内部和外部均有节点，从而 $T_{11}-C$ 有另个分支，这是不可能的。进一步，还有C是诱导的不可分离圈。由命题1.4知，沿着C剪开，可以得到一个图 $G^{\prime }$ 在Euler亏格为0的曲面，即球面，上的一个嵌入Π'。

记 $T_1$ 和 $T_2$ 为C在 $G^{\prime }$ 中的拷贝，对 $i=1,2$ ，令 $x_i,y_i,z_i$ 分别是 $x,y,z$ 在 $T_i$ 中的拷贝。令 $G^{\prime }=G-T_1-T_2$ 是由G删除 $T_1$ 和 $T_2$ 中的点及其关联的边得到的图，则 $G^{\prime }$ 中与 $x,y,z$ 的距离不大于3的点，或者与 $x_1,y_1,z_1$ 相邻，或者与 $x_2,y_2,z_2$ 相邻。因此 $T_1$ 和 $T_2$ 分别被嵌入到 $G^{\prime }$ 的两个不同的面 $F_1$ 和 $F_2$ 中。

由于 $G^{\prime }$ 是平面三角剖分图，所以 $F_i$ 包含 $T_i$ 以及相应的6条边。进一步， $T_1$ 中的每一个点与 $F_1$ 的某个点相邻 $T_2$ 中的每一个点与 $F_2$ 的某个点相邻。因此我们可以得到 $G^{\prime }$ 在平面上的一种嵌入方式，如图2所示。

Figure 2. Plane triangulation embedding of $G\text{'}$

图2. $G\text{'}$ 的平面三角剖分嵌入

现在粘合 $T_1$ 和 $T_2$ ，使得相应的图为T₁₁。因为 $T_1$ 和 $T_2$ 中的点的度数分别为3，4，5，所以仅有一种粘合的方式，粘合产生T₁₁在环面上的嵌入。这与克莱因瓶N₂的不可定向性相矛盾。

确定图的最小亏格问题是NP-困难的。目前已被解决的图类多为完全图、完全二部图等特定图类。本文借助于曲面嵌入图理论中的剪开和粘合的技巧，得到了11-圈的立方体图T₁₁的不可定向亏格。经典的公式在组合计数中得到的结果往往比较粗糙，剪开和粘合的技巧是从图的结构出发，可以得到较为精确的结果。图的亏格问题还与理论计算机科学的研究有密切的关系，图的结构分析将在研究中起着重要的作用。

基金项目

国家自然科学基金项目(11171114)。

参考文献

NOTES

^*第一作者。

^#通讯作者。