互连网络 C n × S m 的谱特征及其能量

期刊菜单

互连网络 $C_{n} \times S_{m}$ 的谱特征及其能量
Spectral Characteristics and Energy of Interconnected Networks

C_{n} \times S_{m}

DOI: 10.12677/pm.2025.153101, PDF, HTML, XML,
作者: 杨金娜, 陈语哲, 梁志鹏^*：塔里木大学信息工程学院，新疆阿拉尔
关键词: 互连网络；邻接谱；Laplace谱；能量；Interconnected Network； Adjacency Spectrum； Laplace Spectrum； Energy

摘要: 图的特征值集及其多重性称为谱，它可以用来获得图的各种拓扑性质，如连通性、韧性等。师海忠利用图的笛卡尔乘积方法构建了新的笛卡尔乘积互连网络

C_{n} \times S_{m}

。本文根据分析研究互连网络的拓扑结构，刻画了

C_{n} \times S_{m}

的邻接谱和Laplace谱。进一步，根据Laplace矩阵的Fiedler向量对

C_{n} \times S_{m}

进行了图划分。另外，我们还研究得到了谱能量表达式。

Abstract: The eigenvalue set and its multiplicity of a graph are called spectra, which can be used to obtain various topological properties of the graph, such as connectivity, resilience, etc. Shi Haizhong used the Cartesian product method of graphs to construct a new Cartesian product interconnection network

C_{n} \times S_{m}

. This article describes the adjacency spectrum and Laplace spectrum of

C_{n} \times S_{m}

based on the analysis and research of the topology structure of interconnected networks. Furthermore,

C_{n} \times S_{m}

was graphically partitioned based on the Fiedler vector of the Laplace matrix. In addition, we have also studied the expression of spectral energy.

文章引用：杨金娜, 陈语哲, 梁志鹏. 互连网络

C_{n} \times S_{m}

的谱特征及其能量[J]. 理论数学, 2025, 15(3): 262-272. https://doi.org/10.12677/pm.2025.153101

1. 引言

根据Laplace谱确定的Fiedler向量进行的图划分是一种有效的图分割方法[1]，它基于图的特征值分解和Fiedler向量的特性，是网络分析及其应用有效研究方法之一。Laplace能量在图论、信号处理、图像处理等多个领域也具有广泛的应用前景。因此，深入研究Laplace谱与图能量及其关系对于推动相关领域的发展具有重要意义。

图的笛卡尔乘积方法是由Sabidussi在1957年和1960年提出的一种重要的构图方法，它是从已知图构造更大图的有效手段，也是网络设计的一种核心手段。基于笛卡尔乘积互连网络的谱对于研究图论之所以重要，主要在于可以用其计算图的诸多不变量，如特征值及其重数等关键参数。在文献[2]-[6]中，对于一些著名的互连网络谱的研究，如(广义)超立方体、折叠超立方体、增广超立方体的(拉普拉斯)谱等，虽然给出了特征值，但并未得到相应重数。而本文利用其公式进行了具体证明研究，如互连网络 $C_{n} \times S_{m}$ 的邻接谱、拉普拉斯谱和能量公式，我们先给出环网 $C_{n}$ 和星图 $S_{m}$ 的定义，利用公式，得到并证明研究 $C_{n} \times S_{m}$ 的邻接谱和Laplace谱，并对其顶点进行了划分，再利用互连网络 $C_{n} \times S_{m}$ 的特征谱，计算得到了其能量。

下面给出本文所需的一些定义符号。

2. 基本概念

定义1 [2] 环网 $C_{n}$ 是无向图，是循环无向图 $G (n, \pm 1)$ ，也是Cayley图。

Cayley图Star网络 $S_{m}$ ，对于给定的 $S_{m}$ Star网络 $(m \geq 2)$ ，是如下Cayley图 $C_{Γ} (P)$ ， $Γ = S_{m}$ 是集合 ${1, 2, \dots, n}$ 上的对称群， $P = {123 \dots (i - 1) i (i + 1) \dots n / 2 \leq i \leq n}$ 即为图 $S_{m}$ ，环网 $C_{n}$ 与Star网络的笛卡尔乘积互连网络表示为 $C_{n} \times S_{m}$ 。

