浙江师范大学数学科学学院，浙江 金华

收稿日期：2023年2月23日；录用日期：2023年3月24日；发布日期：2023年3月31日

摘要

将一个简单图中所有顶点替换为有向圆周(称为结点)，将所有边替换为圆柱面(称为管子)，即得到一个缩影为这个简单图的图式流形。一个图式流形可对应一个伴随矩阵，若管子两端的圆周是同向的则为正管，矩阵对应元素为1；若是反向则为负管，对应元素为−1，若两结点间无管相连，则对应元素为0。利用伴随矩阵的特征多项式，可计算图式流形同胚类的下界。本文对于缩影为正多面体一维骨架的图式流形，分别计算出各情形的伴随矩阵特征多项式，并对其进行对比、去重，得到其同胚类下界。其中，结合正十二面体与正二十面体情形的伴随矩阵的稀疏性，利用Householder变换，先对伴随矩阵进行预处理，将其化为对称三对角矩阵，再用一种简便的递推算法编程计算其特征多项式，得到求同胚类下界的第二种方法，并计算出五种正多面体对应情形的同胚类下界分别为3个、6个、14个、46个和4184个。

关键词

图式流形，伴随矩阵，同胚分类，正多面体，正交变换

Lower Bounds of Homeomorphic Classifications of Graphlike Manifolds Epitomized by the One-Dimensional Skeleton of Regular Polyhedrons

Ziyun Luo

School of Mathematical Science, Zhejiang Normal University, Jinhua Zhejiang

Received: Feb. 23^rd, 2023; accepted: Mar. 24^th, 2023; published: Mar. 31^st, 2023

ABSTRACT

By replacing all vertices in a simple graph with directed circles (called nodes) and all edges with cylinders (called tubes), you get a graphlike manifold epitomized by this simple graph. If the circles at both ends of the tube are in the same direction, it is called apositive tube; otherwise it is called a negative tube, corresponding to the matrix elementsbeing 1 or −1 respectively. If two nodes are not connected, the corresponding matrixelement is 0. Therefore, a graphlike manifold corresponds to a matrix, which is called the associated matrix of the graphlike manifold. The lower bound of the homeomorphic class of graphlike manifolds can be calculated by the characteristic polynomial of the associated matrix. In this paper, the homeomorphic classifications of graphlike manifolds epitomized by the one-dimensional skeleton of regular polyhedrons are presented by using the properties of the associated matrices of graphlike manifolds. For the cases of regular dodecahedron and regular icosahedron, based on the sparseness of the associated matrices, two algorithms for calculating the lower bounds of homeomorphic classifications are given by using the orthogonal transformation of the associated matrices. The results are that the lower bounds of the homeomorphic classes for the cases of five regular polyhedrons are 3, 6, 14, 46 and 4184, respectively.

Keywords:Graphlike Manifolds, Associated Matrices, Homeomorphic Classification, Regular Polyhedron, Orthogonal Mapping

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图式流形的概念由刘亚星、李起升与1994年在文献 [1] 中首次提出。对于一个简单图G，将图G中的所有顶点替换为有向圆周(称其为结点)，同时将图G中的所有边替换为圆柱面(称其为管子)，则得到以图G为缩影的图式流形。由于结点与管子之间的连接方式不同，得到的G图式流形也可能不同。此前有不少学者对具有特殊缩影的图式流形同胚分类问题进行了研究。

1994年，刘亚星、李起升于文献 [1] 中首次提出了扭转变换，即扭转结点圆周的方向，使得与这个结点相连的所有管子均反向，并利用扭转变换，求出以K₄为缩影的图式流形同胚类共有3个。1996年，郭驼英于文献 [2] 中得到以K₅为缩影的图式流形同胚类数量为7个。2009年，郭臣峰在文献 [3] 中利用扭转变换得到，缩影为三棱柱一维骨架的图式流形共有6个同胚类，而缩影为正方体一维骨架的图式流形共有7个同胚类，缩影为五棱柱一维骨架的图式流形同胚类数为12个。2010年，卢建立等人在文献 [4] 利用扭转变换得到缩影为轮图W₈和W₉的图式流形同胚类数分别为18个和30个。

1997年，陈胜敏、胡努春在文献 [5] 中引入了图式流形的伴随矩阵，将图式流形与矩阵以及特征多项式联系起来。若记 $B_n$ 为图式流形的同胚类所成之集，记 $P_n$ 为对于伴随矩阵的特征多项式所成之集，则有 $\left|B_n\right|\ge \left|P_n\right|$ ，且当 $n<7$ 时等号成立。1998年，郭驼英于文献 [6] 推广了上述结论，分别用扭转变换以及伴随矩阵的方法求出了 $n=7$ 时的同胚类数和下界，得到 $\left|B_7\right|=\left|P_7\right|=54$ 。2004年，钱有华、翁云杰等人于文献 [7] 利用图式流形伴随矩阵的特征多项式计算得到缩影为K₈，K₉的图式流形同胚类下界分别为235个和1824个。2007年，周慧清等在文献 [8] 中对上述结果进行改进，通过计算伴随矩阵的积和式进一步提高了K₈，K₉情形的同胚类下界，结果分别为242个和1997个。

