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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Combinatorial Laplacian''' --- комбинаторный лапласиан. Let <math>G = (V,E)</math> be a locally finite graph without isolated vertices. Le…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Combinatorial Laplacian''' --- комбинаторный лапласиан.  
'''Combinatorial Laplacian''' — ''[[комбинаторный лапласиан]].''


Let <math>G = (V,E)</math> be a locally finite graph without isolated vertices.
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
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
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>
<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
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.
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.

Текущая версия от 10:46, 24 октября 2018

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.