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.