Characteristic polynomial of a graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Characteristic polynomial of a graph''' --- характеристический полином графа. Given a graph <math>G</math>, the polynomial <math>p…»)
 
Нет описания правки
 
Строка 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.

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

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.