d-regular graphs(d-正则图) 对于d-正则图，有W=A=1-L,记w的特征值为a1≥a2≥…之an，正交正归化的特征向量为，v2,,n 要研究p:=Wpo,可以把po=c1y1+…+cnn展开 那么W'po=c1aD1+c2a吃v2+…+Cna克n W=A=1-L的特征空间： ·12a1,am≥-1 1=a1,对应的特征向量为1 a1>2当且仅当图是连通的 a41=-an当且仅当图是二分图（课后练习） 可见连通性，和非二分图的性质，分别对应于a2<1和an>一1 这意味着，对连通的非二分图，Wpo→c11ast→∞ 如果a2<1-e,并且am>-1+e,则e越大，收敛越快 Fundamental Theorem of Markov chain, for undirected graph! C1V1是什么？ 对于d-正则图，元=豆=为特征值为1对应的特征向量，因此，=1a=。.)=六po)=言 2m n 因此c==元 89 Fundamental Theorem of Markov chain, for undirected graph!