Combinatorial Laplacian

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

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

[math]\displaystyle{ \,\Delta_{G}f(x) = f(x) - \frac{1}{m_{G}(x)} \sum_{y \sim_{G}x} f(y) }[/math]

for any [math]\displaystyle{ \,f \in L^{2}(G) }[/math], [math]\displaystyle{ \,x \in V(G) }[/math]. Here [math]\displaystyle{ \,m_{G}(x) }[/math] is the degree of a vertex [math]\displaystyle{ \,x \in V(G) }[/math] and we write [math]\displaystyle{ \,y \sim_{G}x }[/math] if the vertices [math]\displaystyle{ \,y }[/math] and [math]\displaystyle{ \,x }[/math] are adjacent in [math]\displaystyle{ \,G }[/math]. Inasmuch as [math]\displaystyle{ \,G }[/math] is a discrete analogue of a Riemannian manifold, [math]\displaystyle{ \,\Delta_{G} }[/math] 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.