1997年，宋中山、张群于文献 [9] 首次运用机器计算，编写算法程序，计算出缩影骨架具有3，4，5个顶点的所有图式流形同胚类数。1998~1999年，林诒勋等人于文献 [10] [11] 运用图论的方法解决图式流形的同胚分类问题。其中林诒勋和邓俊强在文献 [11] 中通过构造独立系，讨论了缩影为轮图W₆，W₇的图式流形分类，得到分类结果分别为8个和14个。

2001年，袁夫永在文献 [12] 中利用求数列个数的办法，推导出缩影为轮图 $W_{n+1}$ 的图式流形同胚类数公式：

其中， $\Phi \left(d\right)$ 为欧拉函数，表示满足 $r<d$ 且 $\left(r,d\right)=1$ 的自然数r的个数。

2012年，平麟等人于文献 [13] [14] 以轮图 $W_{13}$ 为例，利用Burnside引理给出了计算缩影为 $W_n$ 的同胚类上界的方法并计算出同胚类上界数，并猜想当 $n\ge 5$ 时，以轮图 $W_n$ 为缩影的图式流形同胚类数等于由Burnside引理得到的上界数。

多面体相关的研究在各个领域都有着极其广泛的应用，其中正多面体因其具有特殊的结构和性质，吸引了许多学者的目光，如文献 [15] [16] 等。

引理1.2 [17] 空间中正多面体只有五种，分别为正四面体、正六面体、正八面体、正十二面体、正二十面体。

关于引理1.2的证明，早已有许多学者给出了不同的方法，详见文献 [17] [18] [19] 。

现考虑以正多面体的一维骨架为缩影的图式流形。首先，对于缩影为正四面体一维骨架的图式流形，刘亚星、李起升在文献 [1] 中利用扭转变换得到结论：共有3个同胚类。而对于正六面体，郭臣峰在文献 [3] 中有相关讨论，他利用扭转变换得到结果：共有7个同胚类。

本文主要研究的是以正多面体的一维骨架为缩影的图式流形的同胚分类问题，首先验证正四面体与正六面体的情形，再进一步计算正八面体、正十二面体与正二十面体的同胚类型数量的下界，其中结合正十二面体与正二十面体对应的伴随矩阵的稀疏性，给出了两种计算同胚类数量下界的算法，并运用数学软件编程实现。

本文的结构安排如下：

第二章为计算同胚类下界的算法。本章分为5个小节来分别阐述缩影为正四面体、正六面体、正八面体、正十二面体以及正二十面体一维骨架的图式流形同胚类下界的计算过程。其中对于正十二面体和正二十面体的情形，利用特征多项式法以及正交变换法这两种算法来分别计算同胚类下界。

第三章为总结与展望。

2. 计算同胚类下界的算法

下面先给出图式流形的数学定义：

定义2.1 [8] 设 $G=\left(V,X\right)$ 是一个简单图，其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 为顶点集，其元素为图G的n个顶点； $X=\left\{x_1,x_2,\cdots ,x_m\right\}$ 为由m条边所构成的集合。现把V中每个顶点 $v_u\left(u=1,2,\cdots ,n\right)$ 均替换为有向圆周 $S_{v_u}^1$ ，假设两顶点 $v_i,v_j\left(i\ne j\in \left\{1,2,\cdots ,n\right\}\right)$ 间存在一条边，并将其记为 $x_k\in X$ ，则可把 $x_k$ 相应地替换为一个圆柱面 $T_{x_k}=S_{x_k}^1\times \left[0,1\right]$ 。我们将这两个顶点所对应的圆周 $S_{v_i}^1,S_{v_j}^1$ 用一个映射度为1或−1的连续映射与圆柱面的两个边界 $S_{x_k}^1\times \left\{0\right\},S_{x_k}^1\times \left\{1\right\}$ 相连接，这样可以得到一个拓扑空间M。我们将顶点所对应的圆周称为结点，将边所对应的圆柱面称为管子，同时将连接管子与结点的映射称为粘附映射，称由此构造的拓扑空间M为G图式流形，其中图G称为图式流形M的缩影。

根据定义2.1可知，若管子两端的粘附映射的映射度是同号(异号)的，则称管子为正管(负管)，对应的边称为正边(负边)。易知正管两端的结点圆周是同向的，而负管两端的结点圆周是反向的。

设M为满足定义2.1的一个图式流形，其缩影 $G=\left(V,X\right)$ 是有n个顶点m条边的简单图，其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ ， $X=\left\{x_1,x_2,\cdots ,x_m\right\}$ 。

定义2.2 [7] 称n阶矩阵 $A={\left(a_{ij}\right)}_{n\times n}$ 为图式流形M的伴随矩阵，若满足

