# 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.

## Литература

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