两类互连网络的谱特征

Spectral Characteristics of Two Classes Interconnection Networks

摘要: 图的特征值集及其多重性称为谱，它可以用来获得图的各种拓扑性质，如连通性、韧性等。师海忠利用图的笛卡尔乘积方法构建了两类新的笛卡尔乘积互连网络$C_n\times Q_m$ 和$P_n\times Q_m$ 。本文分析研究了此两类互连网络的拓扑结构，得到了两类互连网络的邻接矩阵和拉普拉斯矩阵的特征值及其多重性，刻画了两类互连网络的谱特征，从而增加了已知谱图的类。

Abstract: The eigenvalues and its multiplicity of a graph are called spectrum, which can be used to obtain various topological properties of the graph, such as connectivity, toughness, etc. Shi Haizhong constructed new Cartesian product interconnection networks $C_n\times Q_m$ and $P_n\times Q_m$ using the Cartesian product method of graphs. This article analyzes and studies the topological structures of two types of interconnected networks, obtains the eigenvalues and multiplicities of the adjacency matrix and Laplace matrix of the two types of interconnected networks, characterizes the spectral characteristics of the two types of interconnected networks, so as to increase the classes of the graph with known spectra.

1. 引言

关于图的网络分析及其应用的研究是当前图论研究中的一个热点问题。图的笛卡尔乘积方法是设计互连网络的一类重要方法[1]，是网络设计的一种核心手段。基于笛卡尔乘积互连网络的谱对于研究图论之所以重要，主要在于可以用其计算图的诸多不变量，如特征值及其重数等关键参数。此外，此类方法在交通网络优化、芯片电路设计、社交网络分析等也有实际应用背景。在文献[2]-[7]中，对于一些著名的互连网络谱的研究，如(广义)超立方体、折叠超立方体、增广超立方体的(拉普拉斯)谱等。

本文从两类互连网络$C_n\times Q_m$ 和$P_n\times Q_m$ 的拓扑结构出发，根据邻接谱、Laplace谱定义，得到了邻接矩阵并刻画邻接谱特征、拉普拉斯矩阵并刻画Laplace谱特征，并附有程序代码。

2. 基本概念

本文所讨论的图均为简单图，未定义的术语和记号见文献[8]。下面介绍互连网络、邻接谱以及Laplace谱的定义。

定义1 [1] 设环网$C_n$ 是无向图，m-立方体$Q_m$ 是m正则的连通图，则环网$C_n$ 与m-立方体$Q_m$ 的笛卡尔乘积，即互连网络$C_n\times Q_m$ 。

根据定义，互连网络$C_n\times Q_m$ 的基本性质如下：

a) $Q_m$ 有$2^m$ 个顶点和$m\cdot 2^{m-1}$ 条边；

b) $C_n\times Q_m$ 的顶点数为$n\cdot 2^m$ ，边数为$n\cdot 2^{m-1}\left(m+2\right)$ ；

c) $C_n\times Q_m$ 正则度为$m+2$ 。

定义2 [1] 设Pancake网络$P_n$ 是无向图，m-立方体$Q_m$ 是m正则的连通图，则Pancake网络$P_n$ 与m-立方体$Q_m$ 的笛卡尔乘积，即互连网络$P_n\times Q_m$ 。

根据定义，互连网络$P_n\times Q_m$ 的基本性质如下：

a) $P_n\times Q_m$ 的顶点数为$n!\cdot 2^m$ ，边数为$n\text{!}\cdot 2^m\left(n+m-1\right)$ 。

b) $P_n\times Q_m$ 正则度为$n+m-1$ 。

定义3 [2] 设G是一个简单图，$A\left(G\right)$ 是对应的邻接矩阵。由特征多项式$\left|\lambda E-A\right|=0$ 的解构成所有特征值的集合，称为图G邻接矩阵的谱，简称邻接谱，记作$Sp\left(G\right)$ 。