根据定义，互连网络 $C_{n} \times S_{m}$ 有如下性质：

1) $C_{n} \times S_{m}$ 有 $n \cdot m!$ 个顶点、 $\frac{1}{2} (m + 1)! \cdot n$ 条边。

2) $C_{n} \times S_{m}$ 是 $m + 1$ 正则的连通图。

为了方便，互连网络 $C_{n} \times S_{m}$ 可用如下二元n序列来定义。

设有 $C_{n}$ 的顶点为①，②， $\dots$ ，ⓝ $\in {(0, n) /$ ⓘ $\in N}$ ， $S_{m}$ 的顶点为 $1, 2, \dots, N \in {(0, m) / j \in N}$ ，当且仅当jⓘ有且仅有一个坐标不同。具体示例如下图1。

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

$S p (G) = (\begin{matrix} λ_{1} & λ_{2} & \dots & λ_{n} \\ x_{1} & x_{2} & \dots & x_{n} \end{matrix})$

其中 $λ_{1}, λ_{2}, \dots, λ_{n}$ ，为特征值， $x_{1}, x_{2}, \dots, x_{n}$ 为特征值对应的重数。

Figure 1. Interconnection network $C_{3} \times S_{3}$ and interconnection network $C_{3} \times S_{4}$

图1. 互连网络 $C_{3} \times S_{3}$ 和互连网络 $C_{3} \times S_{4}$

定义3 [3] 设L是Laplace矩阵，由 $L = Δ - A$ ，以及特征方程 $| λ E - L | = 0$ 的解构成所有特征值的集合，称为Laplace谱，记作 $S p (L)$ 。

$S p (L) = (\begin{matrix} μ_{1} & μ_{2} & \dots & μ_{n} \\ y_{1} & y_{2} & \dots & y_{n} \end{matrix})$

其中D与A分别是与L同阶的对角矩阵。矩阵D的对角线上的元素为对应的正则度，矩阵A为邻接矩阵。

定义4 [4] [5] 邻接谱能量为 $E (G) = \sum_{j = 1}^{n} | λ_{j} |$ 、Laplace谱能量为 $L E (G) = \sum_{j = 1}^{n} | λ_{j} - \frac{2 m}{n} |$ 。

为了完成结论的证明，先给出下述的三个引理。

$A (S_{m})$ 为其对应的邻接矩阵。如：

$A (S_{3}) = (\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix})$ , $A (S_{4}) = (\begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix})$

经观察易得图 $S_{4}$ 的邻接矩阵 $A (S_{4})$ 为 $A (S_{4}) = (\begin{matrix} A (S_{3}) & I_{1 \times 3} \\ I_{1 \times 3}^{T} & 0_{1} \end{matrix})$ 。一般地，图 $S_{m}$ 的邻接矩阵 $A (S_{m})$ 为 $A (S_{m}) = (\begin{matrix} A (S_{m - 1}) & I_{1 \times (m - 1)} \\ I_{1 \times (m - 1)}^{T} & 0_{1} \end{matrix})$ 。

引理 1 Star网络 $S_{m}$ 的邻接矩阵为 $A (S_{m}) = (\begin{matrix} A (S_{m - 1}) & I_{1 \times (m - 1)} \\ I_{1 \times (m - 1)}^{T} & 0_{1} \end{matrix})$ ，邻接谱为表1。

证明：Star网络 $S_{m}$ 的邻接谱为 $λ E - A (S_{m}) = | \begin{matrix} λ & - 1 & - 1 & \dots & - 1 \\ - 1 & λ & 0 & \dots & 0 \\ - 1 & 0 & λ & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ - 1 & 0 & 0 & 0 & λ \end{matrix} | = (λ^{2} - (m - 1)) λ^{m - 2}$ ，当

$(λ^{2} - (m - 1)) λ^{m - 2} = 0$ ，得到 $λ_{1} = 0$ (重数为 $m - 2$ )， $λ_{2} = \sqrt{m - 1}$ (重数为1)， $λ_{3} = - \sqrt{m - 1}$ (重数为1)。