$a_{ij}=\{\begin{array}{l}1v_i{v}_j以正管相连\\ -1v_i{v}_j以负管相连\\ 0v_i{v}_j无管相连\end{array}$

根据定义2.2可知，由定义2.1所定义的图式流形的伴随矩阵均为主对角线元素为0、其他元素为±1或0的对称方阵。

定义2.3 [20] 称一个变换为图式流形的扭转变换，如果这个变换将图式流形中某个结点圆周改变方向，即改变与这个结点连接的所有边的符号。

由定义2.3我们可以得到，若对图式流形M中的一个顶点 $v_i$ 进行扭转变换，则相当于将其伴随矩阵的第i行与第i列同时乘以−1。

定义2.4 [8] 称一个变换为图式流形的顶点变换，如果这个变换将其伴随矩阵的第i行与第j行对换，同时将第i列与第j列对换。

定义2.5 [8] 扭转变换和顶点变换统称为图式流形的容许变换。

由文献 [8] 可知，图式流形的容许变换是同胚的，并且同胚的图式流形伴随矩阵的特征多项式也是相同的。因此一个图式流形M经过有限次的容许变换后得到的新的图式流形M'与M同胚，而它们伴随矩阵的特征多项式也相同。所以通过计算对比图式流形伴随矩阵的特征多项式，就可以得到图式流形的同胚类数量的下界。

2.1. 正四面体

首先讨论缩影为正四面体的一维骨架(如图1)的情形。根据图1，我们可以得到一个伴随矩阵的形式为

图1. 正四面体的一维骨架

$T=\left[\begin{array}{cccc}0& \ast & \ast & \ast \\ & 0& \ast & \ast \\ & & 0& \ast \\ & & & 0\end{array}\right],$

并且满足 $T^{\prime }=T$ ，其中“ $\ast$ ”处取值为1或−1。则共有2⁶种不同的伴随矩阵。

接着，利用ntom_tetra函数，依次将自然数k (其中k的取值为 $0,\cdots ,2^6-1$ )转化为上述形式的伴随矩阵T，并分别计算出它们的特征多项式。

最后对得到的特征多项式进行去重，即可得到同胚类数量的下界。

下面给出ntom_tetra函数的算法 [7] ：

首先将自然数k化为二进制表示。再对二进制数k从右往左依次判断每一位数，若为1，则伴随矩阵T上三角部分的对应位置元素赋值为1；若为0，则对应元素赋值为−1。最后利用对称性给伴随矩阵T下三角部分赋值，即可得自然数k所对应的伴随矩阵T。例如输入ntom_tetra(2)，则可输出矩阵

$\left[\begin{array}{cccc}0& -1& 1& -1\\ -1& 0& -1& -1\\ 1& -1& 0& -1\\ -1& -1& -1& 0\end{array}\right].$

运用上述方法，运行得到结果至少有3个同胚类，它们的特征多项式系数向量如下：

1) $\left(1,0,-6,8,-3\right)$ ；

2) $\left(1,0,-6,0,5\right)$ ；

3) $\left(1,0,-6,8,3\right)$ 。

这与文献 [1] 中利用扭转变换讨论得到的结果是一致的。

2.2. 正六面体

正六面体的情形，大致思路与正四面体的情形类似。如图2为正六面体的一维骨架，则可得到正六面体情形对应的一个伴随矩阵形式

$C=\left[\begin{array}{cccccccc}0& \ast & 0& \ast & \ast & 0& 0& 0\\ & 0& *& 0& 0& \ast & 0& 0\\ & & 0& \ast & 0& 0& \ast & 0\\ & & & 0& 0& 0& 0& \ast \\ & & & & 0& \ast & 0& \ast \\ & & & & & 0& \ast & 0\\ & & & & & & 0& \ast \\ & & & & & & & 0\end{array}\right],$

并且满足 $C^{\prime }=C$ ，其中“ $\ast$ ”处取值为1或−1。则共有2¹²种不同的伴随矩阵。为了编程方便，可利用顶点变换将伴随矩阵C化为

$\tilde{C}=\left[\begin{array}{cc}O& B\\ B^{\prime }& O\end{array}\right],$

其中

$B=\left[\begin{array}{cccc}0& \ast & \ast & \ast \\ \ast & 0& \ast & \ast \\ \ast & \ast & 0& \ast \\ \ast & \ast & \ast & 0\end{array}\right],$

且“ $\ast$ ”处取值为1或−1。

图2. 正六面体的一维骨架

然后利用ntom_cube函数，依次将 $k=0,1,\cdots ,2^{12}-1$ 转化为对应的伴随矩阵 $\tilde{C}$ 。

接下来对每个 $\tilde{C}$ 分别计算特征多项式，最后对比去掉重复的，即可得到结果：缩影为正六面体一维骨架的图式流形同胚类数量下界为6个，对应的特征多项式系数向量分别为：

1) $\left(1,0,-12,0,30,0,-28,0,9\right)$ ；

2) $\left(1,0,-12,0,38,0,-28,0,1\right)$ ；

3) $\left(1,0,-12,0,46,0,-60,0,25\right)$ ；

4) $\left(1,0,-12,0,46,0,-60,0,9\right)$ ；

5) $\left(1,0,-12,0,38,0,-12,0,1\right)$ ；

6) $\left(1,0,-12,0,54,0,-108,0,81\right)$ 。

所得结果与文献 [3] 基本吻合。

2.3. 正八面体

正八面体的一维骨架如图3所示，由此可得正八面体对应的一种伴随矩阵的形式

