Combinatorial Laplacian

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.