Characteristic polynomial of a graph

Материал из WikiGrapp
Версия от 11:57, 9 ноября 2012; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Characteristic polynomial of a graphхарактеристический полином графа.

Given a graph [math]\displaystyle{ \,G }[/math], the polynomial [math]\displaystyle{ \,p_{G}(\lambda) = \det(\lambda I - A_{G}) }[/math], where [math]\displaystyle{ \,A_{G} }[/math] is the adjacency matrix of [math]\displaystyle{ \,G }[/math]. This clearly does not depend on the labeling of vertices. The roots of the characteristic polynomial, i.e. the eigenvalues of [math]\displaystyle{ \,A_{G} }[/math], are called the eigenvalues of the graph [math]\displaystyle{ \,G }[/math]. The spectrum of [math]\displaystyle{ \,G }[/math] is the set of solutions to [math]\displaystyle{ \,p(\lambda) = 0 }[/math] denoted by [math]\displaystyle{ S_{p} = \{\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\} }[/math] with [math]\displaystyle{ \lambda_{1} \geq \lambda_{2} \geq \ldots, \lambda_{n} }[/math]. The first eigenvalue [math]\displaystyle{ \,\lambda_{1} }[/math] is called the index or spectral radius.

Литература

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