图的拉普拉斯矩阵

内容来自wikipedia链接为图的拉普拉斯矩阵1.Inthemathematicalfieldofgraphtheory,theLaplacianmatrix,sometimescalledadmittancematrix,KirchhoffmatrixordiscreteLaplacian,isamatrixrepresentationofagraph.TogetherwithKirchhoff'stheorem,itcanbeusedtocalculatethenumberofspanningtreesforagivengraph.TheLaplacianmatrixcanbeusedtofindmanyotherpropertiesofthegraph.Cheeger'sinequalityfromRiemanniangeometryhasadiscreteanalogueinvolvingtheLaplacianmatrix;thisisperhapsthemostimportanttheoreminspectralgraphtheoryandoneofthemostusefulfactsinalgorithmicapplications.ItapproximatesthesparsestcutofagraphthroughthesecondeigenvalueofitsLaplacian.2.定义GivenasimplegraphGwithnvertices,itsLaplacianmatrixnnLisdefinedas:ADL，whereDisthedegreematrixandAistheadjacencymatrixofthegraph.Inthecaseofdirectedgraphs,eithertheindegreeoroutdegreemightbeused,dependingontheapplication.TheelementsofLaregivenbywheredeg(vi)isdegreeofthevertexi.ThesymmetricnormalizedLaplacianmatrixisdefinedas:TheelementsofaregivenbyTherandom-walknormalizedLaplacianmatrixisdefinedas:Theelementsofaregivenby3.例子HereisasimpleexampleofalabeledgraphanditsLaplacianmatrix.LabeledgraphDegreematrixAdjacencymatrixLaplacianmatrix4.性质Foran(undirected)graphGanditsLaplacianmatrixLwitheigenvaluesLissymmetric.Lispositive-semidefinite(thatisforalli).Thisisverifiedintheincidencematrixsection(below).ThiscanalsobeseenfromthefactthattheLaplacianissymmetricanddiagonallydominant.LisanM-matrix(itsoff-diagonalentriesarenonpositive,yettherealpartsofitseigenvaluesarenonnegative).EveryrowsumandcolumnsumofLiszero.Indeed,inthesum,thedegreeofthevertexissummedwitha-1foreachneighborInconsequenc,becausethevectorsatisfiesThenumberoftimes0appearsasaneigenvalueintheLaplacianisthenumberofconnectedcomponentsinthegraph.Thesmallestnon-zeroeigenvalueofLiscalledthespectralgap.ThesecondsmallesteigenvalueofListhealgebraicconnectivity(orFiedlervalue)ofG.WhenGisk-regular,thenormalizedLaplacianis:,whereAistheadjacencymatrixandIisanidentitymatrix.5.L关联矩阵Definean||||veorientedincidencematrixMwithelementMevforedgee(connectingvertexiandj,withij)andvertexvgivenbyThentheLaplacianmatrixLsatisfieswhereisthematrixtransposeofMNowconsideraneigendecompositionofL,withunit-normeigenvectorsivandcorrespondingeigenvaluesiBecauseicanbewrittenastheinnerproductofthevectoriMvwithitself,thisshowsthatandsotheeigenvaluesofLareallnon-negative6.变形的拉普拉斯ThedeformedLaplacianiscommonlydefinedaswhereIistheunitmatrix,Aistheadjacencymatrix,andDisthedegreematrix,andsisa(complex-valued)number.NotethatthestandardLaplacianisjust.7.对称的正规拉普拉斯矩阵The(symmetric)normalizedLaplacianisdefinedaswhereListhe(unnormalized)Laplacian,AistheadjacencymatrixandDisthedegreematrix.SincethedegreematrixDisdiagonalandpositive,itsreciprocalsquareroot2/1DisjustthediagonalmatrixwhosediagonalentriesarethereciprocalsofthepositivesquarerootsofthediagonalentriesofD.ThesymmetricnormalizedLaplacianisasymmetricmatrix.Onehas:whereSisthematrixwhoserowsareindexedbytheverticesandwhosecolumnsareindexedbytheedgesofGsuchthateachcolumncorrespondingtoanedgee={u,v}hasanentry，intherowcorrespondingtou,anentry.intherowcorrespondingtov,andhas0entrieselsewhere.(Note:denotesthetransposeofS).AlleigenvaluesofthenormalizedLaplacianarerealandnon-negative.Wecanseethisasfollows.Sinceissymmetric,itseigenvaluesarereal.Theyarealsonon-negative:consideraneigenvectorgofwitheigenvalueλandsuppose.(Wecanconsidergandfasrealfunctionsontheverticesv.)Then:whereweusetheinnerproductasumoverallverticesv,anddenotesthesumoverallunorderedpairsofadjacentvertices{u,v}.ThequantityiscalledtheDirichletsumoff,whereastheexpressioniscalledtheRayleighquotientofg.Let1bethefunctionwhichassumesthevalue1oneachvertex.Thenisaneigenfunctionofwitheigenvalue0.Infact,theeigenvaluesofthenormalizedsymmetricLaplaciansatisfy0=μ0≤...≤μn-1≤2.Theseeigenvalues(knownasthespectrumofthenormalizedLaplacian)relatewelltoothergraphinvariantsforgeneralgraphs.[4]7.解释离散拉普拉斯算子TheLaplacianmatrixcanbeinterpretedasamatrixrepresentationofaparticularcaseofthediscreteLaplaceoperator.Suchaninterpretationallowsone,e.g.,togeneralisetheLaplacianmatrixtothecaseofgraphswithaninfinitenumberofverticesandedges,leadingtoaLaplacianmatrixofaninfinitesize.Toexpanduponthis,wecandescribethechangeofsomeelement(withsomeconstantk)asInmatrix-vectornotation,whichgivesNoticethatthisequationtakesthesameformastheheatequation,wherethematrixLisreplacingtheLaplacianoperator;hence,thegraphLaplacian.Tofindasolutiontothisdifferentialequation,applystandardtechniquesforsolvingafirst-ordermatrixdifferentialequation.Thatis,writeasalinearcombinationofeigenvectorsofL(sothat),withtime-dependentPluggingintotheoriginalexpression(notethatwewillusethefactthatbecauseLisasymmetricmatrix,itsunit-normeigenvectorsareorthogonal):whosesolutionisAsshownbefore,theeigenvaluesofLarenon-negative,showingthatthesolutiontothediffusionequationapproachesanequilibrium,becauseitonlyexponentiallydecaysorremainsconstant.Thisalsoshowsthatgivenandtheinitialcondition,thesolutionatanytimetcanbe