图的距离模式识别集由Acharya在2006年向Germina提出, 随后Germina等人对此展开了研究, 一些有意思的结论见文献[1-8].图的一个距离模式识别集是图的一个自同构群, 图的每个顶点可由它与距离模式识别集的关系所唯一确定.图可能存在距离模式识别集也可能不存在距离模式识别集, 存在距离模式识别集的图称为距离模式识别图, 否则称为非距离模式识别图.图$G$的距离模式识别集可能不唯一, 阶数最小的距离模式识别集的阶数称为图的距离模式识别数(记为$\rho(G)$).如何判定图的距离模式识别数是个有意思的问题.本文判定两类非距离模式识图, 得到几类图的距离模式识别集和距离模式识别数, 最后给出一个计算距离模式识别率的算法.

定义2.1^[1]  设$v$为图$G(V, E)$的任意一个顶点, 非空集合$M\subseteq{V(G)}$, $j$为非负整数, 记$N^M_j(v)=\{u\in M:d(u, v)=j\}$, 称集合$f_M(v)=\{d(u, v):u\in M\}$为$v$的$M$ -距离模式.显然, $f_M(v)=\{j:N^M_j(v)\neq\phi\}$.如果$f_M:v\mapsto\ f_M(v)$是单射, 那么称$M$为$G$的距离模式识别集.记$n\times(d_G+1)$阶矩阵$D^M_G=(|N^M_{j-1}(v_i)|)$, $j=1, 2, \cdots, ~(d_G+1)$ ($n=|V|, $ $d_G$为$G$的直径), 将$D^M_G$中的非零元用1替换得矩阵$D^{*M}_G$.

定义2.2  设$G_1(V_1, E_1)$和$G_2(V_2, E_2)$为两个简单图, 它们的积图${G_1}\times{G_2}$定义为

$ V({{G}_{1}}\times {{G}_{2}})={{V}_{1}}\times {{V}_{2}}, \\ E({{G}_{1}}\times {{G}_{2}})=\{({{u}_{1}},{{v}_{1}})({{u}_{2}},{{v}_{2}})|{{u}_{1}}={{u}_{2}}\ \ \rm{且}~\ {{\mathit{v}}_{1}}\tilde{\ }{{\mathit{v}}_{2}}\ \rm{或者}~\ {{\mathit{v}}_{1}}={{\mathit{v}}_{2}}\ \\ \rm{且}~\ {{\mathit{u}}_{1}}\tilde{\ }{{\mathit{u}}_{2}}\}, \\ $

其中$v_1\sim{v_2}$表示$v_1$与$v_2$在$G_2$中邻接, $u_1\sim{u_2}$表示$u_1$与$u_2$在$G_1$中邻接, 若$G_1$和$G_2$为两条路, 则它们的积图为方格图.

引理2.3^[2]  设图为$G(V, E)$, 非空集合$M\subseteq{V(G)}$, $M$为$G$的距离模式识别集的充分必要条件是$D^{*M}_G$的任意两行互异.

例2.4  图 1给出了两个图, 其中$G$为距离模式识别图, $H$为非距离模式识别图.

在$G$中, 令$M=\{b, c, e\}$, 则

$ \begin{eqnarray*}&&f_M(a)=\{1, 3\}, f_M(b)=\{0, 1, 3\}, \\ && f_M(c)=\{0, 1, 2\}, f_M(d)=\{1, 2\}, f_M(e)=\{0, 2, 3\}, \\ &&N^M_0(a)=\phi, ~N^M_1(a)=\{b, c\}, N^M_2(a)=\phi, ~N^M_3(a)=\{e\}, \\ &&N^M_0(b)=\{b\}, N^M_1(b)=\{c\}, ~~N^M_2(b)=\phi, ~N^M_3(b)=\{e\}, \\ &&N^M_0(c)=\{c\}, N^M_1(c)=\{b\}, ~~N^M_2(c)=\{e\}, N^M_3(c)=\phi, \\ &&N^M_0(d)=\phi, ~N^M_1(d)=\{c, e\}, N^M_2(d)=\{b\}, N^M_3(d)=\phi, \\ &&N^M_0(e)=\{e\}, N^M_1(e)=\phi, ~~~N^M_2(e)=\{c\}, N^M_3(e)=\{b\}.\\ &&D^M_G=\left( \begin{array}{cccc} 0&2&0&1 \\ 1&1&0&1 \\ 1&1&1&0 \\ 0&2&1&0 \\ 1&0&1&1 \end{array} \right), D^{*M}_G=\left( \begin{array}{cccc} 0&1&0&1 \\ 1&1&0&1 \\ 1&1&1&0 \\ 0&1&1&0 \\ 1&0&1&1 \end{array} \right).\end{eqnarray*} $

