Characteristic polynomial of a graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Characteristic polynomial of a graph''' --- характеристический полином графа. Given a graph <math>G</math>, the polynomial <math>p…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Characteristic polynomial of a graph''' | '''Characteristic polynomial of a graph''' — [[характеристический полином графа]]. | ||
Given a graph <math>G</math>, the polynomial <math>p_{G}(\lambda) = \det(\lambda I - | Given a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G</math>, the polynomial <math>\,p_{G}(\lambda) = \det(\lambda I - | ||
A_{G})</math>, where <math>A_{G}</math> is the ''adjacency matrix'' of <math>G</math>. This | A_{G})</math>, where <math>\,A_{G}</math> is the ''[[adjacency matrix]]'' of <math>\,G</math>. This | ||
clearly does not depend on the labeling of vertices. The roots of the | clearly does not depend on the labeling of [[vertex|vertices]]. The [[root|roots]] of the | ||
characteristic polynomial, i.e. the eigenvalues of <math>A_{G}</math>, are called | characteristic polynomial, i.e. the eigenvalues of <math>\,A_{G}</math>, are called | ||
the '''eigenvalues''' of the graph <math>G</math>. The ''' spectrum''' of <math>G</math> is | the [[eigenvalue of a graph|'''eigenvalues''' of the graph]] <math>\,G</math>. The '''[[spectrum of a graph|spectrum]]''' of <math>\,G</math> is | ||
the set of solutions to <math>p(\lambda) = 0</math> denoted by <math>S_{p} = | the set of solutions to <math>\,p(\lambda) = 0</math> denoted by <math>S_{p} = | ||
\{\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\}</math> with <math>\lambda_{1} | \{\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}\}</math> with <math>\lambda_{1} | ||
\geq \lambda_{2} \geq \ldots, \lambda_{n}</math>. The first eigenvalue | \geq \lambda_{2} \geq \ldots, \lambda_{n}</math>. The first eigenvalue | ||
<math>\lambda_{1}</math> is called the '''index''' or '''spectral radius'''. | <math>\,\lambda_{1}</math> is called the '''[[index]]''' or '''[[spectral radius]]'''. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 11:57, 9 ноября 2012
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.