$H=\left[\begin{array}{cccccc}0& \ast & \ast & \ast & \ast & 0\\ & 0& \ast & 0& \ast & \ast \\ & & 0& \ast & 0& \ast \\ & & & 0& \ast & \ast \\ & & & & 0& \ast \\ & & & & & 0\end{array}\right],$

利用顶点变换，可以将H化为一个排布规律的形式：

$\tilde{H}=\left[\begin{array}{cccccc}0& \ast & \ast & \ast & \ast & 0\\ & 0& \ast & \ast & 0& \ast \\ & & 0& 0& \ast & \ast \\ & & & 0& \ast & \ast \\ & & & & 0& \ast \\ & & & & & 0\end{array}\right],$

且上述H与 $\tilde{H}$ 中“ $\ast$ ”处取值均为±1。则根据“ $\ast$ ”处取值不同，需计算2¹²种情况。

图3. 正八面体的一维骨架

接下来利用ntom_octa函数将 $0,1,\cdots ,2^{12}-1$ 分别输出为对应的伴随矩阵 $\tilde{H}$ ，同时算出它们的特征多项式系数，经过对比去重后可得到结果。

经计算，得到缩影为正八面体一维骨架的图式流形同胚类下界为14个，它们分别对应了14个特征多项式系数向量如下：

1) $\left(1,0,-12,16,0,0,0\right)$ ；

2) $\left(1,0,-12,8,20,-16,0\right)$ ；

3) $\left(1,0,-12,8,32,-32,0\right)$ ；

4) $\left(1,0,-12,0,16,0,0\right)$ ；

5) $\left(1,0,-12,0,36,0,-32\right)$ ；

6) $\left(1,0,-12,0,32,0,-16\right)$ ；

7) $\left(1,0,-12,8,36,-48,16\right)$ ；

8) $\left(1,0,-12,0,36,0,-16\right)$ ；

9) $\left(1,0,-12,0,32,0,0\right)$ ；

10) $\left(1,0,-12,-8,20,16,0\right)$ ；

11) $\left(1,0,-12,-8,32,32,0\right)$ ；

12) $\left(1,0,-12,0,48,0,-64\right)$ ；

13) $\left(1,0,-12,-8,36,48,16\right)$ ；

14) $\left(1,0,-12,-16,0,0,0\right)$ 。

2.4. 正十二面体

图4为正十二面体的一维骨架图，由图4可以得到以正十二面体一维骨架为缩影的图式流形的一个伴随矩阵的形式

$D=\left[\begin{array}{cccccccccccccccccccc}0& \ast & & & \ast & & & & & & & & & \ast & & & & & & \\ \ast & 0& \ast & & & & & & & & & \ast & & & & & & & & \\ & \ast & 0& \ast & & & & & & \ast & & & & & & & & & & \\ & & \ast & 0& \ast & & & \ast & & & & & & & & & & & & \\ \ast & & & \ast & 0& \ast & & & & & & & & & & & & & & \\ & & & & \ast & 0& \ast & & & & & & & & \ast & & & & & \\ & & & & & \ast & 0& \ast & & & & & & & & & & & & \ast \\ & & & \ast & & & \ast & 0& \ast & & & & & & & & & & & \\ & & & & & & & \ast & 0& \ast & & & & & & & & & \ast & \\ & & \ast & & & & & & \ast & 0& \ast & & & & & & & & & \\ & & & & & & & & & \ast & 0& \ast & & & & & & \ast & & \\ & \ast & & & & & & & & & \ast & 0& \ast & & & & & & & \\ & & & & & & & & & & & \ast & 0& \ast & & & \ast & & & \\ \ast & & & & & & & & & & & & \ast & 0& \ast & & & & & \\ & & & & & \ast & & & & & & & & \ast & 0& \ast & & & & \\ & & & & & & & & & & & & & & \ast & 0& \ast & & & \ast \\ & & & & & & & & & & & & \ast & & & \ast & 0& \ast & & \\ & & & & & & & & & & \ast & & & & & & \ast & 0& \ast & \\ & & & & & & & & \ast & & & & & & & & & \ast & 0& \ast \\ & & & & & & \ast & & & & & & & & & \ast & & & \ast & 0\end{array}\right],$

其中“ $\ast$ ”处取值为±1，其余处均为0。易知矩阵D是一个对称矩阵，并且D的每行每列有且仅3个非零元，这是因为正十二面体的每个顶点有且仅有3条边与之相连，因此共有2³⁰种情况。

利用矩阵的稀疏性，提出了两种算法。

图4. 正十二面体的一维骨架

2.4.1. 特征多项式法

特征多项式法与前文算法类似，利用ntom_dodeca函数，将 $0,1,\cdots ,2^{30}-1$ 分别输出为对应的伴随矩阵D，并对它们的特征多项式系数去重，可以得到结果至少有46个同胚类。

计算得到的46个特征多项式中，其中前10个系数向量如下：

1) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0024,-0.2540,-0.0480,1.0095,0.3760,-2.3502,$

$-1.4400,2.8905,2.7000,-1.1400,-2.0000,-0.6000,0,0,0,0)$ ；

2) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0016,-0.2540,-0.0320,1.0127,0.2496,-2.4030,$

$-0.9568,3.2217,1.8544,-2.0600,-1.6480,0.3008,0.4800,0.0960,0,0)$ ；

3) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0016,-0.2540,-0.0320,1.0135,0.2480,-2.4094,$

$-0.9456,3.2361,1.8368,-2.0632,-1.6528,0.2872,0.4864,0.0832,-0.0192,-0.0048)$ ；

4) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0135,0.1248,-2.4222,$

$-0.4784,3.3705,0.9336,-2.5368,-0.8816,0.9080,0.3744,-0.1088,-0.0576,-0.0048)$ ；

5) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0143,0.1248,-2.4302,$

$-0.4816,3.3897,0.9624,-2.5128,-0.9424,0.7904,0.3648,-0.0448,-0.0256,0)$ ；

6) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0151,0.1248,-2.4430,$

$-0.4816,3.4649,0.9656,-2.7080,-0.9744,1.0104,0.4384,-0.1280,-0.0704,-0.0048)$ ；

7) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0,-0.2540,0,1.0135,0,-2.4270,0,3.4265,0,-2.7560,$

$0,1.2360,0,-0.2880,0,0.0272)$ ；

8) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0151,0.1248,-2.4414,$

$-0.4848,3.4489,0.9912,-2.6488,-1.0288,0.9016,0.4576,-0.0512,-0.0448,-0.0048)$ ；

9) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0159,0.1232,-2.4526,$

$-0.4608,3.5033,0.8744,-2.7752,-0.8032,1.0688,0.3072,-0.1536,-0.0384,0)$ ；

10) ${10}^4\times (0.0001,0,-0.0030,0,0.0375,0.0008,-0.2540,-0.0160,1.0159,0.1232,-2.4510,$

$-0.4640,3.4873,0.9000,-2.7224,-0.8640,1.0048,0.3584,-0.1344,-0.0512,0)$ 。

2.4.2. 正交变换法

正交变换法结合矩阵D的稀疏性，可利用Householder变换先将其化为三对角形式，再计算它的特征多项式。下面给出Householder变换的定义。

定义2.6 [21] 称n阶矩阵H为Householder变换，如果满足

$H=I-2u{u}^{\text{T}},$

其中 $u\in {ℝ}^n$ 满足 ${\Vert u\Vert }_2=1$ ，称为Householder向量。

下面的引理给出了Householder矩阵的性质。

引理2.7 [22] 设H为满足定义2.6的Householder矩阵，则

1) 对称性： $H^{\text{T}}=H$ ，

2) 正交性： $H^{\text{T}}H=I$ ，

3) 设 $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}\in {ℝ}^n\left(n>1\right)$ 为任意的非零向量，则存在 $u\in {ℝ}^n$ 满足 ${\Vert u\Vert }_2=1$ ，使得H满足

$Hx=\alpha e_1,$

其中 $\alpha =\pm {\Vert x\Vert }_2$ 。

证明 1) 与2) 利用H的定义容易验证。

3) 可取

$u=\frac{x-\alpha e_1}{{\Vert x-\alpha e_1\Vert }_2},$

则

$\begin{array}{c}Hx=\left(I-2u{u}^{\text{T}}\right)x=x-2u{u}^{\text{T}}x=x-2\left(u^{\text{T}}x\right)u\\ =x-2\frac{{\left(x-\alpha e_1\right)}^{\text{T}}x}{{\Vert x-\alpha e_1\Vert }_2^2}\left(x-\alpha e_1\right)\\ =x-\frac{2{\Vert x\Vert }_2^2-2\alpha e_1^{\text{T}}x}{{\Vert x\Vert }_2^2-2\alpha e_1^{\text{T}}x+{\alpha }^2}\left(x-\alpha e_1\right)\\ =x-\frac{2{\alpha }^2-2\alpha e_1^{\text{T}}x}{{\alpha }^2-2\alpha e_1^{\text{T}}x+{\alpha }^2}\left(x-\alpha e_1\right)\\ =x-\left(x-\alpha e_1\right)=\alpha e_1.\end{array}$

证毕。

由引理2.7可知，利用Householder变换，可以将一个向量中若干相邻分量化为0。根据上面过程，可以按如下步骤来构造确定H的单位向量 $u$ ：

1) 计算 $v=x\pm {\Vert x\Vert }_2{e}_1$ ；

2) 计算 $u=\frac{v}{{\Vert v\Vert }_2}$ ；

3) 计算 $H=I-2u{u}^{\text{T}}$ 。

在上述计算过程中，涉及到 ${\Vert x\Vert }_2$ 前的符号选取问题。如果选取 $v=x-{\Vert x\Vert }_2{e}_1$ ，就会出现计算 $v_1=x_1-{\Vert x\Vert }_2$ (其中 $v_1,x_1$ 分别表示 $v,x$ 的第1个分量)。当 $x_1>0$ 时，按上式计算 $v_1$ 可能会导致有效数字的丢失，此时可改用如下的计算方式：