同样地，据文献[6] Star网络 $S_{m}$ 、环网 $C_{n}$ 的邻接谱如表1、表2：

Table 1. Adjacency spectrum of Star network $S_{m}$

表1. Star网络 $S_{m}$ 的邻接谱

m	特征值	重数
3	$\sqrt{2}, - \sqrt{2}, 0$	1, 1, 1
4	$\sqrt{3}, - \sqrt{3}, 0$	1, 1, 2
5	$\sqrt{4}, - \sqrt{4}, 0$	1, 1, 3
6	$\sqrt{5}, - \sqrt{5}, 0$	1, 1, 4
$\dots$	$\dots$	$\dots$
m	$\sqrt{m - 1}, - \sqrt{m - 1}, 0$	1, 1, m − 2

Table 2. Adjacent spectrum of ring network $C_{n}$

表2. 环网 $C_{n}$ 的邻接谱

n	特征值	重数
3	2, −1	1, 2
4	3, −1	1, 3
5	4, −1	1, 4
6	5, −1	1, 5
$\dots$	$\dots$	$\dots$
n	n − 1, −1	1, n − 1

引理2 [1] 设图G和图H的特征根分别是 $λ_{1}, λ_{2}, \dots, λ_{n}$ 和 $μ_{1}, μ_{2}, \dots, μ_{n}$ ，则笛卡尔乘积图的特征值为 $λ_{i} + μ_{j}$ ，其中 $(1 \leq i \leq n, 1 \leq j \leq m)$ 。

引理3 [3] 已知图的邻接矩阵为A，邻接谱

$S p (A) = (\begin{matrix} λ_{1} & λ_{2} & \dots & λ_{t} \\ μ_{1} & μ_{2} & \dots & μ_{t} \end{matrix})$ ,

正则度为 $Δ$ ，则它的Laplace谱为

$S p (L) = (\begin{matrix} λ_{1} + Δ & λ_{2} + Δ & \dots & λ_{t} + Δ \\ μ_{1} & μ_{2} & \dots & μ_{t} \end{matrix})$

3. 互连网络 $C_{n} \times S_{m}$ 的谱

本节主要刻画互连网络 $C_{n} \times S_{m}$ 的邻接谱和Laplace谱。进一步，根据Laplace矩阵的Fiedler向量对 $C_{n} \times S_{m}$ 进行了图划分。

3.1. $C_{n} \times S_{m}$ 的邻接谱

引理2.1 在图 $C_{n} \times S_{m}$ 中：当n与m共同改变时，图 $C_{n} \times S_{m}$ 的邻接矩阵可表示为

$A (C_{n} \times S_{m}) = (\begin{matrix} A_{m} & I_{m} & O_{m} & \dots & I_{m} \\ I_{m} & A_{m} & I_{m} & \dots & O_{m} \\ O_{m} & I_{m} & A_{m} & \dots & O_{m} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ I_{m} & O_{m} & O_{m} & \dots & A_{m} \end{matrix})$ ，这是一个n阶分块对角矩阵，其中， $S_{m}$ 是Star网络 $S_{m}$ 的邻接矩

阵，而 $I_{m}$ 与 $A_{m}$ 分别是与 $S_{m}$ 同阶的分块单位矩阵和零矩阵。

定理2.2 对于给定的n与m $(n \geq 3, m \geq 2)$ 中，互连网络 $C_{n} \times S_{m}$ 的邻接谱为

$S p (C_{n} \times S_{m}) = (\begin{matrix} n - 1 - \sqrt{m - 1} & n - 1 & n - 1 + \sqrt{m - 1} & - 1 - \sqrt{m - 1} & - 1 & - 1 + \sqrt{m - 1} \\ 1 & m - 2 & 1 & n - 1 & (m - 2) (n - 1) & n - 1 \end{matrix})$

证明：对于给定的n与m $(n \geq 3, m \geq 2)$ 中，Star网络 $S_{m}$ 的特征值为：0， $- \sqrt{m - 1}$ ， $\sqrt{m - 1}$ ，重数分别为 $m - 2$ ，1，1环网 $C_{n}$ 的特征值为： $n - 1$ ，−1重数分别为1， $n - 1$ 。