$Sp\left(G\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{l}{\lambda }_1\\ x_1\end{array}& \begin{array}{l}{\lambda }_2\\ x_2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{l}{\lambda }_n\\ x_n\end{array}\end{array}\right)$

其中，${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ 为特征值，$x_1,x_2,\cdots ,x_n$ 为特征值对应的重数。

用记号$\otimes$ 表示矩阵的张量积(又称为Kronecker积)，则$C_n\times Q_m$ 的邻接矩阵可表示为$A\left(C_n\times Q_m\right)=I_n\otimes A\left(Q_m\right)+A\left(C_n\right)\otimes I_{2^m}$ ，$P_n\times Q_m$ 的邻接矩阵可表示为

$A\left(P_n\times Q_m\right)=I_{n!}\otimes A\left(Q_m\right)+A\left(P_{n!}\right)\otimes I_{2^m}$ .

定义4 [2] 设L是Laplace矩阵，由$L=\Delta -A$ ，以及特征多项式$\left|\lambda E-L\right|=0$ 的解构成所有特征值的集合，称为Laplace谱，其中$\Delta$ 是与L同阶的度矩阵，A是与L同阶的邻接矩阵。

针对本文所提到的两类互连网络的度矩阵分别为

$\Delta \left(C_n\times Q_m\right)=diag\left\{\underset{n\cdot 2^m}{\underbrace{m+2,m+2,\cdots ,m+2}}\right\}$

$\Delta \left(P_n\times Q_m\right)=diag\left\{\underset{n!\cdot 2^m}{\underbrace{n+m-1,n+m-1,\cdots ,n+m-1}}\right\}$

根据文献[9]，环网$C_n$ 、Pancake网$P_n$ 和m-立方体$Q_m$ 的邻接谱如下：

Table 1. Ring network $C_n$ neighbourhood spectrum

表1. 环网$C_n$ 邻接谱

n	特征值	重数
3	2, −1	1, 2
4	3, −1	1, 3
5	4, −1	1, 4
6	5, −1	1, 5
⋯	⋯	⋯
n	n − 1, −1	1, n − 1

Table 2. Pancake network $P_n$ neighbouring spectra

表2. Pancake网$P_n$ 邻接谱

n	特征值	重数
2	1, −1	1, 1
3	$2\cos \left(\frac{\pi j}{7}\right),j=1,2,\cdots ,6$
⋯	⋯	⋯
n	$2\cos \left(\frac{\pi j}{n!+1}\right),j=1,2,\cdots ,n!$

Table 3. m-cube $Q_m$ neighbourhood spectrum

表3. m-立方体$Q_m$ 邻接谱

m	特征值	重数
1	−1, 1	1, 1
2	−2, 0, 2	1, 2, 1
3	−3, −1, 1, 3	1, 3, 3, 1
4	−4, −2, 0, 2, 4	1, 4, 6, 4, 1
⋯	⋯	⋯
m	$-m,-m+2,-m+4,-m+6,\cdots$	$1,m,\frac{m\left(m-1\right)}{2},\frac{m\left(m-1\right)\left(m-2\right)}{6},\cdots$

由以上叙述，本文需要如下两个引理。

引理1 [2] 设图G和H的特征根分别是${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ 和${\mu }_1,{\mu }_2,\cdots ,{\mu }_m$ ，则笛卡尔乘积图的特征值为${\lambda }_i+{\mu }_j$ ，其中$\left(1\le i\le n,1\le j\le m\right)$ 。

引理2 [9] 已知图的邻接矩阵为A，邻接谱$Sp\left(A\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{l}{\lambda }_1\\ {\mu }_1\end{array}& \begin{array}{l}{\lambda }_2\\ {\mu }_2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{l}{\lambda }_t\\ {\mu }_t\end{array}\end{array}\right)$ ，正则度为$\Delta$ ，则它的Laplace谱为$Sp\left(L\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}{\lambda }_1+\Delta \\ {\mu }_1\end{array}& \begin{array}{c}{\lambda }_2+\Delta \\ {\mu }_2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}{\lambda }_t+\Delta \\ {\mu }_t\end{array}\end{array}\right)$ 。