$v_1=x_1-{\Vert x\Vert }_2=\frac{x_1^2-{\Vert x\Vert }_2^2}{x_1+{\Vert x\Vert }_2}=\frac{-\left(x_2^2+\cdots +x_n^2\right)}{x_1+{\Vert x\Vert }_2},$

这样就可避免两个相近数相减的情形。

因此定义2.6可改进为

$H=I-2u{u}^{\text{T}}=I-\frac{2}{v^{\text{T}}v}v{v}^{\text{T}}=I-\beta v{v}^{\text{T}},$

其中 $\beta =\frac{2}{v^{\text{T}}v}$ 。

另外，如果x的某分量过大，其平方运算可能会出现上溢的现象。为避免计算溢出，可以用 $x/{\Vert x\Vert }_{\infty }$ 代替x来构造向量v，其中 ${\Vert x\Vert }_{\infty }={\max }_{i\le i\le n}\left|x_i\right|$ 。

根据上述计算过程，可以实现实列向量的Householder变换。具体Matlab程序如下：

算法2.1 [22] 函数mhouse(x)

function [v,beta]=mhouse(x)

n=length(x);

eta=norm(x,inf ); x=x/eta;

sigma=x(2:n)’*x(2:n);

v=[1;x(2:n)];

if sigma==0

if x(1)>=0 beta=0;

else beta=2;

end

else

alpha=(x(1)^2+sigma)^0.5;

if x(1)<=0

v(1)=x(1)-alpha;

else

v(1)=-sigma/(x(1)+alpha);

end

beta=2*v(1)^2/(sigma+v(1)^2);

v=v/v(1);

end

进一步，可利用上述Householder变换，将一个对称矩阵化为对称三对角形式，算法步骤如下 [22] ：

设 $A=\left(a_{ij}\right)$ 为n阶实对称方阵。记 $A_1=A=\left(a_{ij}^{\left(1\right)}\right)$ ，取 $x={\left(0,a_{21}^{\left(1\right)},\cdots ,a_{n1}^{\left(1\right)}\right)}^{\text{T}}$ ，再记 $a_1=\Vert x\Vert$ 。则由引理2.7，可构造Householder矩阵

$H_1=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& \ast & \cdots & \ast \\ ⋮& ⋮& \ddots & ⋮\\ 0& \ast & \cdots & \ast \end{array}\right],$

使得

$H_{1}x=a_1{e}_2.$

因此可计算得 $H_1{A}_1$ 的第一列为

$H_1\left[\begin{array}{c}{a}_{11}^{\left(1\right)}\\ a_{21}^{\left(1\right)}\\ ⋮\\ a_{n1}^{\left(1\right)}\end{array}\right]=H_{1}x+H_1\left[\begin{array}{c}{a}_{11}^{\left(1\right)}\\ 0\\ ⋮\\ 0\end{array}\right]=a_1{e}_2+\left[\begin{array}{c}{a}_{11}^{\left(1\right)}\\ 0\\ ⋮\\ 0\end{array}\right]=\left[\begin{array}{c}{a}_{11}^{\left(1\right)}\\ a_1\\ ⋮\\ 0\end{array}\right].$

因为 $A_1,H_1$ 均为对称矩阵，于是

$A_2=H_1{A}_1{H}_1=\left[\begin{array}{ccccc}{a}_{11}^{\left(1\right)}& a_1& 0& \cdots & 0\\ a_1& a_{22}^{\left(2\right)}& a_{23}^{\left(2\right)}& \cdots & a_{2n}^{\left(2\right)}\\ 0& a_{32}^{\left(2\right)}& a_{33}^{\left(2\right)}& \cdots & a_{3n}^{\left(2\right)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& a_{n2}^{\left(2\right)}& a_{n3}^{\left(2\right)}& \cdots & a_{nn}^{\left(2\right)}\end{array}\right].$

再取 $x={\left(0,0,a_{32}^{\left(2\right)},\cdots ,a_{n2}^{\left(2\right)}\right)}^{\text{T}}$ ，记 $a_2=\Vert x\Vert$ ，构造

$H_2=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 0& 1& 0& \cdots & 0\\ 0& 0& \ast & \cdots & \ast \\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& \ast & \cdots & \ast \end{array}\right],$

使得

$H_{2}x=a_2{e}_3,$

则可得

$A_3=H_2{A}_2{H}_2=\left[\begin{array}{cccccc}\ast & a_1& 0& 0& \cdots & 0\\ a_1& \ast & a_2& 0& \cdots & 0\\ 0& a_2& \ast & \ast & \cdots & \ast \\ 0& 0& \ast & \ast & \cdots & \ast \\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& \ast & \ast & \cdots & \ast \end{array}\right].$

重复上述过程 $n-2$ 次，直至对称阵 $A_1$ 化为三对角形式

$A_{n-1}=H_{n-2}\cdots H_2{H}_1{A}_1{H}_1{H}_2\cdots H_{n-2}=\left[\begin{array}{ccccc}\ast & a_1& & & \\ a_1& \ast & a_2& & \\ & a_2& \ast & \ddots & \\ & & \ddots & \ddots & a_{n-1}\\ & & & a_{n-1}& \ast \end{array}\right].$

根据上述过程可编写Matlab程序如下：

