Double图的撞击时间的期望值 Expected Hitting Time of Double Graphs

doi:10.12677/PM.2021.114060

Pure Mathematics
Vol. 11 No. 04 ( 2021 ), Article ID: 41565 , 5 pages
10.12677/PM.2021.114060

Double图的撞击时间的期望值

孙春雨

●How to Cite this Article

华南理工大学数学学院，广东广州

收稿日期：2021年3月6日；录用日期：2021年4月8日；发布日期：2021年4月15日

摘要

令G为简单连通图，D_G为其double图，称图G的随机游走从点u首次到达点v所需步数的期望值为点u到点v的撞击时间的期望值。本文给出了D_G和G中任意两点撞击时间的期望值之间的关系。

关键词

Double图，撞击时间的期望值，随机游走，Randi 矩阵

Expected Hitting Time of Double Graphs

Chunyu Sun

School of Mathematics, South China University of Technology, Guangzhou Guangdong

Received: Mar. 6^th, 2021; accepted: Apr. 8^th, 2021; published: Apr. 15^th, 2021

ABSTRACT

Let G be a simple connected graph and let D_G be its double graph. The expected hitting time from vertices u to v is the expected value of the minimum number of jumps the random walk needs from u to v. In this paper, a relation for the expected hitting time between any two vertices of D_G and G is displayed.

Keywords:Double Graph, Expected Hitting Time, Random Walk, Randić Matrix

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

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

1. 引言

令 $G = (V_{G}, E_{G})$ 为简单连通图。顶点v的邻域表示G中与v相邻的顶点的集合，记为 $N_{G} (v)$ 。v的度定义为 $N_{G} (v)$ 的元素个数，记为 $d_{G} (v) = | N_{G} (v) |$ 。G的邻接矩阵A(G)是如下的0~1方阵：如果u和v相邻，则它的(u, v)元为1，否则为0。D(G)为G的度对角矩阵。G的Laplacian矩阵定义为 $L (G) = D (G) - A (G)$ 。

对于图G而言，如果它的一个简单的随机游走满足从当前的一个顶点u以 $1 / d_{G} (u)$ 的概率到达它的下一个邻点v，则该简单随机游走构成一个马尔可夫链。点u到点v的撞击时间的期望值定义为G的所有马尔科夫链中从点u首次到达点v所经过的步数的期望值，记为 $H_{G} (u, v)$ 。随机游走的撞击时间的期望值是一个很重要的图参数 [1] [2] 并已被广泛研究 [3] [4] [5] [6]。通常，很难从其定义中给出两个给定顶点之间的撞击时间的期望值的表达式，尤其是在复杂的网络结构的情况下。计算撞击时间的期望值的一项非凡成就归功于 [7]，他根据正则Laplacian特征值及其对应的特征向量给出了一个公式(请参见下面的引理2.1)。因此，获得正则Laplacian特征值及其对应的特征向量是计算撞击时间的期望值的最有效方法之一。但是，对于一般图要给出正则Laplacian特征值及其对应的特征向量非常困难。然后，许多研究人员试图研究一些特殊类别的图，例如参见 [8] [9] [10]。

令G是顶点集为 $V_{G} = {v_{1}, v_{2}, \dots, v_{n}}$ 的图。取G的一个复制，其对应顶点集记为 ${{v^{'}}_{1}, {v^{'}}_{2}, \dots, {v^{'}}_{n}}$ ，对每个i，令 ${v^{'}}_{i}$ 与 $N_{G} (v_{i})$ 中所有点相连接，我们将所得的图称为G的double图，记为D_G，显然 $| V_{D_{G}} | = 2 | V_{G} |$ 和 $| E_{D_{G}} | = 4 | E_{G} |$ 。有关double图的更多性质和应用，请参考 [11] [12] [13]。本文主要结论如下：

定理1.1设G为边数为m的连通图， $V_{G} = {v_{1}, v_{2}, \dots, v_{n}}$ 。令D_G为G的double图， $V_{D_{G}} = {v_{1}, v_{2}, \dots, v_{n}, {v^{'}}_{1}, {v^{'}}_{2}, \dots, {v^{'}}_{n}}$ ，其中 ${v^{'}}_{i}$ 对应于 $v_{i}, 1 \leq i \leq n$ ，则

1) $H_{D_{G}} (v_{i}, v_{j}) = H_{D_{G}} ({v^{'}}_{i}, {v^{'}}_{j}) = H_{G} (v_{i}, v_{j}) + \frac{2 m}{d_{G} (v_{j})}, i, j \in {1, 2, \dots, n}$ ；

2) $H_{D_{G}} (v_{i}, {v^{'}}_{i}) = H_{D_{G}} ({v^{'}}_{i}, v_{i}) = \frac{4 m}{d_{G} (v_{i})}, 1 \leq i \leq n$ ；

