Combinatorial Laplacian

Материал из WikiGrapp
Перейти к:навигация, поиск

Combinatorial Laplacianкомбинаторный лапласиан.

Let \,G = (V,E) be a locally finite graph without isolated vertices. Let \,L^{2}(G) be the space of all \,R-valued functions on \,V(G). The combinatorial Laplacian \,\Delta_{G}: \; L^{2}(G) \rightarrow L^{2}(G) of \,G is given by

\,\Delta_{G}f(x) = f(x) - \frac{1}{m_{G}(x)} \sum_{y \sim_{G}x} f(y)

for any \,f \in L^{2}(G), \,x \in V(G). Here \,m_{G}(x) is the degree of a vertex \,x \in V(G) and we write \,y \sim_{G}x if the vertices \,y and \,x are adjacent in \,G. Inasmuch as \,G is a discrete analogue of a Riemannian manifold, \,\Delta_{G} is a discrete analogue of the ordinary Laplace—Beltrami operator in Riemannian geometry. This analogy has been widely exploited both in the development of a harmonic analysis on graphs and within the spectral geometry of graphs.


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.