二部图无符号积和多项式根的性质

Properties of the Roots of the Unsigned Permanent Polynomial of Bipartite Graphs

摘要: 令$G$ 是$n$ 个顶点的二部图。任意图的所有特征值都是实数，并且一个图是二部图当且仅当其谱关于原点对称。本文主要研究了二部图的无符号积和多项式的根的性质。

Abstract: Let $G$ be a bipartite graph on $n$ vertices. It is well known that all eigenvalues of any graph are real, and that a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. This paper mainly studies the properties of the roots of the unsigned product and sum polynomials of bipartite graphs.

1. 引言

令$G$ 是$n$ 个顶点的二部图。积和式由Binet和Cauchy分别独立提出[1]。它在组合计数和图论上有着重要应用。积和式理论广泛渗透于量子化学、统计物理与信息科学等前沿方向，其数值求解的极端难度也使该课题长期跻身国际数学界的核心关注之列。Agrawal [2]在2006年世界数学家大会的45分钟报告中详细报告了积和式研究的最新进展。

积和多项式作为积和式的衍生物，是图的一个组合不变量，涉及信息科学、网络科学、统计物理和结构化学等。作为图论研究的关键手段，积和多项式由Kasum等人[3]与Merris团队[4]在数学和化学两大领域分别独立引入。积和多项式在计算高精度富勒烯上的研究可参见文献[5]。学界主要围绕各类图矩阵对应的积和多项式，对其根分布及系数结构展开深入探讨。柳顺义，张和平等人[6]指出：若一般图出现非零实根，则必为正数；二部图则无此非零实根；只要图含至少一条边，其积和多项式必存在非实复根。部分积和多项式的性质可参见文献[7]和[8]。与图的积和多项式相关的永久和问题研究可参见文献[9]。柳顺义[10]对双变量积和多项式进行了系数研究并证明了路、圈、完全二部图等均由双变量积和多项式确定。由于积和多项式的计算是#p完全问题[11]，因此无符号积和多项式的研究也很困难。目前关于无符号积和多项式的研究文献较少，因此无符号积和多项式的相关问题是值得关注并深入探索的问题。本文主要研究了二部图的无符号积和多项式的根的性质，并证明了二部图的无符号积和根关于实轴和虚轴都是对称的。

2. 相关概念

设$G$ 是一个简单图。其顶点集为$V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ 。图$G$ 的邻接矩阵$A\left(G\right)=\left(a_{ij}\right)$ 是一个$n$ 阶方阵，其中：$a_{ij}=1$ ，如果$v_i$ 与$v_j$ 在$G$ 中相邻；$a_{ij}=0$ ，如果$v_i$ 与$v_j$ 在$G$ 中不相邻。

记$S_n$ 为$n$ 次对称群。一个$n$ 阶方阵$M=\left(m_{ij}\right)$ 的行列式定义为

$\det M={\displaystyle \sum _{\tau \in S_n}{\left(-1\right)}^{\text{sgn}\left(\tau \right)}}{\displaystyle \prod _{i=1}^n{m}_{i\tau \left(i\right)}},$

这里$\mathrm{sgn}\left(\tau \right)$ 代表排列$\tau$ 的奇偶符号。

若将行列式展开式中每一项前的系数统一替换为+1，便得到矩阵积和式的定义。设$M=\left(m_{ij}\right)$ 是一个$n$ 阶方阵，其积和式定义为：

$\text{per}M={\displaystyle \sum _{\tau \in S_n}{\displaystyle \prod _{i=1}^n{m}_{i\tau \left(i\right)}}}.$

设$G$ 是一个简单图。$A\left(G\right)$ 是$G$ 的邻接矩阵。图$G$ 的特征多项式定义为

$\varphi \left(G,x\right)=\det \left(x{I}_n-A\left(G\right)\right)$

这里$I_n$ 表示$n$ 阶单位矩阵。图$G$ 的特征多项式的根称为图$G$ 的特征根。图$G$ 的所有特征根构成的多重集称为$G$ 的谱。同样，$G$ 的所有无符号积和根构成的多重集称为$G$ 的无符号积和谱。对矩阵$x{I}_n+A\left(G\right)$ 求积和式运算，即可导出该图对应的无符号积和多项式。

给定$n$ 个顶点的图$G$ ，记其邻接矩阵为$A\left(G\right)$ 。图$G$ 的无符号积和多项式由下式定义：

$\pi \left(G,x\right)=\text{per}\left(x{I}_n+A\left(G\right)\right).$

图$G$ 的无符号积和多项式的根称为图$G$ 的无符号积和根。

3. 图的无符号积和多项式根的一些性质

一个图$G$ 被称为Sachs子图，如果$G$ 的每一个组成部分是孤立边或单圈。Merris [12]得到图的积和多项式改良Sachs定理。本文得到了图的无符号积和多项式改良Sachs定理如下：

定理3.1 设$G$ 是一个简单图，$A\left(G\right)$ 是$G$ 的邻接矩阵。如果