由引理2，得到 $C_{n} \times S_{m}$ 的特征值为 $n - 1 - \sqrt{m - 1}$ ， $n - 1$ ， $n - 1 + \sqrt{m - 1}$ ， $- 1 - \sqrt{m - 1}$ ，−1， $- 1 + \sqrt{m - 1}$ 。其重数分别为1， $m - 1$ ，1， $n - 1$ ， $(m - 1) (n - 1)$ ， $n - 1$

综上所述， $C_{n} \times S_{m}$ 的谱

通过利用定理2.2我们可以很容易的得到一些维数较低的互连网络的邻接谱。如：

$S p (C_{3} \times S_{3}) = (\begin{matrix} 2 - \sqrt{2} & 2 & 2 + \sqrt{2} & - 1 - \sqrt{2} & - 1 & - 1 + \sqrt{2} \\ 1 & 1 & 1 & 2 & 2 & 2 \end{matrix})$

$S p (C_{3} \times S_{4}) = (\begin{matrix} 2 - \sqrt{3} & 2 & 2 + \sqrt{3} & - 1 - \sqrt{3} & - 1 & - 1 + \sqrt{3} \\ 1 & 2 & 1 & 2 & 4 & 2 \end{matrix})$

3.2. $C_{n} \times S_{m}$ 的Laplace谱

根据引理3，互连网络的Laplace谱实际上是由网络的邻接谱的特征值与其正则度经过逐项相加确定的，且对应特征值的重数不变。因此，互连网络 $C_{n} \times S_{m}$ 的Laplace谱特征有如下结论：

定理2.3 互连网络 $C_{n} \times S_{m}$ 的Laplace谱为

$L (C_{n} \times S_{m}) = (\begin{matrix} n - \sqrt{m - 1} + m & n + m & n + \sqrt{m - 1} + m & m - \sqrt{m - 1} & m & m + \sqrt{m - 1} \\ 1 & m - 2 & 1 & n - 1 & (m - 2) (n - 1) & n - 1 \end{matrix})$

证明：根据定义性质，互连网络 $C_{n} \times S_{m}$ 的正则度为 $m + 1$ ，邻接矩阵特征值为 $n - 1 - \sqrt{m - 1}$ ， $n - 1$ ， $n - 1 + \sqrt{m - 1}$ ， $- 1 - \sqrt{m - 1}$ ，−1， $- 1 + \sqrt{m - 1}$ 。

由引理3可知：

通过利用定理2。3我们可以很容易的得到一些维数较低的互连网络的Laplace谱。如：

$L (C_{3} \times S_{3}) = (\begin{matrix} 6 - \sqrt{2} & 6 & 6 + \sqrt{2} & 3 - \sqrt{2} & 3 & 3 + \sqrt{2} \\ 1 & 1 & 1 & 2 & 2 & 2 \end{matrix})$

$L (C_{3} \times S_{4}) = (\begin{matrix} 7 - \sqrt{3} & 7 & 7 + \sqrt{3} & 4 - \sqrt{3} & 4 & 4 + \sqrt{3} \\ 1 & 2 & 1 & 2 & 4 & 2 \end{matrix})$

3.3. $C_{n} \times S_{m}$ 的顶点划分

与Laplace谱的第二小特征值相关的特征向量(称为Fiedler向量)可用于对图划分。为此，我们根据第二小特征值的Fiedler向量中的正负值对应的顶点划分，将互连网络 $C_{n} \times S_{m}$ 的顶点划分为两部分。根据Fiedler向量的值较大的顶点通常是图中的关键节点，去掉这些节点会显著影响图的连通性，如去掉这些关键节点会导致电力网络的断开，从而影响电力供应。

算法如下：

算法2.4

输入：互连网络 $C_{n} \times S_{m}$ 的邻接矩阵A

$V_{1} \leftarrow \emptyset, V_{2} \leftarrow \emptyset$

计算度矩阵 $Δ$ ， $L = Δ - A$

计算L的特征值与特征向量

记 $e_{2}$ 为L的第二小特征值

记 $c_{2}$ 为 $e_{2}$ 对应的特征向量

对所有 $x \in c_{2}$

若 $x > 0$ 则 $V_{1} \leftarrow V_{1} \cup {x}$