3. 互连网络$C_n\times Q_m$ 的谱特征

3.1. 互连网络$C_n\times Q_m$ 的邻接谱

设互连网络$C_n\times Q_m$ ，分别将环网$C_n$ 、m-立方体$Q_m$ 和$I_m$ 的特征值代入互连网络的邻接矩阵A中对应的分块矩阵的位置上，得到的新矩阵记为$A^{\prime }$ 。

定理3.1 已知互连网络$C_3\times Q_m$ 与其对应的新矩阵$A^{\prime }$ ，则$A^{\prime }$ 的特征值即为互连网络$C_3\times Q_m$ 邻接谱。

证明：互连网络$C_3\times Q_m$ 的邻接矩阵可表示为$A\left(C_3\times Q_m\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{l}{Q}_m\\ I_m\\ I_m\end{array}& \begin{array}{l}{I}_m\\ Q_m\\ I_m\end{array}\end{array}& \begin{array}{l}{I}_m\\ I_m\\ Q_m\end{array}\end{array}\right)$ ，其中$Q_m$ 是超立方体$Q_m$ 的邻接矩阵，$I_m$ 是与$Q_m$ 同阶的分块单位矩阵。

先将$Q_m$ 与$I_m$ 的特征值代入邻接矩阵A中，再对其求解特征值。

1. 当$Q_m$ 的特征值为$-m$ (重数为1)时，$A^{\prime }=\left(\begin{array}{ccc}-m& 1& 1\\ 1& -m& 1\\ 1& 1& -m\end{array}\right)$ 。

由特征多项式$\left|\lambda E-A\right|=0$ 得：

$\begin{array}{c}\left|\lambda E-A^{\prime }\right|=\left|\begin{array}{ccc}\lambda +m& -1& -1\\ -1& \lambda +m& -1\\ -1& -1& \lambda +m\end{array}\right|=\lambda +m-2\left|\begin{array}{ccc}1& -1& -1\\ 1& \lambda +m& -1\\ 1& -1& \lambda +m\end{array}\right|\\ =\lambda +m-2\left|\begin{array}{ccc}1& -1& -1\\ 0& \lambda +m+1& 0\\ 0& 0& \lambda +m+1\end{array}\right|=\left(\lambda +m-2\right){\left(\lambda +m+1\right)}^2=0.\end{array}$

得：${\lambda }_1=-m+2$ (重数为1)，${\lambda }_2=-m-1$ (重数为2)。

2. 当$Q_m$ 的特征值为$-m+2$ (重数为m)时，

$A^{\prime }=\left(\begin{array}{ccc}-m+2& 1& 1\\ 1& -m+2& 1\\ 1& 1& -m+2\end{array}\right)$ .

由特征多项式$\left|\lambda E-A\right|=0$ 得：

$\begin{array}{c}\left|\lambda E-A^{\prime }\right|=\left|\begin{array}{ccc}\lambda +m-2& -1& -1\\ -1& \lambda +m-2& -1\\ -1& -1& \lambda +m-2\end{array}\right|=\lambda +m-4\left|\begin{array}{ccc}1& -1& -1\\ 1& \lambda +m-2& -1\\ 1& -1& \lambda +m-2\end{array}\right|\\ =\lambda +m-4\left|\begin{array}{ccc}1& -1& -1\\ 0& \lambda +m-1& 0\\ 0& 0& \lambda +m-1\end{array}\right|=\left(\lambda +m-4\right){\left(\lambda +m-1\right)}^2=0.\end{array}$

得：${\lambda }_3=-m+4$ (重数为m)，${\lambda }_4=-m+1$ (重数为2m)。

3. 当$Q_m$ 的特征值为$-m+4$ (重数为$\frac{m\left(m-1\right)}{2}$ )时，