3) $H_{D_{G}} (v_{i}, {v^{'}}_{j}) = H_{D_{G}} ({v^{'}}_{i}, v_{j}) = H_{G} (v_{i}, v_{j}) + \frac{2 m}{d_{G} (v_{j})}, i, j \in {1, 2, \dots, n}$ 。

2. 预备知识

在本节，我们给出一些基本定义和相关引理，这些结果将用于证明我们的主要结论。给定一个连通图G，G的Randi 矩阵 [14] 定义为

$R (G) = D {(G)}^{- 1 / 2} A (G) D {(G)}^{- 1 / 2} .$ (2.1)

设 $λ_{1} \geq λ_{2} \geq λ_{3} \geq \dots \geq λ_{n}$ 为 $R (G)$ 的全部特征值， $x_{1}, x_{2}, \dots, x_{n}$ 为相应的两两正交的单位特征向量，则由文献 [15]， $λ_{1} = 1, λ_{2} < 1$ 当且仅当G是连通图。设 $U = (x_{1}, x_{2}, \dots, x_{n})$ ，则U是正交矩阵，即

$\sum_{k = 1}^{n} x_{i k} x_{j k} = \sum_{k = 1}^{n} x_{k i} x_{k j} = {\begin{matrix} 1, i = j; \\ 0, i \neq j . \end{matrix}$ (2.2)

设 $x_{i} = {(x_{i 1}, x_{i 2}, \dots, x_{i n})}^{t}$ ，其中t表示转置，则容易得到

$x_{1} = {(\sqrt{d_{G} (v_{1}) / 2 m}, \sqrt{d_{G} (v_{2}) / 2 m}, \dots, \sqrt{d_{G} (v_{n}) / 2 m})}^{t} .$ (2.3)

1993年，Lovász [7] 给出了关于撞击时间的期望的公式，如下所示：

引理2.1 ( [7] )设G为具有m条边的n阶图，则对于任意 $v_{i}, v_{j} \in V_{G}$ ，

$H_{G} (v_{i}, v_{j}) = 2 m \sum_{k = 2}^{n} \frac{1}{1 - λ_{k}} [\frac{x_{k j}^{2}}{d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{\sqrt{d_{G} (v_{i}) d_{G} (v_{j})}}] .$

给定一个连通图G，其中 $| V_{G} | = n, | E_{G} | = m$ ，则 $| V_{D_{G}} | = 2 n, | E_{D_{G}} | = 4 m$ ，我们有

$A (D_{G}) = (\begin{matrix} A (G) & A (G) \\ A (G) & A (G) \end{matrix}), D (D_{G}) = (\begin{matrix} 2 D (G) & 0 \\ 0 & 2 D (G) \end{matrix}) .$

再由(2.1)得出

$\begin{matrix} R (D_{G}) = D {(D_{G})}^{- 1 / 2} A (D_{G}) D {(D_{G})}^{- 1 / 2} \\ = (\begin{matrix} \frac{1}{\sqrt{2}} D {(G)}^{- 1 / 2} & 0 \\ 0 & \frac{1}{\sqrt{2}} D {(G)}^{- 1 / 2} \end{matrix}) (\begin{matrix} A (G) & A (G) \\ A (G) & A (G) \end{matrix}) (\begin{matrix} \frac{1}{\sqrt{2}} D {(G)}^{- 1 / 2} & 0 \\ 0 & \frac{1}{\sqrt{2}} D {(G)}^{- 1 / 2} \end{matrix}) \\ = \frac{1}{2} (\begin{matrix} R (G) & R (G) \\ R (G) & R (G) \end{matrix}) \end{matrix}$ (2.4)

接下来，我们求出 $R (D_{G})$ 的特征值和相应的正交特征向量，如下所示：

引理2.2设G为具有m条边的n阶图， $1 = λ_{1} \geq λ_{2} \geq \dots \geq λ_{n} \geq - 1$ 为 $R (G)$ 的特征值， $x_{1}, x_{2}, \dots, x_{n}$ 为相应的正交特征向量，则 $R (D_{G})$ 的特征值和相应的正交特征向量如下：

1) 特征值1的重数为1及其相应的特征向量为

${(\sqrt{d_{G} (v_{1}) / 4 m}, \dots, \sqrt{d_{G} (v_{n}) / 4 m}, \sqrt{d_{G} (v_{1}) / 4 m}, \dots, \sqrt{d_{G} (v_{n}) / 4 m})}^{t};$

2) 特征值0的重数为n及其相应的特征向量为

$\frac{1}{\sqrt{2}} (\begin{matrix} x_{i} \\ - x_{i} \end{matrix})$

其中 $i = 1, 2, \dots, n$ 。

3) $λ_{k} (k = 2, 3, \dots, n)$ 为 $R (D_{G})$ 的特征值，其相应的特征向量为