若 $x < 0$ 则 $V_{2} \leftarrow V_{2} \cup {x}$

输出：两个顶点集合 $V_{1}$ 和 $V_{2}$

例1 互连网络 $C_{3} \times S_{4}$ 的顶点划分。

解：根据上述算法2.4，我们设计了顶点划分程序代码(见附录)，得到了互连网络 $C_{3} \times S_{4}$ 的顶点划分集 $V_{1}$ 和 $V_{2}$ ，其中集合 $V_{1}$ 是指互连网络 $C_{3} \times S_{4}$ 的Fiedler向量中正值对应的顶点，集合 $V_{2}$ 是指互连网络 $C_{3} \times S_{4}$ 的Fiedler向量中负值对应的顶点。具体对应顶点如下：

集合 $V_{1}$ ： ${(0, 0), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 2), (2, 3), (3, 0), (3, 2), (3, 3)}$

集合 $V_{2}$ ： ${(0, 1), (1, 1), (2, 1) (3, 1) (2, 0)}$

4. $C_{n} \times S_{m}$ 的能量

根据两个能量的定义公式，由上节得到的谱特征值，下面我们重点分类讨论邻接谱能量、Laplace谱能量并得其能量公式。

4.1. 邻接谱能量

根据定义4，邻接谱的能量公式为 $E (G) = \sum_{j = 1}^{n} | λ_{j} |$ ， $λ$ 为邻接谱特征值，再由定理2.2，互连网络 $C_{n} \times S_{m}$ 的邻接谱为

$(n \geq 3, m \geq 2)$ ，我们可以得到互连网络 $C_{n} \times S_{m}$ 的邻接谱特征值和重数并代入邻接谱的能量公式 $E (G) = \sum_{j = 1}^{n} | λ_{j} |$ ，有互连网络 $C_{n} \times S_{m}$ 的邻接谱能量为

$\begin{matrix} E (G) = \sum_{j = 1}^{n} | λ_{j} | \\ = \sum_{i = 1}^{1} | n - 1 - \sqrt{m - 1} | + \sum_{i = 1}^{m - 2} | n - 1 | + \sum_{i = 1}^{1} | n - 1 + \sqrt{m - 1} | \\ + \sum_{i = 1}^{n - 1} | - 1 - \sqrt{m - 1} | + \sum_{i = 1}^{(m - 2) (n - 1)} | - 1 | + \sum_{i = 1}^{n - 1} | - 1 + \sqrt{m - 1} | \\ = | n - 1 - \sqrt{m - 1} | + (m - 2) | n - 1 | + | n - 1 + \sqrt{m - 1} | \\ + (n - 1) | - 1 - \sqrt{m - 1} | + (m - 2) (n - 1) + (n - 1) | - 1 + \sqrt{m - 1} | \\ = | n - 1 - \sqrt{m - 1} | + (m - 2) (n - 1) + (n - 1 + \sqrt{m - 1}) \\ + (n - 1) (1 + \sqrt{m - 1}) + (m - 2) (n - 1) + (n - 1) (- 1 + \sqrt{m - 1}) \\ = 2 m n - 2 m - 3 n + 3 + (2 n - 1) \sqrt{m - 1} + | n - 1 - \sqrt{m - 1} | \end{matrix}$

已知 $(n \geq 3, m \geq 2)$ 。下面分情况讨论：

1) 当 $n - 1 > \sqrt{m - 1}$ ，即 $n > \sqrt{m - 1} + 1 \geq 1$

$\begin{matrix} E (G) = 2 m n - 2 m - 3 n + 3 + (2 n - 1) \sqrt{m - 1} + (n - 1 - \sqrt{m - 1}) \\ = 2 m n - 2 m - 2 n + 2 + (2 n - 2) \sqrt{m - 1} \\ = 2 (m - 1 + \sqrt{m - 1}) (n - 1) \end{matrix}$

2) $n - 1 \leq \sqrt{m - 1}$ ，即 $n \leq \sqrt{m - 1} + 1$