$A^{\prime }=\left(\begin{array}{ccc}-m+4& 1& 1\\ 1& -m+4& 1\\ 1& 1& -m+4\end{array}\right)$ .

由特征多项式$\left|\lambda E-A\right|=0$ 得：

$\begin{array}{c}\left|\lambda E-A^{\prime }\right|=\left|\begin{array}{ccc}\lambda +m-4& -1& -1\\ -1& \lambda +m-4& -1\\ -1& -1& \lambda +m-4\end{array}\right|=\lambda +m-6\left|\begin{array}{ccc}1& -1& -1\\ 1& \lambda +m-4& -1\\ 1& -1& \lambda +m-4\end{array}\right|\\ =\lambda +m-6\left|\begin{array}{ccc}1& -1& -1\\ 0& \lambda +m-3& 0\\ 0& 0& \lambda +m-3\end{array}\right|=\left(\lambda +m-6\right){\left(\lambda +m-3\right)}^2=0\end{array}$

得：${\lambda }_5=-m+6$ (重数为$\frac{m\left(m-1\right)}{2}$ )，${\lambda }_6=-m+3$ (重数为$m\left(m-1\right)$ )。

以此类推，可得：

$Sp\left(C_3\times Q_m\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cccc}\begin{array}{cc}\begin{array}{c}-m+2\\ 1\end{array}& \begin{array}{c}-m+4\\ m\end{array}\end{array}& \begin{array}{c}-m+6\\ m\left(m-1\right)/2\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}& \begin{array}{c}-m-1\\ 2\end{array}\end{array}& \begin{array}{c}-m+1\\ 2m\end{array}\end{array}& \begin{array}{c}-m+3\\ m\left(m-1\right)\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}\right)$

即定理3.1成立，得证。

通过利用上述定理，我们可以很容易得到一些维数较低的互连网络$C_3\times Q_m$ 的谱。如：

$Sp\left(C_3\times Q_4\right)=\left(\begin{array}{cccccccccc}-2& 0& 2& 4& 6& -5& -3& -1& 1& 3\\ 1& 4& 6& 4& 1& 2& 8& 12& 8& 2\end{array}\right)$ .

引理3.2 互连网络$C_n\times Q_m$ 的邻接矩阵可表示为

$A\left(C_n\times Q_m\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}{Q}_m\\ I_m\\ O_m\\ O_m\\ ⋮\\ I_m\end{array}& \begin{array}{c}{I}_m\\ Q_m\\ I_m\\ O_m\\ ⋮\\ O_m\end{array}\end{array}& \begin{array}{c}{O}_m\\ I_m\\ Q_m\\ I_m\\ ⋮\\ O_m\end{array}\end{array}& \begin{array}{c}{O}_m\\ O_m\\ I_m\\ Q_m\\ ⋮\\ O_m\end{array}\end{array}& \begin{array}{c}\cdots \\ \cdots \\ \cdots \\ \cdots \\ \ddots \\ \cdots \end{array}\end{array}& \begin{array}{c}{I}_m\\ O_m\\ O_m\\ O_m\\ ⋮\\ Q_m\end{array}\end{array}\right)$ ,

是n阶分块对角矩阵，其中$Q_m$ 是超立方体$Q_m$ 的邻接矩阵，$I_m$ 与$O_m$ 分别是与$Q_m$ 同阶的分块单位矩阵和零矩阵。

定理3.3 互连网络$C_n\times Q_m$ 的谱为

$Sp\left(C_n\times Q_m\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}n-m-1\\ 1\end{array}& \begin{array}{c}n-m+1\\ m\end{array}\end{array}& \begin{array}{c}n-m+3\\ m\left(m-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}-m-1\\ n-1\end{array}\end{array}& \begin{array}{c}-m+1\\ m\left(m-1\right)\end{array}\end{array}& \begin{array}{c}-m+3\\ m\left(m-1\right)\left(n-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}\right)$