$\frac{1}{\sqrt{2}} (\begin{matrix} x_{k} \\ x_{k} \end{matrix}) .$

证明：1) 因为 $| E_{D_{G}} | = 4 m$ ， $\forall v_{i}, {v^{'}}_{i} \subseteq V_{D_{G}}, i = 1, 2, \dots, n$ 。 $d_{D_{G}} (v_{i}) = d_{D_{G}} ({v^{'}}_{i}) = 2 d_{G} (v_{i})$ ，则由(2.3)得出：特征值1相应的特征向量为

${(\sqrt{d_{G} (v_{1}) / 4 m}, \dots, \sqrt{d_{G} (v_{n}) / 4 m}, \sqrt{d_{G} (v_{1}) / 4 m}, \dots, \sqrt{d_{G} (v_{n}) / 4 m})}^{t} .$

2) 由(2.4)，我们有

$R (D_{G}) (\begin{matrix} x_{i} \\ - x_{i} \end{matrix}) = \frac{1}{2} (\begin{matrix} R (G) & R (G) \\ R (G) & R (G) \end{matrix}) (\begin{matrix} x_{i} \\ - x_{i} \end{matrix}) = 0.$

进而，

${(\begin{matrix} x_{i} \\ - x_{i} \end{matrix})}^{t} (\begin{matrix} x_{j} \\ - x_{j} \end{matrix}) = 2 x_{i}^{t} x_{j} = {\begin{matrix} 2, i = j; \\ 0, i \neq j . \end{matrix}$

因此，0为 $R (D_{G})$ 的特征值， $\frac{1}{\sqrt{2}} (\begin{matrix} x_{i} \\ - x_{i} \end{matrix}), i = 1, 2, \dots, n$ 为相应的单位特征向量。

3) 由(2.4)，我们有

$R (D_{G}) (\begin{matrix} x_{k} \\ x_{k} \end{matrix}) = \frac{1}{2} (\begin{matrix} R (G) & R (G) \\ R (G) & R (G) \end{matrix}) (\begin{matrix} x_{k} \\ x_{k} \end{matrix}) = λ_{k} (\begin{matrix} x_{k} \\ x_{k} \end{matrix}) .$

另外，

${(\begin{matrix} x_{k} \\ x_{k} \end{matrix})}^{t} (\begin{matrix} x_{j} \\ x_{j} \end{matrix}) = 2 k_{i}^{t} x_{j} = {\begin{matrix} 2, k = j; \\ 0, k \neq j . \end{matrix}$

因此， $λ_{k}$ 为 $R (D_{G})$ 的特征值， $\frac{1}{\sqrt{2}} (\begin{matrix} x_{k} \\ x_{k} \end{matrix}), k = 2, 3, \dots, n$ 为相应的单位特征向量。

3. 定理1.1的证明

在本节，我们根据引理2.1和引理2.2给出定理1.1的证明。

证明：1) 回顾： $| E_{D_{G}} | = 4 | E_{G} | = 4 m$ ，由引理2.1和引理2.2，我们有

