Characteristic polynomial of a graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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


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