$D^{*M}_G$的任意两行互异, 所以$M$为$G$的距离模式识别集, 即$G$为距离模式识别图, 且$\rho(G)=3$. $H$不存在距离模式识别集, 即$H$为非距离模式识别图.

引理2.5^[2]  设$C_n$为$n$阶圈, 则$C_n$为距离模式识别图的充分必要条件是$n\geq7$.

引理2.6^[3]  设$G$为距离模式识别图, $M$为$G$的距离模式识别集.那么$M$的导出子图$G[M]$是非连通的.

引理2.7^[1]  (a)平凡图$K_1$是唯一的距离模式识别数为自身价数的图.

(b) 路是唯一的距离模式识别数为1的图.

(c) 不存在距离模式识别数为2的图.

(d) 若$n\geq7$, 则$\rho(C_n)=3$.

定理3.1  (a)设$G$为任意给定的图, $v$为$G$的任一顶点, $H_1$为$G$在点$v$粘三个悬挂点所得的图, 则$H_1$为非距离模式识别图.

(b) 设树$T^*$如图 2所示, 将$T^*$粘到(在点$v$处)任一图的任一顶点上得$H_2$, 则$H_2$为非距离模式识别图.

证  (a)设粘到点$v$上的三个悬挂点分别为$v_1$, $v_2$, $v_3$.假设$H_1$有一个距离模式识别集$M$, 对$v_1$, $v_2$, $v_3$而言有以下两种情形:

情形1  $v_1, v_2, v_3$中至少有两个顶点属于$M$.不失一般性, 令$v_1, v_2$属于$M$, 那么在$D^{*M}_{H_1}$中对应于$v_1, v_2$的两行相同, 与$M$为距离模式识别集矛盾.

情形2  $v_1, v_2, v_3$中至少有两个顶点不属于$M$.不失一般性, 令$v_1, v_2$属于$M$, 那么在$D^{*M}_{H_1}$中对应于$v_1, v_2$的两行也相同, 与$M$为距离模式识别集矛盾.

(b) 设树$T^*$的四个悬挂点分别为$v_1$, $v_2$, $v_3$, $v_4$.假设$H_2$有一个距离模式识别集$M$, 对$v_1$, $v_2$, $v_3$, $v_4$而言也有至少两个顶点属于$M$或者至少两个顶点不属于$M$的两种情形, 证明与(a)相同.所以结论成立.

定理3.2  设$C_n$为$n$($n\geq3$)阶圈, $P_m$为$m$($m\geq2$)阶路, 将$P_m$的一个悬挂点粘到$C_n$的一个顶点上得图$H$.当$m=2$且$n=3$或者$n=4$时, $H$为非距离模式识别图.其它情形$H$为距离模式识别图, 且$\rho(H)=3$.

证 情形1  $n=3$且$m=2$.设$C_3=v_1v_2v_3v_1$, $P_1=v_1v_4$是粘到$v_1$上的路.假设$H$有一个距离模式识别集$M$.由引理2.7知$|M|\neq1, 2, 4$, 那么$M$只能是$\{v_2, v_3, v_4\}$, 但在$D^{*M}_{H}$中对应于$v_2, v_3$的两行相同, 与$M$为距离模式识别集矛盾, 即$H$为非距离模式识别图.

情形2  $n=3$且$m>2$.设$C_3=v_1v_2v_3v_1$, $P_m=v_1v_4v_5{\cdots}v_{2+m}$是粘到$v_1$上的路.考察集合$M=\{v_1, v_3, v_5\}$, 则