$\begin{matrix} E (G) = 2 m n - 2 m - 3 n + 3 + (2 n - 1) \sqrt{m - 1} - (n - 1 - \sqrt{m - 1}) \\ = 2 (m - 2) (n - 1) + 2 n \sqrt{m - 1} \end{matrix}$

由上述讨论，我们得到如下定理：

定理3.1 1) 当 $n > \sqrt{m - 1} + 1 \geq 1$ ， $E (G) = 2 (m - 1 + \sqrt{m - 1}) (n - 1)$

2) 当 $n \leq \sqrt{m - 1} + 1$ ， $E (G) = 2 (m - 2) (n - 1) + 2 n \sqrt{m - 1}$

4.2. Laplace谱能量

根据定义4，Laplace谱能量为 $L E (G) = \sum_{j = 1}^{n} | λ_{j} - \frac{2 m}{n} |$ ， $λ$ 为Laplace谱特征值，再根据定理2.3互连网络 $C_{n} \times S_{m}$ 的Laplace谱为

$(n \geq 3, m \geq 2)$ ，我们可以得到互连网络 $C_{n} \times S_{m}$ 的Laplace谱特征值和重数并代入Laplace谱的能量公式 $L E (G) = \sum_{j = 1}^{n} | λ_{j} - \frac{2 m}{n} |$ ，有

Laplace谱能量为

$\begin{matrix} L E (G) = \sum_{j = 1}^{n} | λ_{j} - \frac{2 m}{n} | \\ = \sum_{i = 1}^{1} | n + m - \sqrt{m - 1} - \frac{2 m}{n} | + \sum_{i = 1}^{m - 2} | n + m - \frac{2 m}{n} | + \sum_{i = 1}^{1} | n + m + \sqrt{m - 1} - \frac{2 m}{n} | \\ + \sum_{i = 1}^{n - 1} | m - \sqrt{m - 1} - \frac{2 m}{n} | + \sum_{i = 1}^{(m - 2) (n - 1)} | m - \frac{2 m}{n} | + \sum_{i = 1}^{n - 1} | \sqrt{m - 1} + m - \frac{2 m}{n} | \\ = | n + m - \sqrt{m - 1} - \frac{2 m}{n} | + (m - 2) | n + m - \frac{2 m}{n} | + | n + m + \sqrt{m - 1} - \frac{2 m}{n} | \\ + (n - 1) | m - \sqrt{m - 1} - \frac{2 m}{n} | + (m - 2) (n - 1) | m - \frac{2 m}{n} | + (n - 1) | m + \sqrt{m - 1} - \frac{2 m}{n} | \end{matrix}$

已知 $(n \geq 3, m \geq 2)$ ， $n, m$ 为 $N^{+}$ ，故有 $m < m + n, - \sqrt{m - 1} - \frac{2 m}{n} < - \frac{2 m}{n} < \sqrt{m - 1} - \frac{2 m}{n}$ 。下面分情况讨论：

1) 当 $n \geq 4$ 时， $m - \sqrt{m - 1} - \frac{2 m}{n} \geq m - \sqrt{m - 1} - \frac{m}{2} = \frac{m}{2} - \sqrt{m - 1} \geq 0$

$\begin{matrix} L E (G) = (n + m - \sqrt{m - 1} - \frac{2 m}{n}) + (m - 2) (n + m - \frac{2 m}{n}) \\ + (n + m + \sqrt{m - 1} - \frac{2 m}{n}) + (n - 1) (m - \sqrt{m - 1} - \frac{2 m}{n}) \\ + (m - 2) (n - 1) (m - \frac{2 m}{n}) + (n - 1) (m + \sqrt{m - 1} - \frac{2 m}{n}) \\ = m (n m - 2 m + n) \end{matrix}$

4) 当 $n = 3$ 时， $m - \sqrt{m - 1} - \frac{2 m}{n} = \frac{m}{3} - \sqrt{m - 1}$

