FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Adjacency matrix

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 aij is the number of edges from vertex i to vertex j, and the diagonal entry aii 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 non-zero 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. ...

Contents

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.
Labeled graph Adjacency matrix
begin{matrix} 1 & 1 & 0 & 0 & 1 & 0 1 & 0 & 1 & 0 & 1 & 0 0 & 1 & 0 & 1 & 0 & 0 0 & 0 & 1 & 0 & 1 & 1 1 & 1 & 0 & 1 & 0 & 0 0 & 0 & 0 & 1 & 0 & 0 end{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 Kr,s has the form
begin{pmatrix} O & J  J^T & O end{pmatrix},

where J is an r × s matrix of all ones and O denotes an all-zero 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 6n-graph2. ... 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 non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...


Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given. G1 and G2 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. ...

PA1P − 1 = A2.

In particular, A1 and A2 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 n-by-n 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 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. 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 (IA) − 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 n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... In linear algebra, an n-by-n (square) matrix is called invertible, non-singular, or regular if there exists an n-by-n matrix such that where denotes the n-by-n 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. ...

(IA) − 1 = I + A + A2 + A3 + ...

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 aij = − 1 if ij is an edge and +1 if it is not. This matrix is used in studying strongly regular graphs and two-graphs. 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 two-graph 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 two-graph. ...


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. In mathematics, a distance matrix is a matrix (two-dimensional 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 n2 / 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 32-bit 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 n2 edges, allowing loops, we can let d = e / n2 denote the density of the graph. Then, 16e > n2 / 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: Springer-Verlag. ISBN 0-387-95241-1

Thomas H. Cormen is the co-author 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.

  Results from FactBites:
 
math lessons - List of matrices (755 words)
Adjacency matrix - a (0,1)-matrix that is square with all diagonal elements zero.
Companion matrix - the companion matrix of a polynomial is a special form of matrix, whose eigenvalues are equal to the roots of the polynomial.
Permutation matrix - matrix representation of a permutation.
Adjacency matrix - Wikipedia, the free encyclopedia (947 words)
The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.
The adjacency matrix of a complete graph is all 1's except for 0's on the diagonal.
The adjacency matrix of an undirected graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m