$ D^{*M}_H=\\ \left( \begin{array}{cccccccccccc} 1&1&1&0&0&0&0&\cdots&0&0&0&0 \\ 0&1&0&1&0&0&0&\cdots&0&0&0&0 \\ 1&1&0&1&0&0&0&\cdots&0&0&0&0 \\ 0&1&1&0&0&0&0&\cdots&0&0&0&0 \\ 1&0&1&1&0&0&0&\cdots&0&0&0&0 \\ 0&1&0&1&1&0&0&\cdots&0&0&0&0 \\ 0&0&1&0&1&1&0&\cdots&0&0&0&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&0&0&0&\cdots&1&0&1&1 \end{array} \right). $

在$D^{*M}_H$中前五行互异, 从第六行开始, 第$i$行元素1的位置是第$i-1$行元素1的位置向右移一个单位所得$(i=6, \cdots, 2+m)$.所以$D^{*M}_H$的任意两行互异, $M$为$H$的距离模式识别集, 即$H$为距离模式识别图, 且$\rho(H)=3$.

情形3  $n=4$且$m=2$.设$C_4=v_1v_2v_3v_4v_1$, $P_1=v_1v_5$是粘到$v_1$上的路.假设$H$有一个距离模式识别集$M$.由引理2.6和引理2.7知$|M|\neq1, 2, 4, 5$, 那么$M$只能是$\{v_1, v_3, v_5\}$, $\{v_3, v_4, v_5\}$, $\{v_2, v_3, v_5\}$和$\{v_2, v_4, v_5\}$.容易验证对应的$D^{*M}_H$中总有两行相同, 与$M$为距离模式识别集矛盾, 即$H$为非距离模式识别图.

情形4  $n=4$且$m>2$.设$C_4=v_1v_2v_3v_4v_1, ~~ P_m=v_1v_5v_6{\cdots}v_{3+m}$是粘到$v_1$上的路.考察集合$M=\{v_1, v_2, v_6\}$, 则

$ D^{*M}_H=\left( \begin{array}{cccccccccccc} 1&1&1&0&0&0&\cdots&0&0&0&0 \\ 1&1&0&1&0&0&\cdots&0&0&0&0 \\ 0&1&1&0&1&0&\cdots&0&0&0&0 \\ 0&1&1&1&0&0&\cdots&0&0&0&0 \\ 0&1&1&0&0&0&\cdots&0&0&0&0 \\ 1&0&1&1&0&0&\cdots&0&0&0&0 \\ 0&1&0&1&1&0&\cdots&0&0&0&0 \\ 0&0&1&0&1&1&\cdots&0&0&0&0 \\ \cdots&\cdots&\cdots &\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&0&0&\cdots&1&0&1&1 \end{array} \right). $

在$D^{*M}_H$中前六行互异, 从第七行开始, 第$i$行元素1的位置是第$i-1$行元素1的位置向右移一个单位所得$(i=7, \cdots, 3+m)$.所以$D^{*M}_H$的任意两行互异, $M$为$H$的距离模式识别集, 即$H$为距离模式识别图, 且$\rho(H)=3$.

情形5  $n=5$且$m\geq2$.设$C_5=v_1v_2v_3v_4v_5v_1, ~~ P_m=v_1v_6v_7{\cdots}v_{4+m}$是粘到$v_1$上的路.考察集合$M=\{v_1, v_3, v_6\}$, 则

$ D^{*M}_H=\left( \begin{array}{cccccccccccc} 0&1&1&0&0&0&\cdots&0&0&0&0 \\ 1&1&1&0&0&0&\cdots&0&0&0&0 \\ 1&1&0&1&0&0&\cdots&0&0&0&0 \\ 0&1&1&1&0&0&\cdots&0&0&0&0 \\ 0&0&1&0&0&0&\cdots&0&0&0&0 \\ 1&0&1&1&0&0&\cdots&0&0&0&0 \\ 0&1&0&1&1&0&\cdots&0&0&0&0 \\ 0&0&1&0&1&1&\cdots&0&0&0&0 \\ \cdots&\cdots&\cdots &\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&0&0&\cdots&1&0&1&1 \end{array} \right). $

