Combinatorial Laplacian: различия между версиями

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

Let <math>\,G = (V,E)</math> be a [[locally finite graph]] without [[isolated vertex|isolated vertices]].

Let <math>\,L^{2}(G)</math> be the space of all <math>\,R</math>-valued functions on <math>\,V(G)</math>. The '''combinatorial Laplacian''' <math>\,\Delta_{G}: \; L^{2}(G) \rightarrow L^{2}(G)</math> of <math>\,G</math> is given by

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

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

 

 

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