4634
правки
Characteristic polynomial of a graph: различия между версиями
Перейти к навигации
Перейти к поиску
Characteristic polynomial of a graph (посмотреть исходный код)
Версия от 11:57, 9 ноября 2012
, 9 ноября 2012нет описания правки
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. | |||