证明：根据$C_n$ 和$Q_m$ 的结构特征及邻接谱的定义，由表1和表3可得邻接谱。由引理1可知，$C_n\times Q_m$ 的特征值，为$n-m-1,n-m+1,n-m+3,\cdots ,-m-1,-m+1,-m+3,\cdots$ 。重数分别为：$1,m,\frac{m\left(m-1\right)}{2},\cdots ,n-1,m\left(n-1\right),\frac{m\left(m-1\right)\left(n-1\right)}{2},\cdots$

由此可知$C_n\times Q_m$ 的邻接谱为：

$Sp\left(C_n\times Q_m\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}n-m-1\\ 1\end{array}& \begin{array}{c}n-m+1\\ m\end{array}\end{array}& \begin{array}{c}n-m+3\\ m\left(m-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}-m-1\\ n-1\end{array}\end{array}& \begin{array}{c}-m+1\\ m\left(m-1\right)\end{array}\end{array}& \begin{array}{c}-m+3\\ m\left(m-1\right)\left(n-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}\right)$

3.2. 互连网络$C_n\times Q_m$ 的Laplace谱

定理3.4互连网络$C_n\times Q_m$ 的Laplace谱为

$Sp\left(L\left(C_n\times Q_m\right)\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}n+1\\ 1\end{array}& \begin{array}{c}n+3\\ m\end{array}\end{array}& \begin{array}{c}n+5\\ m\left(m-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}1\\ n-1\end{array}\end{array}& \begin{array}{c}3\\ m\left(n-1\right)\end{array}\end{array}& \begin{array}{c}5\\ m\left(m-1\right)\left(n-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}\right)$

证明：由定义1和定理3.3，有互连网络$C_n\times Q_m$ 的正则度为$m+2$ ，特征值为$n-m-1,n-m+1,n-m+3,\cdots ,-m-1,-m+1,-m+3,\cdots$

根据引理1容易得出，互连网络的Laplace谱上的特征值是由互连网络的邻接谱的特征值与其正则度经过逐项相加得到的，相应重数不变。从而，互连网络$C_n\times Q_m$ 的Laplace特征值为$n+1,n+3,n+5,\cdots ,1,3,5,\cdots$

综上可知：

$Sp\left(L\left(C_n\times Q_m\right)\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}n+1\\ 1\end{array}& \begin{array}{c}n+3\\ m\end{array}\end{array}& \begin{array}{c}n+5\\ m\left(m-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}& \begin{array}{c}1\\ n-1\end{array}\end{array}& \begin{array}{c}3\\ m\left(n-1\right)\end{array}\end{array}& \begin{array}{c}5\\ m\left(m-1\right)\left(n-1\right)/2\end{array}\end{array}& \begin{array}{l}\cdots \\ \cdots \end{array}\end{array}\right)$

4. 互连网络$P_n\times Q_m$ 的谱特征

受第三节互连网络$C_n\times Q_m$ 谱特征证明思路，本节互连网络$P_n\times Q_m$ 的两种谱求解不再详细写出证明过程。又因对确定的互连网络$C_n\times Q_m$ 谱特征分析观察，没有一般的公式解。因此，本节利用上一节讨论两种谱特征思路，利用算法编程实现互连网络$P_n\times Q_m$ 两种谱特征的讨论。

4.1. 互连网络$P_n\times Q_m$ 的邻接谱

互连网络$P_n\times Q_m$ 的邻接谱求解算法思路：

第一步，设计Pancake网$P_n$ 邻接谱程序。根据表2的结果，我们利用Mathematica软件编程，可得Pancake网$P_n$ 邻接谱。

第二步，设计m-立方体$Q_m$ 邻接谱程序。根据表3的结果，我们利用Mathematica软件编程，可得m-立方体$Q_m$ 邻接谱。

第三步，根据引理1，设计任意两个特征值求和，即得互连网络$P_n\times Q_m$ 的邻接谱。即将上述两步得到的特征值分为两组数值列表，进而生成一个包含每组数值的所有可能的配对，每个配对求和并输出列表。