算法2.2 [22] 函数H_mhessen(A)

function A=H mhessen(A)

n=size(A,1);

for k=1:(n-2)

x=A(k+1:n,k);

[v,beta]=mhouse(x);

H=(eye(length(v))-beta*v*v’);

A(k+1:n,1:n)=H*A(k+1:n,1:n);

A(1:n,k+1:n)=A(1:n,k+1:n)*H;

end

实现了对称矩阵三对角化后，运用文献 [23] 所述的递推算法，可简便计算三对角矩阵的特征多项式。

引理2.8 [23] 设A为n阶实三对角矩阵，

$A=\left[\begin{array}{cccccc}{a}_1& c_1& & & & \\ b_1& a_2& c_2& & & \\ & b_2& a_3& c_3& & \\ & & \ddots & \ddots & \ddots & \\ & & & \ddots & \ddots & c_{n-1}\\ & & & & b_{n-1}& a_n\end{array}\right],$

其中 $a_i,b_i,c_i\in ℝ$ 。设A的特征多项式为

$f\left(\lambda \right)=\left|\lambda E-A\right|={\lambda }^n+b_{n-1}{\lambda }^{n-1}+\cdots +b_1\lambda +b_0.$

记 $A_k$ 为A的k阶顺序主子式，则 $A_k$ 的特征多项式记为

$f_k\left(\lambda \right)=\left[\lambda E-A\right)={\lambda }^n+b_{n-1}^{\left(k\right)}{\lambda }^{n-1}+\cdots +b_1^{\left(k\right)}\lambda +b_0^{\left(k\right)},$

其中 $b_i^{\left(n\right)}=b_i\left(i=1,2,\cdots ,n-1\right)$ 。则有递推关系：

$b_i^{\left(n\right)}=b_i\left(i=1,2,\cdots ,n-1\right)$

$\left(\begin{array}{c}{b}_1^{\left(2\right)}\\ b_0^{\left(2\right)}\end{array}\right)=\left(\begin{array}{cc}-a_2& 1\\ & -a_2\end{array}\right)\left(\begin{array}{c}1\\ b_0^{\left(1\right)}\end{array}\right)-b_1{c}_1\left(\begin{array}{c}0\\ 1\end{array}\right),$

$\left(\begin{array}{c}{b}_2^{\left(3\right)}\\ b_1^{\left(3\right)}\\ b_0^{\left(3\right)}\end{array}\right)=\left(\begin{array}{ccc}-a_3& 1& 0\\ & -a_3& 1\\ & & -a_3\end{array}\right)\left(\begin{array}{c}1\\ b_1^{\left(2\right)}\\ b_0^{\left(2\right)}\end{array}\right)-b_2{c}_2\left(\begin{array}{c}0\\ 1\\ b_0^{\left(1\right)}\end{array}\right),$

$⋮$

$\left(\begin{array}{c}{b}_{n-1}^{\left(n\right)}\\ b_{n-2}^{\left(n\right)}\\ ⋮\\ b_1^{\left(n\right)}\\ b_0^{\left(n\right)}\end{array}\right)=\left(\begin{array}{ccccc}-a_n& 1& & & \\ & -a_n& 1& & \\ & & \ddots & \ddots & \\ & & & \ddots & 1\\ & & & & -a_n\end{array}\right)\left(\begin{array}{c}1\\ b_{n-2}^{\left(n-1\right)}\\ ⋮\\ b_1^{\left(n-1\right)}\\ b_0^{\left(n-1\right)}\end{array}\right)-b_{n-1}{c}_{n-1}\left(\begin{array}{c}0\\ 1\\ b_{n-3}^{\left(n-2\right)}\\ ⋮\\ b_1^{\left(n-2\right)}\\ b_0^{\left(n-2\right)}\end{array}\right).$

引理2.8的证明详见文献 [23] 。

利用引理2.8所给的算法，即可实现三对角矩阵特征多项式的简便计算，编写的Matlab程序如下：

算法3.3 函数tripoly(A)

function v=tripoly(A)

n=size(A,1);

a=diag(A,-1);

b=diag(A);

c=diag(A,1);

v=-b(1);

temp=[0;1];

for k=2:n

r=[1;v];

B=diag(diag(-b(k)*eye(k)))+diag(diag(eye(k-1)),1);

v=B*r-a(k-1)*c(k-1)*temp;

temp=[0;r];

end

v=[1;v];

综上所述，可得正交变换法的步骤：

1) 利用ntom_dodeca函数生成伴随矩阵；

2) 利用H_mhessen函数，对步骤1) 生成的伴随矩阵进行三对角化；

3) 利用tripoly函数，计算步骤2) 所得的三对角矩阵的特征多项式；

4) 对求得的所有特征多项式系数向量进行去重，即可得以正十二面体一维骨架为缩影的图式流形同胚类数量的下界。

由正交变换法可编程计算得，同胚类下界为46个，与特征多项式法运行结果一致。

2.5. 正二十面体

正二十面体的每个顶点连接了5条边(它的骨架图如图5所示)，因此所对应的伴随矩阵每行每列有且仅有5个非零元。伴随矩阵的一种代表形式如下所示：