$\pi \left(G,x\right)=\text{per}\left(x{I}_n+A\left(G\right)\right)={\displaystyle {\sum }_{k=0}^n{a}_k{x}^{n-k}},$

则$a_k={\displaystyle \sum _{U\in {\mathcal{U}}_k}{2}^{c\left(U\right)}}$ ，$1\le k\le n$ 。式中$U_k$ 表示$G$ 中所有恰好k个顶点的Sachs子图之集合，$c\left(U\right)$ 为子图U所含圈的个数。

该公式之所以关键，在于它把无符号积和多项式的各阶系数与图的具体结构直接挂钩。根据无符号积和多项式的定义可得：$a_0=1$ ，$a_i\ge 0,\left(i=1,2,\cdots ,n\right)$ 。通过图的无符号积和多项式改良Sachs定理可得：$a_1\equiv 0$ ，图$G$ 中孤立边数为$a_2$ ，图$G$ 中二倍三角形数为$a_3$ 。

根据积和式的定义，可得以下定理：

定理3.2 对于图$G$ 的无符号积和多项式$\pi \left(G,x\right)$ ，如果$G$ 在某区间内不存在任何无符号积和根，则该区间被称为无根区间。对图簇$S$ 而言，若其中每张图在此区间皆无根，则该区间即称为整个图族的统一无根区间。

定理3.3 设$G$ 为$n$ 阶图，则其无符号积和多项式在0处的重数等于$n-p$ ，这里$p$ 表示$G$ 中最大Sachs子图所能包含的顶点数。

定理3.3 可由定理3.1得到，作为直接推论，有以下两个推论。

推论3.4 图$G$ 以0为无符号积和根等价于$G$ 不存在生成Sachs子图。

推论3.5 若$G$ 是二部图，则无符号积和多项式零根的重数等于图$G$ 的亏量(即最大匹配未能覆盖的顶点数目[13])。

根据Borowiecki在文献[14]关于积和多项式和二部图的结论，本文得到无符号积和多项式与二部图的结论。

定理3.6 令$G$ 是一个有$n$ 个顶点的图，且$\pi \left(G,x\right)={\displaystyle {\sum }_{k=0}^n{a}_k{x}^{n-k}}$ 。则$G$ 是二部图当且仅当对于所有的奇数$i$ ，都有$a_i=0$ 。

证明：由定理3.1可知：无符号积和多项式的系数$a_i\ge 0$ 。若图存在奇圈，则图对应的奇次项系数严格大于0 (因为没有像行列式那样的符号抵消)。若对于所有的奇数$i$ ，都有$a_i=0$ ，则说明图不含奇圈，为二部图。若$G$ 是二部图，则无法构造出奇数个顶点的Sachs子图，因此对于所有的奇数$i$ ，都有$a_i=0$ 。

4. 二部图的无符号积和根

由复共轭根定理，如果$z\in C$ 是$\pi \left(G,x\right)$ 的一个复根，则$\overline{z}$ 也是$\pi \left(G,x\right)$ 的一个复根。以下证明一个二部图的所有非零无符号积和根均以纯虚根对$\left(ib,-ib\right),b\in R$ 且$b\ne 0$ ，和四元对$\pm a\pm ib,a,b\in R$ 的形式出现。

定理4.1 令$Q\left(x\right)=x^n+a_1{x}^{n-2}+a_2{x}^{n-4}+\cdots +a_n{x}^{n-2p}$ ，这里$p\le \frac{n}{2}$ ，$a_i\in R$ ，$a_p\ne 0$ 。于是，多项式$Q\left(x\right)$ 的零点必然关于实轴与虚轴同时对称；换言之，所有非零的无符号积和根均成对出现，形式为：实数对$\left(a,-a\right),a\in R$ ，纯虚数对$\left(ib,-ib\right),b\in R$ ，和四元对$\pm a\pm ib,a,b\in R$ 。

证明：令$f\left(s\right)=s^p+a_1{s}^{p-1}+a_2{s}^{p-2}+\cdots +a_{p-1}s+a_p$ ，则：

$Q\left(x\right)=x^n-2p\left(x^{2p}+a_1{x}^{2p-2}+a_2{x}^{2p-4}+\cdots +a_p\right)=x^{n-2p}f\left(x^2\right)$

显然，$Q\left(x\right)$ 的根由0和$f\left(x^2\right)$ 的根共同构成，其中0的个数为$n-2p$ 。因为$a_p\ne 0$ ，则0不是$f\left(s\right)$ 的根。

设$f\left(s\right)$ 的根为$z_1,\overline{z_1},z_2,\overline{z_2},\cdots ,z_t,\overline{z_t},a_1,a_2,\cdots ,a_l,c_1,c_2,\cdots ,c_m$ ，这里$z_j\left(j=1,\cdots ,t\right)$ 为复数，$a_j\left(j=1,\cdots ,l\right)$ 为正数，$c_j\left(j=1,\cdots ,m\right)$ 为负数，且$2t+l+m=p$ 。

