adjacency matrix
Definition
Let be a graph with vertex set and edge set . The adjacency matrix of is defined as follows: is an matrix such that
In other words, start with the zero matrix, put a in if there is an edge whose endpoints are and .
For example, the adjacency matrix of the following graph
is
Remarks. Let be a graph and be its adjacency matrix.
-
•
is symmetric with ’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 is twice the number of edges in .
-
•
iff is a complete graph. Here, is the matrix whose entries are all and is the identity matrix.
-
•
If we are given a symmetric matrix of order whose entries are either or and whose entries in the main diagonal are all , then we can construct a graph such that .
Generalizations
The above definition of an adjacency matrix can be extended to multigraphs (multiple edges between pairs of vertices allowed), pseudographs (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.
(Edges are not directional).
Since a multigraph is just a special case of a pseudograph, we will define for a pseudograph . Let be a pseudograph with The adjacency matrix of is an matrix such that is the number of edges whose endpoints are and . Again, is symmetric, but the main diagonal may contain non-zero entries, in case there are loops.
-
2.
(Edges are directional).
Since a digraph is a special case of a directed pseudograph, we again define in the most general setting. Let be a directed pseudograph with and . The adjacency matrix of is an matrix such that
In other words, is the number of directed edges from to .
Remarks
-
•
If is a multigraph, then the entries in the main diagonal of must be all .
-
•
If is a graph, then corresponds to the original definition given in the previous section.
-
•
If is a digraph, then entries consists of ’s and ’s and its main diagonal consists of all ’s.
-
•
Given any square matrix , there is a directed pseudograph with . In addition, corresponds to adjacency matrix of various types of graphs if appropriate conditions are imposed on
-
•
Generally, one can derive a pseudograph from a directed pseudograph by “forgetting” the order in the ordered pairs of vertices. If is a directed pseudograph and is the corresponding derived pseudograph. Let and , then .
In the language of category theory, the above operation is done via a forgetful functor (from the category 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 |