Algebraic graph theory: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Algebraic graph theory''' --- алгебраическая теория графов. '''Algebraic graph theory''' can be considered ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Algebraic graph theory''' | '''Algebraic graph theory''' — ''[[алгебраическая теория графов]].'' | ||
'''Algebraic graph theory''' can be considered as a branch of the graph | '''Algebraic graph theory''' can be considered as a branch of the graph | ||
theory, where ''eigenvalues'' and eigenvectors of certain matrices | theory, where ''[[eigenvalue of a graph|eigenvalues]]'' and eigenvectors of certain matrices | ||
associated with [[graph, undirected graph, nonoriented graph|graphs]] are employed to deduce some of their | |||
properties. In fact, eigenvalues are closely related to almost all | properties. In fact, eigenvalues are closely related to almost all | ||
major invariants of a graph, linking one extremal property to another. | major invariants of a graph, linking one extremal property to another. | ||
Текущая версия от 16:55, 22 ноября 2011
Algebraic graph theory — алгебраическая теория графов.
Algebraic graph theory can be considered as a branch of the graph theory, where eigenvalues and eigenvectors of certain matrices associated with graphs are employed to deduce some of their properties. In fact, eigenvalues are closely related to almost all major invariants of a graph, linking one extremal property to another. These eigenvalues play a central role in our fundamental understanding of graphs. Many interesting books on the algebraic graph theory can be found, such as Biggs (1993), Cvetkovic et al. (1980), Seidel (1989), and Chung (1997).
One of the major contributions to the algebraic graph theory is due to Fiedler, where the properties of the second eigenvalue and eigenvector of the Laplacian of a graph have been introduced. This eigenvector, known as the Fiedler vector, is used in graph partitioning and nodal ordering.