Spectrum of a graph

Материал из WikiGrapp
Версия от 18:13, 23 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Spectrum of a graph''' --- спектр графа. Given a graph <math>G</math>, the ''' pectrum of the graph''' <math>G</math> is the spectrum (collection of …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Spectrum of a graph --- спектр графа.

Given a graph [math]\displaystyle{ G }[/math], the pectrum of the graph [math]\displaystyle{ G }[/math] is the spectrum (collection of eigenvalues) of the adjacency matrix [math]\displaystyle{ A_{g} }[/math] of [math]\displaystyle{ G }[/math]. Since [math]\displaystyle{ A_{G} }[/math] is symmetric, the eigenvalues of [math]\displaystyle{ G }[/math] (the elements of its spectrum) are real.

For an infinite digraph, a complex number [math]\displaystyle{ \lambda }[/math] is a spectrum of an operator [math]\displaystyle{ A }[/math], if [math]\displaystyle{ A - \lambda }[/math] has no bounded inverse, and the set [math]\displaystyle{ \sigma(A) }[/math] of all spectra of [math]\displaystyle{ A }[/math] is called the spectrum of [math]\displaystyle{ A }[/math]. In particular, [math]\displaystyle{ \pi_{0}(A) }[/math] denotes the point spectrum, that is, the set of all proper values of [math]\displaystyle{ A }[/math]. If there is a sequence [math]\displaystyle{ \{x_{n}\} }[/math] of unit vectors in a Hilbert space [math]\displaystyle{ {\mathcal H} }[/math] with [math]\displaystyle{ \|(T - \lambda)^{\ast}x_{n}\| \rightarrow 0 }[/math], then [math]\displaystyle{ \lambda }[/math] is called an approximate proper value, and all approximate proper values form the approximate point spectrum [math]\displaystyle{ \pi(A) }[/math]. If [math]\displaystyle{ \|(T - \lambda)x_{n}\| \rightarrow 0 }[/math] and [math]\displaystyle{ \|(T - \lambda)^{\ast}x_{n}\| \rightarrow 0 }[/math] for some unit vectors [math]\displaystyle{ \{x_{n}\} }[/math], then [math]\displaystyle{ \lambda }[/math] is called a normal approximate spectrum of [math]\displaystyle{ A }[/math], all of which form the normal approximate (point) spectrum [math]\displaystyle{ \pi_{n}(A) }[/math]. Obviously we have

[math]\displaystyle{ \pi_{n}(A) \subseteq \pi(A) \subseteq \sigma(A). }[/math]

For a directed graph [math]\displaystyle{ G }[/math], the spectrum [math]\displaystyle{ \sigma(G) }[/math], the point spectrum [math]\displaystyle{ \pi_{0}(G) }[/math], the approximate point spectrum [math]\displaystyle{ \pi(G) }[/math] and the normal approximate (point) spectrum [math]\displaystyle{ \pi_{n}(G) }[/math] are defined by

[math]\displaystyle{ \sigma(G) = \sigma(A(G)), \; \pi_{0}(G) = \pi_{0}(A(G)), \; \pi(G) = \pi(A(G)) }[/math] and [math]\displaystyle{ \pi_{n}(G) = \pi_{n}(A(G)). }[/math]