图的拉普拉斯矩阵

《图的拉普拉斯矩阵》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内容来自wikipedia链接为http://en.wikipedia.org/wiki/Laplacian_matrix图的拉普拉斯矩阵1.Inthe mathematical fieldof graphtheory,the Laplacianmatrix,sometimescalled admittancematrix, Kirchhoffmatrix or discreteLaplacian,isa matrixrepresentationofa graph.Togetherwith Kirchhoff'stheor

2、em,itcanbeusedtocalculatethenumberof spanningtrees foragivengraph.TheLaplacianmatrixcanbeusedtofindmanyotherpropertiesofthegraph. Cheeger'sinequality from Riemanniangeometry hasadiscreteanalogueinvolvingtheLaplacianmatrix;thisisperhapsthemostimportanttheoremin spe

3、ctralgraphtheory andoneofthemostusefulfactsinalgorithmicapplications.ItapproximatesthesparsestcutofagraphthroughthesecondeigenvalueofitsLaplacian.2.定义Givena simplegraph G with n vertices,itsLaplacianmatrix isdefinedas:，where D isthe degreematrix and A isthe adjace

4、ncymatrix ofthegraph.Inthecaseof directedgraphs,eitherthe indegreeoroutdegree mightbeused,dependingontheapplication.Theelementsof  aregivenbywheredeg(vi)isdegreeofthevertex i.The symmetricnormalizedLaplacianmatrix isdefinedas:Theelementsof  aregivenbyThe random-wa

5、lknormalizedLaplacianmatrix isdefinedas:Theelementsof  aregivenby2.例子HereisasimpleexampleofalabeledgraphanditsLaplacianmatrix.LabeledgraphDegreematrixAdjacencymatrixLaplacianmatrix2.性质Foran(undirected)graph G anditsLaplacianmatrix L with eigenvalues·L issymmetric.

6、·L is positive-semidefinite (thatis forall i).Thisisverifiedinthe incidencematrix section(below).ThiscanalsobeseenfromthefactthattheLaplacianissymmetricand diagonallydominant.·L isan M-matrix (itsoff-diagonalentriesarenonpositive,yettherealpartsofitseigenvaluesare

7、nonnegative).·Everyrowsumandcolumnsumof L iszero.Indeed,inthesum,thedegreeofthevertexissummedwitha"-1"foreachneighbor·Inconsequenc,becausethevector  satisfies ·Thenumberoftimes0appearsasaneigenvalueintheLaplacianisthenumberof connectedcomponents inthegraph.·Thesma

8、llestnon-zeroeigenvalueof L iscalledthe spectralgap.·Thesecondsmallesteigenvalueof L isthe algebraicconnectivity (or Fiedlervalue)of G.·WhenGisk-regular