$\begin{matrix} L E (G) = | 3 - \sqrt{m - 1} + \frac{m}{3} | + (m - 2) | 3 + \frac{m}{3} | + | 3 + \sqrt{m - 1} + \frac{m}{3} | + (n - 1) | - \sqrt{m - 1} + \frac{m}{3} | \\ + (m - 2) (n - 1) | \frac{m}{3} | + (n - 1) | \sqrt{m - 1} + \frac{m}{3} | \\ = (3 - \sqrt{m - 1} + \frac{m}{3}) + (m - 2) (3 + \frac{m}{3}) + (3 + \sqrt{m - 1} + \frac{m}{3}) + (n - 1) | - \sqrt{m - 1} + \frac{m}{3} | \\ + (m - 2) (n - 1) \frac{m}{3} + (n - 1) (\sqrt{m - 1} + \frac{m}{3}) \end{matrix}$

若 $- \sqrt{m - 1} + \frac{m}{3} \geq 0$ ，即 $m > \frac{9}{2} + \frac{3 \sqrt{5}}{2}$ ，则有 $L E (G) = m^{2} + 3 m$

若 $- \sqrt{m - 1} + \frac{m}{3} < 0$ ，即 $2 \leq m < \frac{9}{2} + \frac{3 \sqrt{5}}{2}$ ，则有 $L E (G) = m^{2} + \frac{5 m}{3} + 4 \sqrt{m - 1}$

由上述讨论，我们得到如下定理：

定理3.2

当 $n = 3$ ， $L E (G) = {\begin{cases} m^{2} + 3 m, m > \frac{9}{2} + \frac{3 \sqrt{5}}{2} \\ m^{2} + \frac{5 m}{3} + 4 \sqrt{m - 1}, 2 \leq m < \frac{9}{2} + \frac{3 \sqrt{5}}{2} \end{cases}$

当 $n \geq 4$ ， $L E (G) = m (n m - 2 m + n)$ 。

附录

顶点划分程序代码：

import numpy as npimport networkx as nxfrom scipy.sparse import csr_matrixfrom scipy.sparse.linalg import eigsh def create_node_index_map(graph): return {node: idx for idx, node in enumerate(graph.nodes())} def laplacian_matrix(graph, node_index_map): n = len(node_index_map) row, col, data = [], [], [] for u, nbrs in graph.adjacency(): u_idx = node_index_map[u] degree_u = len(nbrs) for v in nbrs: v_idx = node_index_map[v] row.append(u_idx) col.append(v_idx) data.append(-1.0) row.append(u_idx) col.append(u_idx) data.append(degree_u) return csr_matrix((data, (row, col)), shape=(n, n), dtype=float) def fiedler_vector_from_laplacian(L): eigvals, eigvecs = eigsh(L, k=2, which='SM') return eigvecs[:, 1].real def partition_graph_by_fiedler_vector(fiedler_vec, node_index_map): partition = {+1: set(), -1: set()} for node, idx in node_index_map.items(): sign = np.sign(fiedler_vec[idx]) partition[sign].add(node) return partition n = 4 m = 3 C = nx.cycle_graph(n) S = nx.star_graph(m) G = nx.cartesian_product(C, S) node_index_map = create_node_index_map(G) L = laplacian_matrix(G, node_index_map) fiedler_vec = fiedler_vector_from_laplacian(L) partition = partition_graph_by_fiedler_vector(fiedler_vec, node_index_map) print("图的顶点划分结果：")for sign, nodes in partition.items(): print(f"集合 {sign}: {nodes}")

NOTES

^*通讯作者。

参考文献

[1]	Fiedler, M. (1973) Algebraic Connectivity of Graphs. Czechoslovak Mathematical Journal, 23, 298-305. https://doi.org/10.21136/cmj.1973.101168
[2]	师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学, 2013, 40(S1): 265-270+306.
[3]	Brouwer, A.E. and Haemers, W.H. (2012) Spectra of Graphs. Springer.
[4]	Gutman, I. and Zhou, B. (2006) Laplacian Energy of a Graph. Linear Algebra and Its Applications, 414, 29-37. https://doi.org/10.1016/j.laa.2005.09.008
[5]	So, W., Robbiano, M., de Abreu, N.M. and Gutman, I. (2009) Applications of a Theorem by Ky Fan in the Theory of Graph Energy. Linear Algebra and Its Applications, 432, 2163-2169.
[6]	Florkowski III, S.F. (2008) Spectral Graph Theory of the Hypercube. Naval Postgraduate School.

为你推荐

友情链接