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 a_{ij} is the number of edges from vertex i to vertex j, and the diagonal entry 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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ...
In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...
This article just presents the basic definitions. ...
(Redirected from (0,1) matrix) A binary matrix or (0,1)matrix is a matrix whose entries are all either zero or one. ...
In linear algebra, a symmetric matrix is a matrix that is its own transpose. ...
For sparse graphs, that is, graphs with few edges, an adjacency list is often preferred as a representation of the graph because it uses less space. In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
Another matrix representation for a graph is the incidence matrix. In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. ...
The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory. In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...
In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are nonzero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. ...
Examples
 Here is a simple example of a labeled graph and its adjacency matrix. The convention followed here is that a loop counts 1 in the matrix.
 The adjacency matrix of a complete graph is all 1's except for 0's on the diagonal.
 The adjacency matrix of a complete bipartitite graph K_{r,s} has the form
where J is an r × s matrix of all ones and O denotes an allzero matrix. In graph theory (which is an area in mathematics and computer science) a labeled graph is a graph with labels assigned to its nodes and edges. ...
Image File history File links 6ngraph2. ...
In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...
Properties The 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. In linear algebra, a symmetric matrix is a matrix that is its own transpose. ...
In mathematics, the real numbers may be described informally in several different ways. ...
In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...
In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are nonzero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...
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 isomorphic if and only if there exists a permutation matrix P such that A graph isomorphism is a bijection between the vertices of two graphs and : with the property that any two vertices and from are adjacent if and only if and are adjacent in . ...
In linear algebra, a permutation matrix is a binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere. ...
 PA_{1}P ^{− 1} = A_{2}.
In particular, A_{1} and 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). Several equivalence relations in mathematics are called similarity. ...
In mathematics, the minimal polynomial of an object Î± is the monic polynomial p of least degree such that p(Î±)=0. ...
In linear algebra, one associates a polynomial to every square matrix, its characteristic polynomial. ...
In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...
In algebra, a determinant is a function depending on n that associates a scalar det(A) to every nÃ—n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...
In linear algebra, the trace of an nbyn square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A, i. ...
If A is the adjacency matrix of the directed or undirected graph G, then the matrix A^{n} (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. This article gives an overview of the various ways to perform matrix multiplication. ...
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 (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: In linear algebra, the identity matrix of size n is the nbyn square matrix with ones on the main diagonal and zeros elsewhere. ...
In linear algebra, an nbyn (square) matrix is called invertible, nonsingular, or regular if there exists an nbyn matrix such that where denotes the nbyn identity matrix and the multiplication used is ordinary matrix multiplication. ...
In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...
In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...
In mathematics, a geometric progression is a sequence of numbers such that the quotient of any two successive members of the sequence is a constant called the common ratio of the sequence. ...
 (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.
Variations The Seidel adjacency matrix or (0,−1,1)adjacency matrix of a simple graph has zero on the diagonal and entry a_{ij} = − 1 if ij is an edge and +1 if it is not. This matrix is used in studying strongly regular graphs and twographs. In mathematics, in graph theory, the Seidel adjacency matrix of a simple graph G (also called the Seidel matrix andâ€”the original nameâ€”the (âˆ’1,1,0)adjacency matrix) is the symmetric matrix with a row and column for each vertex, having 0 on the diagonal and, in the positions...
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors. ...
In mathematics, a twograph is a set of (unordered) triples chosen from a finite vertex set X, such that every (unordered) quadruple from X contains an even number of triples of the twograph. ...
A distance matrix is like a higherlevel 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. In mathematics, a distance matrix is a matrix (twodimensional array) containing the distances, taken pairwise, of a set of points. ...
Data structures 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. A binary tree, a simple type of branching linked data structure. ...
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
It has been suggested that this article or section be merged with Memory locality. ...
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 32bit computer, an adjacency list for an undirected graph requires about 16e bytes of storage, where e is the number of edges. In computer science, a linked list is one of the fundamental data structures used in computer programming. ...
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, 16e > 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 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. Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...
References  Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: SpringerVerlag. ISBN 0387952411
Thomas H. Cormen is the coauthor of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ...
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
External links  Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.
