In mathematics and computer science, the adjacency matrix for a finite graph_(mathematics) on ''n'' vertices is an ''n'' × ''n'' matrix_(mathematics) where the nondiagonal entry ''a''''ij'' is the number of edges joining vertex and vertex , and the diagonal entry ''a''''ii'' is twice the number of loops at vertex . There exists a unique adjacency matrix for each graph, 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 matrix. For sparse graphs, that is graphs with few edges, an adjacency list is often the preferred representation because it uses less space. An alternative matrix representation for a graph is the incidence matrix. The relationship between a graph and its adjacency matrix is studied in spectral graph theory. == Examples == The adjacency matrix for the following vertex labeled graph : is : == Properties == The adjacency matrix of an undirected graph is symmetric matrix, and therefore has a complete set of eigenvalues and orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. Suppose two directed or undirected graphs ''G''1 and ''G''2 with adjacency matrices ''A''1 and ''A''2 are given. ''G''1 and ''G''2 are graph isomorphism if and only if there exists a permutation matrix ''P'' such that :''PA''1''P'' −1 = ''A''2. In particular, ''A''1 and ''A''2 are similar and have therefore the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace (matrix). These can therefore serve as isomorphism invariants of graphs. Given the two adjacency matrices, it is possible to reconstruct the permutation matrix used: see Permutation matrix#Solving for P for details. Note, however, that the converse is not true: two graphs may possess the same set of eigenvalues but not be isomorphic (one cannot 'hear' the shape of a graph). The multiplication with the permutation matrix can be visualized as a relabeling of the vertices. If ''A'' is the adjacency matrix of the directed or undirected graph ''G'', then the matrix ''A''''n'' (i.e. the matrix multiplication 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''-by-''n'' identity matrix) is invertible matrix if and only if there are no directed cycles in the graph ''G''. In this case, the inverse (''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: :(''I'' − ''A'')−1 = ''I'' + ''A'' + ''A''2 + ''A''3 + ... 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. == Trade-offs as a data structure == When 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 ''n''2/8 bytes of contiguous space, where ''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 linked list implementation on a 32-bit computer, an adjacency list for an undirected graph requires about 16''e'' bytes of storage, where ''e'' is the number of edges. Noting that a simple graph can have at most ''n''2 edges, allowing loops, we can let ''d'' = ''e''/''n''2 denote the ''density'' of the graph. Then, 16''e'' > ''n''2/8, or the adjacency list representation occupies more space, precisely when ''d'' > 1/128. 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 Big O notation(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. Linear algebra Graph theory Matrices
I removed ''The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.'' from the article. The edges in graphs are defined as a set, so it is not possible that an edge (''v''''i'',''v''''j'') is contained more than once. I think the adjacency matrix should be a (0,1)-matrix and perhaps in a subsection someone could extend this definition to count the number of edges two vertices share.User:MathMartin 18:56, 25 Sep 2004 (UTC) :This is correct, although multigraphs have a multiset of edges. User:Dcoetzee 00:25, 2 Oct 2004 (UTC) Maybe the example graph can contain a self loop, to show how it can be represented into the adjacency matrix. :That's a great idea. User:Dcoetzee 01:39, 21 Mar 2005 (UTC) Most software packages show a binary adjacency matrix, even on the diagonal. But loops are always counted twice, and some books show an adjacency matrix like this one, with 2 on the diagonal...
See other meanings of words starting from letter:
Words begining with Adjacency_matrix:
Adjacency-matrix_representation
Adjacency_matrix
Adjacency_matrix
Adjacency matrix
In mathematics and computer science, the adjacency matrix for a finite graph_(mathematics) on ''n'' vertices is an ''n'' × ''n'' matrix_(mathematics) where the nondiagonal entry ''a''''ij'' is the number of edges joining vertex and vertex , and the diagonal entry ''a''''ii'' is twice the number of loops at vertex . There exists a unique adjacency matrix for each graph, 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 matrix. For sparse graphs, that is graphs with few edges, an adjacency list is often the preferred representation because it uses less space. An alternative matrix representation for a graph is the incidence matrix. The relationship between a graph and its adjacency matrix is studied in spectral graph theory. == Examples == The adjacency matrix for the following vertex labeled graph : is : == Properties == The adjacency matrix of an undirected graph is symmetric matrix, and therefore has a complete set of eigenvalues and orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. Suppose two directed or undirected graphs ''G''1 and ''G''2 with adjacency matrices ''A''1 and ''A''2 are given. ''G''1 and ''G''2 are graph isomorphism if and only if there exists a permutation matrix ''P'' such that :''PA''1''P'' −1 = ''A''2. In particular, ''A''1 and ''A''2 are similar and have therefore the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace (matrix). These can therefore serve as isomorphism invariants of graphs. Given the two adjacency matrices, it is possible to reconstruct the permutation matrix used: see Permutation matrix#Solving for P for details. Note, however, that the converse is not true: two graphs may possess the same set of eigenvalues but not be isomorphic (one cannot 'hear' the shape of a graph). The multiplication with the permutation matrix can be visualized as a relabeling of the vertices. If ''A'' is the adjacency matrix of the directed or undirected graph ''G'', then the matrix ''A''''n'' (i.e. the matrix multiplication 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''-by-''n'' identity matrix) is invertible matrix if and only if there are no directed cycles in the graph ''G''. In this case, the inverse (''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: :(''I'' − ''A'')−1 = ''I'' + ''A'' + ''A''2 + ''A''3 + ... 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. == Trade-offs as a data structure == When 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 ''n''2/8 bytes of contiguous space, where ''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 linked list implementation on a 32-bit computer, an adjacency list for an undirected graph requires about 16''e'' bytes of storage, where ''e'' is the number of edges. Noting that a simple graph can have at most ''n''2 edges, allowing loops, we can let ''d'' = ''e''/''n''2 denote the ''density'' of the graph. Then, 16''e'' > ''n''2/8, or the adjacency list representation occupies more space, precisely when ''d'' > 1/128. 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 Big O notation(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. Linear algebra Graph theory Matrices
Adjacency matrix
I removed ''The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.'' from the article. The edges in graphs are defined as a set, so it is not possible that an edge (''v''''i'',''v''''j'') is contained more than once. I think the adjacency matrix should be a (0,1)-matrix and perhaps in a subsection someone could extend this definition to count the number of edges two vertices share.User:MathMartin 18:56, 25 Sep 2004 (UTC) :This is correct, although multigraphs have a multiset of edges. User:Dcoetzee 00:25, 2 Oct 2004 (UTC) Maybe the example graph can contain a self loop, to show how it can be represented into the adjacency matrix. :That's a great idea. User:Dcoetzee 01:39, 21 Mar 2005 (UTC) Most software packages show a binary adjacency matrix, even on the diagonal. But loops are always counted twice, and some books show an adjacency matrix like this one, with 2 on the diagonal...
See other meanings of words starting from letter:
A
AB | AC | AD | AE | AF | AG | AH | AI | AJ | AK | AL | AM | AN | AO | AP | AR | AS | AT | AU | AW | AX | AY | AZ |Words begining with Adjacency_matrix:
Adjacency-matrix_representation
Adjacency_matrix
Adjacency_matrix
Sponsored links: praca.
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
