随机算法 (Fall 2011)/Graph Spectrum
The adjacency matrix of an -vertex graph , denoted , is an matrix where is the number of edges in between vertex and vertex . Because is a symmetric matrix with real entries, due to the Perron-Frobenius theorem, it has real eigenvalues , which associate with an orthonormal system of eigenvectors with . We call the eigenvalues of the spectrum of the graph .
The spectrum of a graph contains a lot of information about the graph. For example, supposed that is -regular, the following lemma holds.
- for all .
- and the corresponding eigenvector is .
- is connected if and only if .
- If is bipartite then .
Proof. Let be the adjacency matrix of , with entries . It is obvious that for any .
- (1) Suppose that , and let be an entry of with the largest absolute value. Since , we have
- and so
- Thus .
- (2) is easy to check.
- (3) Let be the nonzero vector for which , and let be an entry of with the largest absolute value. Since , we have
- Since and by the maximality of , it follows that for all that . Thus, if and are adjacent, which implies that if and are connected. For connected , all vertices are connected, thus all are equal. This shows that if is connected, the eigenvalue has multiplicity 1, thus .
- If otherwise, is disconnected, then for two different components, we have and , where the entries of and are nonzero only for the vertices in their components components. Then . Thus, the multiplicity of is greater than 1, so .
- (4) If if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets and such that all edges have one endpoint in each of and . Algebraically, this means that the adjacency matrix can be organized into the form
- where is a permutation matrix, which has no change on the eigenvalues.
- If is an eigenvector corresponding to the eigenvalue , then which is obtained from by changing the sign of the entries corresponding to vertices in , is an eigenvector corresponding to the eigenvalue . It follows that the spectrum of a bipartite graph is symmetric with respect to 0.