$\begin{matrix} H_{D_{G}} (v_{i}, v_{j}) = 8 m [\sum_{k = 2}^{n} \frac{1}{1 - λ_{k}} (\frac{x_{k j}^{2}}{4 d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{4 \sqrt{d_{G} (v_{i}) d_{G} (v_{j})}}) + \sum_{k = 1}^{n} (\frac{x_{k j}^{2}}{4 d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{4 \sqrt{d_{G} (v_{i}) d_{G} (v_{j})}})] \\ = 2 m \sum_{k = 2}^{n} \frac{1}{1 - λ_{k}} (\frac{x_{k j}^{2}}{4 d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{4 \sqrt{d_{G} (v_{i}) d_{G} (v_{j})}}) + \frac{2 m}{d_{G} (v_{j})} = H_{G} ((v_{i}, v_{j}) + \frac{2 m}{d_{G} (v_{j})} \end{matrix}$ (3.1)

其中 $i \neq j$ ，由(2.2)可得(3.1)中等号成立。由D_G的对称性，，其中 $i \neq j$ 。

2) 由引理2.1、引理2.2和(2.2)可得：

$H_{D_{G}} (v_{i}, {v^{'}}_{i}) = 8 m \sum_{k = 1}^{n} (\frac{x_{k i}^{2}}{4 d_{G} (v_{i})} + \frac{x_{k i}^{2}}{4 d_{G} (v_{i})}) = \frac{4 m}{d_{G} (v_{i})} .$

由D_G的对称性， $H_{D_{G}} ({v^{'}}_{i}, v_{i}) = \frac{4 m}{d_{G} (v_{i})}$ ，其中 $1 \leq i \leq n$ 。

3) 再由引理2.1、引理2.2和(2.2)，我们有

$\begin{matrix} H_{D_{G}} (v_{i}, {v^{'}}_{j}) = 8 m [\sum_{k = 2}^{n} \frac{1}{1 - λ_{k}} (\frac{x_{k j}^{2}}{4 d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{4 \sqrt{d_{G} (v_{i}) d_{G} (v_{j})}}) + \sum_{k = 1}^{n} (\frac{x_{k j}^{2}}{4 d_{G} (v_{j})} + \frac{x_{k i} x_{k j}}{4 \sqrt{d_{G} (v_{i}) d_{G} (v_{j})}})] \\ = 2 m \sum_{k = 2}^{n} \frac{1}{1 - λ_{k}} (\frac{x_{k j}^{2}}{d_{G} (v_{j})} - \frac{x_{k i} x_{k j}}{\sqrt{d_{G} (v_{i}) d_{G} (v_{j})}}) + \frac{2 m}{d_{G} (v_{j})} = H_{G} (v_{i}, v_{j}) + \frac{2 m}{d_{G} ( v j )} \end{matrix}$

其中 $i \neq j$ ，由D_G的对称性， $H_{D_{G}} ({v^{'}}_{i}, {v^{'}}_{j}) = H_{G} (v_{i}, v_{j}) + \frac{2 m}{d_{G} (v_{j})}$ ，其中 $i \neq j$ 。

致谢

本论文在写作过程中和黄晶博士进行了有益的讨论，在此表示感谢！

基金项目

本论文由广州市基础与应用基金(项目编号：201804010102)支持。

文章引用

孙春雨. Double图的撞击时间的期望值
Expected Hitting Time of Double Graphs[J]. 理论数学, 2021, 11(04): 472-476. https://doi.org/10.12677/PM.2021.114060

参考文献

1. Aldous, D.J. (1993) Reversible Markov Chains and Random Walks on Graphs. University of California, Berkeley.

2. Kemeny, J.G. and Snell, J.L. (1960) Finite Markov Chains. Van Nostrand, Princeton.

3. Chang, X. and Xu, H. (2017) Chung-Yau Invariants and Graphs with Symmetric Hitting Times. Journal of Graph Theory, 85, 691-705. https://doi.org/10.1002/jgt.22099

4. Georgakopoulos, A. and Wagner, S. (2017) Hitting Times, Cover Cost, and the Wiener Index of a Tree. Journal of Graph Theory, 84, 311-326. https://doi.org/10.1002/jgt.22029

5. Xu, H. and Yau, S.-T. (2013) Discrete Greens Functions and Random Walks on Graphs. Journal of Combinatorial Theory, Series A, 120, 483-499. https://doi.org/10.1016/j.jcta.2012.10.002

6. Xu, H. and Yau, S.-T. (2014) An Explicit Formula of Hitting Times for Random Walks on Graphs. Pure and Applied Mathematics Quarterly, 10, 567-581. https://doi.org/10.4310/PAMQ.2014.v10.n3.a6

7. Lova ́sz, L. (1993) Random Walks on Graphs: A Survey. Paul Erdo ̈s is Eighty, Bolyai Society Mathematical Studies, 2, 1-46.

8. Chen, H.Y. (2018) Hitting Times for Random Walks on Subdivision and Triangulation Graphs. Linear and Multilinear Algebra, 66, 117-130. https://doi.org/10.1080/03081087.2017.1287159

9. Huang, J. and Li, S.C. (2018) Expected Hitting Times for Random Walks on Quadrilateral Graphs and Their Applications. Linear and Multilinear Algebra, 66, 2389-2408. https://doi.org/10.1080/03081087.2017.1395793

10. Wang, C.Y., Guo, Z.L. and Li, S.C. (2018) Expected Hitting Times for Random Walks on the k-Triangle Graph and Their Applications. Applied Mathematics and Computation, 338, 698-710. https://doi.org/10.1016/j.amc.2018.06.056

11. Munarini, E., Cippo, C.P., Scagliola, A. and Salvi, N.Z. (2008) Double Graphs. Discrete Mathematics, 308, 242-254. https://doi.org/10.1016/j.disc.2006.11.038

12. Xin, L.W. and Yi, W.F. (2011) The Number of Spanning Trees of Double Graphs. Kragujevac Journal of Mathematics, 35, 183-190.

13. Zhang, Z.F., Qiu, P.X., Zhang, D.H., Bian, L., Li, J.W. and Zhang, T. (2008) The Double Graph and the Complement Double Graph of a Graph. Advances in Mathematics (China), 37, 303-310.

14. Gutman, I., Furtula, B. and Bozkurt, S. (2014) On Randic Energy. Linear Algebra and Its Applications, 422, 50-57. https://doi.org/10.1016/j.laa.2013.06.010

15. Chung, F.R.K. (1997) Spectral Graph Theory. American Mathematical Society, Providence.

期刊菜单