例1 画出互连网络$P_2\times Q_3$ 的图形并求解邻接谱。

解：互连网络$P_2\times Q_3$ 的图形，见图1：

Figure 1. $P_2\times Q_3$

图1. $P_2\times Q_3$

根据附录中的程序代码1，可得互连网络$P_2\times Q_3$ 的邻接谱

$Sp\left(A\left(P_2\times Q_3\right)\right)=\left(\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}-4\\ 1\end{array}& \begin{array}{c}-2\\ 4\end{array}\end{array}& \begin{array}{c}0\\ 6\end{array}\end{array}& \begin{array}{c}2\\ 4\end{array}\end{array}& \begin{array}{c}4\\ 1\end{array}\end{array}\right)$

4.2. 互连网络$P_n\times Q_m$ 的Laplace谱

上小节得到的邻接谱后，根据定义2和引理2，互连网络$P_n\times Q_m$ 的正则度为$\Delta \left(P_n\times Q_m\right)=diag\left\{\underset{n!\cdot 2^m}{\underbrace{n+m-1,n+m-1,\cdots ,n+m-1}}\right\}$ ，从而可得$P_n\times Q_m$ 的Laplace谱。我们也设计了程序代码，见附录。

例2 求解互连网络$P_2\times Q_3$ 的Laplace谱。

解：根据附录中的程序代码2，可得互连网络$P_2\times Q_3$ 的Laplace谱

$Sp\left(L\left(P_2\times Q_3\right)\right)=\left(\begin{array}{ccc}\begin{array}{cc}\begin{array}{cc}\begin{array}{c}0\\ 1\end{array}& \begin{array}{l}2\\ 4\end{array}\end{array}& \begin{array}{l}4\\ 6\end{array}\end{array}& \begin{array}{l}6\\ 4\end{array}& \begin{array}{c}8\\ 1\end{array}\end{array}\right)$

5. 总结

本文从师海忠构建的两类新的互连网络$C_n\times Q_m$ 和$P_n\times Q_m$ 的拓扑结构出发，根据邻接谱、Laplace谱定义，得到了邻接矩阵并刻画邻接谱特征、拉普拉斯矩阵并刻画Laplace谱特征，并根据证明思路设计了算法，文末附有程序代码。

根据定理3.3可知互连网络$C_n\times Q_m$ 随着n和m的增大，最大特征值与最小非零特征值之间的差距会越大，因此该图的直径会越来越小；同理可得互连网络$P_n\times Q_m$ 也是如此。

根据定理3.4可知互连网络$C_n\times Q_m$ 的Laplace矩阵第二小特征值(也称代数连通度)大于零，则该图是连通的；同理可得互连网络$P_n\times Q_m$ 也是连通的。又因为$C_n\times Q_m$ 的代数连通度大于$P_n\times Q_m$ ，因此互连网络$P_n\times Q_m$ 的节点间平均路径长度要比互连网络$C_n\times Q_m$ 更大。

下一步我们根据所得到的谱特征，研究其性质并反馈在互连网络的一些不变量中。

附 录

1.程序代码1：

n=Input["n="];

m=Input["m="];

FactorialPlusOne:=Factorial[n]+1;

g1=2*Cos[Pi*Range[1,FactorialPlusOne-1]/FactorialPlusOne];

g2=Eigenvalues[AdjacencyMatrix[HypercubeGraph[m]]];

cartesianProduct:=Tuples[{g1,g2}];

allSums:=Plus@@@cartesianProduct;

allSums

2.程序代码2：

n=Input["n="];

m=Input["m="];

FactorialPlusOne:=Factorial[n]+1;

g1=2*Cos[Pi*Range[1,FactorialPlusOne-1]/FactorialPlusOne];

g2=Eigenvalues[AdjacencyMatrix[HypercubeGraph[m]]];

cartesianProduct:=Tuples[{g1,g2}];

allSums:=Plus@@@cartesianProduct;

allSums

%+(n+m-1)

NOTES

^*通讯作者。