令$z_j=r_j{\text{e}}^{i{\theta }_j}\left({\theta }_j\ne k\pi ,k=0,\pm 1,\pm 2,\cdots \right)$ ，其中$i^2=-1$ ，则$\overline{z_j}=r_j{\text{e}}^{-i{\theta }_j}$

求解方程$x^2=z_j$ ，得：

$\{\begin{array}{l}{x}_0=\sqrt{r_j}{\text{e}}^{i\frac{{\theta }_j}{2}}=\sqrt{r_j}\left(\cos \frac{{\theta }_j}{2}+i\sin \frac{{\theta }_j}{2}\right)\hfill \\ x_1=\sqrt{r_j}{\text{e}}^{i\frac{{\theta }_j+2\pi }{2}}=\sqrt{r_j}\left(-\cos \frac{{\theta }_j}{2}-i\sin \frac{{\theta }_j}{2}\right)\hfill \end{array}$

求解方程$x^2=\overline{z_j}$ ，得：

$\{\begin{array}{l}{x}_2=\sqrt{r_j}{\text{e}}^{i\frac{-{\theta }_j}{2}}=\sqrt{r_j}\left(\cos \frac{{\theta }_j}{2}-i\sin \frac{{\theta }_j}{2}\right)\hfill \\ x_3=\sqrt{r_j}{\text{e}}^{i\frac{-{\theta }_j+2\pi }{2}}=\sqrt{r_j}\left(-\cos \frac{{\theta }_j}{2}+i\sin \frac{{\theta }_j}{2}\right)\hfill \end{array}$

求解方程$x^2=a_j$ ，得：$x_{4,5}=\pm \sqrt{a_j}$ 。

求解方程$x^2=c_j$ ，得：$x_{6,7}=\pm \sqrt{c_j}$ 。

综上所述，定理得证。

定理4.2 一个图$G$ 是二部图，当且仅当其无符号积和谱在复平面上同时关于实轴与虚轴对称。

证明：设$G$ 为含$n$ 个顶点的图，且其无符号积和谱同时关于实轴与虚轴对称。设$\pi \left(G,x\right)={\displaystyle {\sum }_{k=0}^p{a}_k{x}^{n-k}}$ ，其中$p$ 表示图$G$ 的最大Sachs子图所能覆盖的顶点总数。

令$f\left(s\right)=s^p+a_1{s}^{p-1}+a_2{s}^{p-2}+\cdots +a_{p-1}s+a_p$ ，则$\pi \left(G,x\right)=x^{n-p}f\left(x\right)$ 。显见，多项式$\pi \left(G,x\right)$ 的零点由0与$f\left(x\right)$ 的根联合组成，其中0的个数为$n-2p$ 。易知$G$ 没有正的无符号积和根。

设$G$ 的无符号积和根为

$\left\{0,\cdots ,0\right\}\cup \left\{\pm a_j\pm i{c}_j|a_j,c_j\in R,a_j>0,c_j>0,j=1,\cdots ,t\right\}\cup \left\{\pm i{d}_j|d_j\in R,d_j>0,j=1,\cdots ,l\right\}$

这里$4t+2l=p$ 。令$z_j=a_j+i{c}_j$ ,则：

$f\left(x\right)={\displaystyle {\prod }_{i=1}^t\left(\left(x-z_j\right)\left(x+z_j\right)\left(x-\overline{z_j}\right)\left(x+\overline{z_j}\right)\right)}{\displaystyle {\prod }_{j=1}^l\left(\left(x-i{d}_j\right)\left(x+i{d}_j\right)\right)}$

进一步，化简得：

$f\left(x\right)={\displaystyle {\prod }_{j=1}^t\left(x^4-2\left(a_j^2-c_j^2\right)x^2+{\left(a_j^2+c_j^2\right)}^2\right)}{\displaystyle {\prod }_{j=1}^l\left(x^2+d_j^2\right)}$

由于$f\left(x\right)$ 的奇次项系数全为0，设$\begin{array}{c}f\left(x\right)=x^p+{a^{\prime }}_2{x}^{p-2}+{a^{\prime }}_4{x}^{p-4}+\cdots +{a^{\prime }}_{p-2}{x}^2+{a^{\prime }}_p\end{array}$ ，因此

$\pi \left(G,x\right)=x^{n-p}\left(x^p+{a^{\prime }}_2{x}^{p-2}+{a^{\prime }}_4{x}^{p-4}+\cdots +{a^{\prime }}_{p-2}{x}^2+{a^{\prime }}_p\right)=x^n+{a^{\prime }}_2{x}^{n-2}+{a^{\prime }}_4{x}^{n-4}+\cdots +{a^{\prime }}_{p-2}{x}^{n-p+2}+{a^{\prime }}_p{x}^{n-p}$

由定理3.6可得：$G$ 是二部图。定理的充分性证明完毕。

由定理3.6和定理4.1可得：二部图的无符号积和谱在复平面上关于坐标实轴和虚轴对称。定理的必要性证明完毕。

综上所述，一个图$G$ 是二部图，当且仅当其无符号积和谱在复平面上同时关于实轴与虚轴对称。