Adjacency Matrices
Simple Graphs
An adjacency matrix of a graph is a matrix consisting
solely of 1's and 0's, where a one in the
entry in the matrix indicates that vertex i is adjacent to
vertex j. For undirected graphs, if M is a
adjacency matrix, and if
,
then
.
For directed graphs,
indicates that there is a directed edge from vertex i to vertex
j.
Picture of Graph:
Self Loops
Typically, simple graphs do not have edges connecting the same vertex. However,
if this type of edge, called a loop, is allowed, then the Adjacency Matrix
will allow for non-zero entries along its main diagonal.
Multi-graphs
The definition of an Adjacency Matrix changes slightly when considering
non-simple graphs. Entries in the matrix are allowed to have nonnegative
values (aside from just 0 and 1).
Back to A Naive Solution
Copyright
2000
Rensselaer Polytechnic Institute. All Rights Reserved.