Commute time 定理、对任意的节点s和t,Cs,t=2mRef(s,t),其中m= E(G)儿. 证明(cont'd): ds-2m 2m L(h.,t-h.s)= u 0 d:-2m 2m 因此h-九 2m 2=bst。回顾L中=bt,有解，且解空间是一维的 令中= -, 有 2m Refr(S,t)=φ(s)-中(t)= hst-hss hithts hstt hts Cst 2m 2m 2m 2m 6Commute time 定理. 对任意的节点� 和 �, �!,# = 2��$%% �,� , 其中� = � � . 证明(cont’d)： � ℎ∗,# − ℎ∗,$ = �! �" ⋮ �# − 2� − �! − 2� �" ⋮ �# = 2� 0 ⋮ −2� 因此 & '∗,&('∗,' )* = �!,#。回顾�� = �$#，有解，且解空间是一维的 令� = &∗,#'&∗,$ () ，有 �*++ �,� = � � − � � = ℎ$,# − ℎ$,$ 2� − ℎ#,# − ℎ#,$ 2� = ℎ!,# + ℎ#,! 2� = �$,# 2� 6