Algebraic graph theory: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Algebraic graph theory''' --- алгебраическая теория графов. '''Algebraic graph theory''' can be considered ...)
 
Нет описания правки
 
Строка 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
asso\-ci\-ated with graphs are employed to deduce some of their
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.