在$D^{*M}_H$中前六行互异, 从第七行开始, 第$i$行元素1的位置是第$i-1$行元素1的位置向右移一个单位所得$(i=7, \cdots, 4+m)$.所以$D^{*M}_H$的任意两行互异, $M$为$H$的距离模式识别集, 即$H$为距离模式识别图, 且$\rho(H)=3$.

情形6  $n=6$且$m\geq2$.设

$ C_6=v_1v_2v_3v_4v_5v_6v_1, ~~ P_m=v_1v_7v_8{\cdots}v_{5+m} $

是粘到$v_1$上的路.考察集合$M=\{v_1, v_3, v_7\}$, 则

$ D^{*M}_H=\left( \begin{array}{cccccccccccc} 1&1&1&0&0&0&\cdots&0&0&0&0 \\ 0&1&1&0&0&0&\cdots&0&0&0&0 \\ 1&0&1&1&0&0&\cdots&0&0&0&0 \\ 0&1&0&1&1&0&\cdots&0&0&0&0 \\ 0&0&1&1&0&0&\cdots&0&0&0&0 \\ 0&1&1&1&0&0&\cdots&0&0&0&0 \\ 1&1&0&1&0&0&\cdots&0&0&0&0 \\ 0&1&1&0&1&0&\cdots&0&0&0&0 \\ 0&0&1&1&0&1&\cdots&0&0&0&0 \\ \cdots&\cdots&\cdots &\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&0&0&\cdots&1&0&1&1 \end{array} \right). $

在$D^{*M}_H$中前七行互异, 从第八行开始, 第$i$行元素1的位置是第$i-1$行元素1的位置向右移一个单位所得$(i=8, \cdots, 5+m)$.所以$D^{*M}_H$的任意两行互异, $M$为$H$的距离模式识别集, 即$H$为距离模式识别图, 且$\rho(H)=3$.

情形7  $n\geq7$且$m\geq2$.设

$ C_n=v_1v_2v_3v_4{\cdots}v_nv_1, ~~ P_m=v_{[\frac{n}{2}]}v_{n+1}v_{n+2}{\cdots}v_{n+m-1} $

是粘到$v_{[\frac{n}{2}]}$ 上的路. 考察集合$M=\{v_1, v_2, v_4\}$, 由引理2.7知$M=\{v_1, v_2, v_4\}$是$C_n$的距离模式识别集, 所以在$D^{*M}_H$中对应于点$v_1, v_2, {\cdots}, v_n$的行是互异的.第$(n+1)$行元素1的位置是第$[\frac{n}{2}]$行元素1的位置向右移一个单位所得, 从第$(n+i)$行开始, 第$(n+(i+1))$行元素1的位置是第$(n+i)$行元素1的位置向右移一个单位所得$(i=1, 2, \cdots, m-2)$.所以$D^{*M}_H$的任意两行互异, $M$为$H$的距离模式识别集, 即$H$为距离模式识别图, 且$\rho(H)=3$.所以结论成立.

由定理3.2的证明不难得出下面推论.

推论3.3  设$G$为距离模式识别图, $P_m$为$m(\geq2)$阶路, 将$P_m$的一个悬挂点粘到$G$的一个顶点上得图$H$, 且$d_H=d_G+m-1$, 则$H$为距离模式识别集, 且$\rho(H)=\rho(G)$.

定理3.4  设$P_m$, $P_n$分别是$m$阶和$n$阶路, $G={P_m}\times{P_n}$是一个格子图$(m\geq2, n\geq4, n>m)$, 则$G$为距离模式识别图, 且$\rho(G)=3$.

证  设

$ V(G)=\{v_{11}, v_{12}, \cdots, v_{1n}, v_{21}, v_{22}, \cdots, v_{2n}, \cdots\cdots, \\ v_{m1}v_{m2}, \cdots, , v_{mn}\}, $

如果$M$是$G$的一个距离模式识别集, 则$|M|\geq3$.考察集合$M=\{v_{11}, v_{12}, v_{1n}\}$, 有两种情形.

情形1  $n$为奇数.在$D^{*M}_H$中对应点$v_{11}, v_{12}, \cdots, v_{1n}$的行所形成的子矩阵记为$D_1$, 则$D_1$为