$S=\left[\begin{array}{cccccccccccc}0& \ast & \ast & & & & & & \ast & \ast & \ast & \\ \ast & 0& \ast & \ast & & & & & & \ast & & \ast \\ \ast & \ast & 0& \ast & \ast & & & & & & \ast & \\ & \ast & \ast & 0& \ast & \ast & & & & & & \ast \\ & & \ast & \ast & 0& \ast & \ast & & & & \ast & \\ & & & \ast & \ast & 0& \ast & \ast & & & & \ast \\ & & & & \ast & \ast & 0& \ast & \ast & & \ast & \\ & & & & & \ast & \ast & 0& \ast & \ast & & \ast \\ \ast & & & & & & \ast & \ast & 0& \ast & \ast & \\ \ast & \ast & & & & & & \ast & \ast & 0& & \ast \\ \ast & & \ast & & \ast & & \ast & & \ast & & 0& \\ & \ast & & \ast & & \ast & & \ast & & \ast & & 0\end{array}\right],$

其中，S为对称矩阵，且“ $\ast$ ”处取值为±1，其余处均为0，则共有2³⁰种情况。

图5. 正二十面体的一维骨架

2.5.1. 特征多项式法

特征多项式法先运用ntom_icosa函数，将 $0,1,\cdots ,2^{30}-1$ 分别输出为对应的伴随矩阵S，并对它们的特征多项式系数去重，可以得到缩影为正二十面体一维骨架的图式流形同胚类下界为4184。

得到的4184个同胚类中，前10个对应的伴随矩阵特征多项式的系数向量如下：

1) ${10}^3\times (0.0010,0,-0.0300,0.0400,0.2550,-0.5760,-0.5800,2.6400,-1.4250,-3.2000,$

$5.2500,-3.0000,0.6250)$ ；

2) ${10}^3\times (0.0010,0,-0.0300,0.0320,0.2710,-0.4800,-0.7880,2.2080,-0.1930,-2.9760,$

$2.4500,-0.3200,-0.1750)$ ；

3) ${10}^3\times (0.0010,0,-0.0300,0.0320,0.2790,-0.5120,-0.7720,2.2720,-0.3210,-2.6240,$

$1.7300,0.3200,-0.3750)$ ；

4) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.2790,-0.3840,-0.8520,1.6800,0.1110,-1.2800,$

$0.2100,0.2160,0.0250)$ ；

5) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.2790,-0.3520,-1.0120,1.7120,1.1670,-3.1040,$

$0.3700,1.7200,-0.7750)$ ；

6) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.2790,-0.3680,-0.9160,1.6000,0.7830,-2.1920,$

$0.4020,0.4240,-0.0070)$ ；

7) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.2950,-0.3840,-1.1240,1.9680,1.2470,-3.4560,$

$0.6100,1.3360,-0.4870)$ ；

8) ${10}^3\times (0.0010,0,-0.0300,0.0320,0.2790,-0.5280,-0.6440,1.9680,-0.3530,-1.5840,$

$0.5780,0.3680,-0.0870)$ ；

9) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.2870,-0.3840,-0.9480,1.6800,0.6710,-1.8560,$

$-0.0140,0.5360,0.0330)$ ；

10) ${10}^3\times (0.0010,0,-0.0300,0.0240,0.3030,-0.4160,-1.1880,2.3840,1.0070,-4.6400,$

$2.5300,0.6000,-0.5750)$ 。

2.5.2. 正交变换法

根据2.4.2节中正交变换法的步骤，可得计算正二十面体情形的算法。经实验，两种算法运行所得结果一致，同胚类下界均为4184。

综上所述，我们可得到如下定理。

定理2.9 缩影为正四面体一维骨架的图式流形同胚类下界为3个；

缩影为正六面体一维骨架的图式流形同胚类下界为6个；

缩影为正八面体一维骨架的图式流形同胚类下界为14个；

缩影为正十二面体一维骨架的图式流形同胚类下界为46个；

缩影为正二十面体一维骨架的图式流形同胚类下界为4184个。

3. 总结与展望

本文利用特征多项式法以及正交变换法分别验证和计算了缩影为正多面体一维骨架的图式流形同胚类下界。对比两种算法，特征多项式法的整体运行时间较少，见表1。但这两种算法均只能得到同胚类下界，例如文献 [3] 中的正六面体有两种同胚类(其代表元如图6)用本文方法则无法进行区分。

表1. 两算法运行时间对比

图6. 无法区分的两种同胚类(虚线表示负边)

另外，文献 [13] 中利用Burnside引理求出了以轮图 $W_{13}$ 为缩影的图式流形同胚类上界。能否利用Burnside引理计算缩影为正多面体一维骨架的图式流形同胚类上界，还有待进一步研究。

文章引用

罗紫韵. 缩影为正多面体一维骨架的图式流形同胚分类下界
Lower Bounds of Homeomorphic Classifications of Graphlike Manifolds Epitomized by the One-Dimensional Skeleton of Regular Polyhedrons[J]. 理论数学, 2023, 13(03): 716-731. https://doi.org/10.12677/PM.2023.133076

参考文献