The elements of the matrix indicate whether pairs of vertices are adjacent or not in the 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 (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric.
[1] The diagonal elements of the matrix are all 0, since edges from a vertex to itself (loops) are not allowed in simple graphs.
[2] The same concept can be extended to multigraphs and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements.
Loops may be counted either once (as a single edge) or twice (as two vertex-edge incidences), as long as a consistent convention is followed.
In this case, the smaller matrix B uniquely represents the graph, and the remaining parts of A can be discarded as redundant.
Formally, let G = (U, V, E) be a bipartite graph with parts U = {u1, ..., ur}, V = {v1, ..., vs} and edges E. The biadjacency matrix is the r × s 0–1 matrix B in which bi,j = 1 if and only if (ui, vj) ∈ E. If G is a bipartite multigraph or weighted graph, then the elements bi,j are taken to be the number of edges between the vertices or the weight of the edge (ui, vj), respectively.
An (a, b, c)-adjacency matrix A of a simple graph has Ai,j = a if (i, j) is an edge, b if it is not, and c on the diagonal.
This matrix is used in studying strongly regular graphs and two-graphs.
The distance is the length of a shortest path connecting the vertices.
The convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop (an edge from a vertex to itself) adds 2 to the appropriate cell on the diagonal in the matrix.
[4] This allows the degree of a vertex to be easily found by taking the sum of the values in either its respective row or column in the adjacency matrix.
One can define the adjacency matrix of a directed graph either such that The former definition is commonly used in graph theory and social network analysis (e.g., sociology, political science, economics, psychology).
The adjacency matrix of a complete graph contains all ones except along the diagonal where there are only zeros.
The adjacency matrix of an undirected simple graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis.
Without loss of generality assume vx is positive since otherwise you simply take the eigenvector -v, also associated to
This bound is tight in the Ramanujan graphs, which have applications in many areas.
Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given.
In an undirected graph, each triangle will be counted twice for all three nodes, because the path can be followed clockwise or counterclockwise : ijk or ikj.
The main alternative data structure, also in use for this application, is the adjacency list.
They can, for example, be used to represent sparse graphs without incurring the space overhead from storing the many zero entries in the adjacency matrix of the sparse graph.
In the following section the adjacency matrix is assumed to be represented by an array data structure so that zero and non-zero entries are all directly represented in storage.
Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only |V |2 / 8 bytes to represent a directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately |V |2 / 16 bytes to represent an undirected graph.
Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all n-vertex graphs.
[14] Besides avoiding wasted space, this compactness encourages locality of reference.
[15] It is also possible to store edge weights directly in the elements of an adjacency matrix.
Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list, and takes time proportional to the number of neighbors.
With an adjacency matrix, an entire row must instead be scanned, which takes a larger amount of time, proportional to the number of vertices in the whole graph.
On the other hand, testing 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.