$ \left( \begin{array}{ccccccccccccccccccc} 1&1&0&0&\cdots&0&0&0&0&0&0&0&\cdots&0&0&0&1&\cdots&0 \\ 1&1&0&0&\cdots&0&0&0&0&0&0&0&\cdots&0&0&1&0&\cdots&0 \\ 0&1&1&0&\cdots&0&0&0&0&0&0&0&\cdots&0&1&0&0&\cdots&0 \\ 0&0&1&1&\cdots&0&0&0&0&0&0&0&\cdots&1&0&0&0&\cdots&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots& \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&\cdots&0&1&1&0&1&0&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&0&1&1&0&0&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&0&1&1&1&0&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&1&0&0&1&1&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&1&0&0&0&0&1&1&\cdots&0&0&0&0&\cdots&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots& \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&1&0&0&\cdots&0&0&0&0&0&0&0&\cdots&0&1&1&0&\cdots&0 \\ 1&0&0&0&\cdots&0&0&0&0&0&0&0&\cdots&0 & 0&1&1&\cdots&0 \end{array} \right). $

$D_1$中的任意两行互异, 记$D_i$为$D^{*M}_H$中对应点$v_{i1}, v_{i2}, \cdots, v_{in}$的行所形成的子矩阵, 则$D_{i+1}$中的元素1的位置由$D_i$中的元素1的位置向右移一个单位得到$(i=1, 2, \cdots, m-1)$.所以$D^{*M}_H$的任意两行互异, $M$为$G$的距离模式识别集, 即$G$为距离模式识别图, 且$\rho(G)=3$.

情形2  $n$为偶数.在$D^{*M}_H$中对应点$v_{11}, v_{12}, \cdots, v_{1n}$的行所形成的子矩阵记为$D_1$, 则$D_1$为

$ \left( \begin{array}{cccccccccccccccccc} 1&1&0&0&\cdots&0&0&0&0&0&0&\cdots&0&0&0&1&\cdots&0 \\ 1&1&0&0&\cdots&0&0&0&0&0&0&\cdots&0&0&1&0&\cdots&0 \\ 0&1&1&0&\cdots&0&0&0&0&0&0&\cdots&0&1&0&0&\cdots&0 \\ 0&0&1&1&\cdots&0&0&0&0&0&0&\cdots&1&0&0&0&\cdots&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots& \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&0&0&0&\cdots&1&1&0&0&1&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&1&1&1&0&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&0&1&1&0&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&0&1&0&1&1&0&\cdots&0&0&0&0&\cdots&0 \\ 0&0&0&0&\cdots&1&0&0&0&1&1&\cdots&0&0&0&0&\cdots&0 \\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots& \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots \\ 0&1&0&0&\cdots&0&0&0&0&0&0&\cdots&0&1&1&0&\cdots&0 \\ 1&0&0&0&\cdots&0&0&0&0&0&0&\cdots&0&0 & 1&1&\cdots&0 \end{array} \right). $

后面的证明与情形1相同.所以结论成立.

设图$G(V, E)$为简单图, 非空集合$M\subseteq{V(G)}$, 记$r_M$为$D^{*M}_G$所有行构成的集合的阶, 称$\mu(G)=\max\limits_{M\subseteq V}{\frac{r_M}{|V|}}$为$G$的距离模式识别率, 当$\mu(G)=1$时$G$为距离模式识别图, 当$\mu(G)<1$时$G$为非距离模式识别图.以下给出计算图的距离模式识别率和距离模式识别数的算法:

第一步  利用弗洛伊德算法计算$G$的距离矩阵$D$.

第二步  求出$G$的所有$n\times k$阶子阵$D^\prime$以及与$D^\prime$对应的顶点集$M$ (其中$1\leq k\leq n$且$k\neq2$).

第三步  求出$M$对应的$D^{*M}_G$以及$r_M$.

第四步  计算距离模式识别率$\mu(G)=\max\limits_{M\subseteq V}{\frac{r_M}{|V|}}$, 当$\mu(G)=1$时, 输出所有距离模式识别集$M$, 转第五步.

第五步  计算距离模式识别数$\rho(G)=\min|M|$.