adjacency matrix


Definition

Let G=(V,E) be a graph with vertex set V={v1,,vn} and edge set E. The adjacency matrixMathworldPlanetmath MG=(mij) of G is defined as follows: MG is an n×n matrix such that

mij={1if {vi,vj}E0otherwise.

In other words, start with the n×n zero matrixMathworldPlanetmath, put a 1 in (i,j) if there is an edge whose endpointsMathworldPlanetmath are vi and vj.

For example, the adjacency matrix of the following graph

is

(0011000011100011100001100).

Remarks. Let G be a graph and MG be its adjacency matrix.

  • MG is symmetricPlanetmathPlanetmathPlanetmathPlanetmath with 0’s in its main diagonal.

  • The sum of the cells in any given column (or row) is the degree of the corresponding vertex. Therefore, the sum of all the cells in MG is twice the number of edges in G.

  • MG=𝟏-I iff G is a complete graphMathworldPlanetmath. Here, 𝟏 is the matrix whose entries are all 1 and I is the identity matrixMathworldPlanetmath.

  • If we are given a symmetric matrix M of order n whose entries are either 1 or 0 and whose entries in the main diagonal are all 0, then we can construct a graph G such that M=MG.

Generalizations

The above definition of an adjacency matrix can be extended to multigraphsMathworldPlanetmath (multiple edges between pairs of vertices allowed), pseudographsMathworldPlanetmath (loops allowed), and even directed pseudographs (edges are directional). There are two cases in which we can generalize the definition, depending on whether edges are directional.

  1. 1.

    (Edges are not directional).

    Since a multigraph is just a special case of a pseudograph, we will define MG for a pseudograph G. Let G=(V,E) be a pseudograph with V={v1,,vn} The adjacency matrix MG=(mij) of G is an n×n matrix such that mij is the number of edges whose endpoints are vi and vj. Again, MG is symmetric, but the main diagonal may contain non-zero entries, in case there are loops.

  2. 2.

    (Edges are directional).

    Since a digraphMathworldPlanetmath is a special case of a directed pseudograph, we again define MG in the most general setting. Let G=(V,E) be a directed pseudograph with V={v1,,vn} and EV×V×({0}). The adjacency matrix MG of G is an n×n matrix such that

    mij=|{k(vi,vj,k)E}|.

    In other words, mij is the number of directed edges from vi to vj.

Remarks

  • If G is a multigraph, then the entries in the main diagonal of MG must be all 0.

  • If G is a graph, then MG corresponds to the original definition given in the previous sectionPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath.

  • If G is a digraph, then entries MG consists of 0’s and 1’s and its main diagonal consists of all 0’s.

  • Given any square matrixMathworldPlanetmath M, there is a directed pseudograph G with M=MG. In additionPlanetmathPlanetmath, M corresponds to adjacency matrix of various types of graphs if appropriate conditions are imposed on M

  • Generally, one can derive a pseudograph from a directed pseudograph by “forgetting” the order in the ordered pairs of vertices. If G is a directed pseudograph and G is the corresponding derived pseudograph. Let MG=(mij) and MG=(nij), then nij=mij+mji.

    In the languagePlanetmathPlanetmath of category theoryMathworldPlanetmathPlanetmathPlanetmathPlanetmath, the above operationMathworldPlanetmath is done via a forgetful functorMathworldPlanetmathPlanetmath (from the categoryMathworldPlanetmath of directed pseudographs to the category of pseudographs). Other forgetful functors between categories of various types of graphs are possible. In each case, the forgetful functor has an associated operation on the adjacency matrices of the graphs involved.

Title adjacency matrix
Canonical name AdjacencyMatrix
Date of creation 2013-03-22 17:22:43
Last modified on 2013-03-22 17:22:43
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 05C50