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.