Adjacency matrix
From Wikipedia, the free encyclopedia
|
In Architecture and Interior Design, an Adjacency Matrix is used as a graphic representation of desired space relationships. In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry Failed to parse (Missing texvc executable; please see math/README to configure.): a_{ij}
is the number of edges from vertex i to vertex j, and the diagonal entry Failed to parse (Missing texvc executable; please see math/README to configure.): a_{ii}
is either twice the number of loops at vertex i or just the number of loops (usages differ, depending on the mathematical needs; this article follows the former convention for undirected graphs, though directed graphs always follow the latter). There exists a unique adjacency matrix for each graph (up to permuting rows and columns), and it is not the adjacency matrix of any other graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected, the adjacency matrix is symmetric.
Another matrix representation for a graph is the incidence matrix. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.
Examples
where J is an r × s matrix of all ones and O denotes an all-zero matrix. PropertiesThe adjacency matrix of an undirected graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. Suppose two directed or undirected graphs Failed to parse (Missing texvc executable; please see math/README to configure.): G_1 and Failed to parse (Missing texvc executable; please see math/README to configure.): G_2 with adjacency matrices Failed to parse (Missing texvc executable; please see math/README to configure.): A_1 and Failed to parse (Missing texvc executable; please see math/README to configure.): A_2 are given. Failed to parse (Missing texvc executable; please see math/README to configure.): G_1 and Failed to parse (Missing texvc executable; please see math/README to configure.): G_2 are isomorphic if and only if there exists a permutation matrix Failed to parse (Missing texvc executable; please see math/README to configure.): P such that
. In particular, Failed to parse (Missing texvc executable; please see math/README to configure.): A_1 and Failed to parse (Missing texvc executable; please see math/README to configure.): A_2 are similar and therefore have the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic (one cannot 'hear' the shape of a graph). If A is the adjacency matrix of the directed or undirected graph G, then the matrix An (i.e., the matrix product of n copies of A) has an interesting interpretation: the entry in row i and column j gives the number of (directed or undirected) paths of length n from vertex i to vertex j. The matrix I − A (where I denotes the n × n identity matrix) is invertible if and only if there are no directed cycles in the graph G. In this case, the inverse Failed to parse (Missing texvc executable; please see math/README to configure.): (I - A)^{-1} has the following interpretation: the entry in row i and column j gives the number of directed paths from vertex i to vertex j (which is always finite if there are no directed cycles). This can be understood using the geometric series for matrices:
corresponding to the fact that the number of paths from i to j equals the number of paths of length 0 plus the number of paths of length 1 plus the number of paths of length 2, etc. The main diagonal of every adjacency matrix corresponding to a graph without loops has all zero entries. For Failed to parse (Missing texvc executable; please see math/README to configure.): \left( d \right) -regular graphs, d is also an eigenvalue of A, for the vector Failed to parse (Missing texvc executable; please see math/README to configure.): v=\left( 1,...,1 \right) , and Failed to parse (Missing texvc executable; please see math/README to configure.): G is connected iff the multiplicity of Failed to parse (Missing texvc executable; please see math/README to configure.): d is 1. It can be shown that Failed to parse (Missing texvc executable; please see math/README to configure.): -d is also an eigenvalue of A iff G is connected bipartite graph. The above are results of Perron–Frobenius theorem. VariationsThe Seidel adjacency matrix or (0,−1,1)-adjacency matrix of a simple graph has zero on the diagonal and entry Failed to parse (Missing texvc executable; please see math/README to configure.): a_{ij} = -1 if ij is an edge and +1 if it is not. This matrix is used in studying strongly regular graphs and two-graphs. A distance matrix is like a higher-level adjacency matrix. Instead of only providing information about whether or not two vertices are connected, also tells the distances between them. This assumes the length of every edge is 1. A variation is where the length of an edge is not necessarily 1. Data structuresWhen used as a data structure, the main competitor for the adjacency matrix is the adjacency list. Because each entry in the adjacency matrix requires only one bit, they can be represented in a very compact way, occupying only Failed to parse (Missing texvc executable; please see math/README to configure.): {n^2} / 8 bytes of contiguous space, where Failed to parse (Missing texvc executable; please see math/README to configure.): n is the number of vertices. Besides just avoiding wasted space, this compactness encourages locality of reference. On the other hand, for a sparse graph, adjacency lists win out, because they do not use any space to represent edges which are not present. Using a naive array implementation on a 32-bit computer, an adjacency list for an undirected graph requires about Failed to parse (Missing texvc executable; please see math/README to configure.): 8 e bytes of storage, where Failed to parse (Missing texvc executable; please see math/README to configure.): e is the number of edges. Noting that a simple graph can have at most Failed to parse (Missing texvc executable; please see math/README to configure.): n^2 edges, allowing loops, we can let Failed to parse (Missing texvc executable; please see math/README to configure.): d = e / n^2 denote the density of the graph. Then, Failed to parse (Missing texvc executable; please see math/README to configure.): 8 e > n^2 / 8 , or the adjacency list representation occupies more space, precisely when Failed to parse (Missing texvc executable; please see math/README to configure.): d > 1/64 . Thus a graph must be sparse indeed to justify an adjacency list representation. Besides the space tradeoff, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes O(n) time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list. References
External links
es:Matriz de adyacencia fr:Matrice d'adjacence it:Matrice delle adiacenze nl:Bogenmatrix ja:隣接行列 pl:Macierz sąsiedztwa pt:Matriz de adjacência vi:Ma trận kề |
