Review of Spectral Graph Theory
ACM SIGACT News · 1999-06 · 30 (2) · 14-16
DOI: 10.1145/568547.568553 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGACT News, 1999-06. Verfasst von Jacob Lurie. Die Arbeit wurde bisher 37-mal zitiert (Crossref).
Abstract (Originalsprache)
Specifying a graph is equivalent to specifying its adjacency relation, which may be encoded in the form of a matrix. This suggests that study of the adjacency matrix from a linear-algebraic point of view might yield valuable information about graphs. In particular, any invariant associated to the matrix is also an invariant associated to the graph, and might have combinatorial meaning. Spectral graph theory is the study of the relationship between a graph and the eigenvalues of matrices (such as the adjacency matrix) naturally associated to that graph. This book looks at the subject from a geometric point of view, exploiting an analogy between a graph and a Riemannian manifold: Chung defines the Laplacian of a graph, a matrix closely related to the adjacency matrix, in analogy with the continuous case and studies the eigenvalues of this Laplacian.There are several reasons that these eigenvalues may be of interest. On the purely mathematical level, the eigenvalues have the advantage of being an extremely natural invariant which behaves nicely under operations such as Cartesian product and disjoint union. From a combinatorial point of view, the eigenvalues of a graph are related to many other more "discrete" invariants. From a geometric point of view, there are many respects in which the eigenvalues of a graph behave like the spectrum of a compact Riemannian manfiold. For the computationally-minded, the eigenvalues of a graph are easy to compute, and their relationship to other invariants can often yields good approximations to less tractible computations.
Zitieren
APA
Lurie, J. (1999). Review of Spectral Graph Theory. ACM SIGACT News, 30(2), 14-16. https://doi.org/10.1145/568547.568553
Vancouver
Lurie J. Review of Spectral Graph Theory. ACM SIGACT News. 1999;30(2):14-16. doi:10.1145/568547.568553
BibTeX
@article{Lurie1999,
author = {Lurie, Jacob},
title = {Review of Spectral Graph Theory},
journal = {ACM SIGACT News},
year = {1999},
volume = {30},
number = {2},
pages = {14--16},
doi = {10.1145/568547.568553}
}
EUVIMED