ADJACENCY MATRIX

ADJACENCY MATRIX (LET)

Let Subcommand

Create an adjacency matrix from a list of edges.

In graph theory, given n vertices an nxn adjacency matrix defines the connections between the edges. If there is an edge between vertex i and vertex j, then A_ij = 1. Otherwise, A_ij = 0.

We make a distinction between undirected and directed adjacency matrices. For the undirected case, the order of the edges does not matter. So an edge between vertex i and vertex j means that both A_ij and A_ji will be set to 1. In the directed case, the order is relevant. So if A_ij = 1, this does not imply that A_ji = 1.

Adjaency matrices are most useful when dealing with dense graphs with a relatively modest number of vertices.

LET <mat> = ADJACENCY MATRIX <edge1> <edge2> <nvert>
where <edge1> is a variable that identifies the first vertex in the edge;
            <edge2> is a variable that identifies the second vertex in the edge;
and <mat> is a matrix where the adjacency matrix is saved.

This syntax is used for the undirected case.

LET <mat> = DIRECTED ADJACENCY MATRIX <edge1> <edge2> <nvert>
where <edge1> is a variable that identifies the first vertex in the edge;
            <edge2> is a variable that identifies the second vertex in the edge;
and <mat> is a matrix where the adjacency matrix is saved.

This syntax is used for the directed case.

LET M = ADJACENCY MATRIX E1 E2 NVERT

The maximum size matrix that DATAPLOT can handle is set when DATAPLOT is built on a particular site. Enter HELP DIMENSION and HELP MATRIX DIMENSION for details.

None

EDGES TO ADJACENCY MATRIX is a synonym for ADJACENCY MATRIX.

2D CONVEX HULL	= Compute the 2D convex hull of a set of points.
MINIMUM SPANNING TREE	= Compute the minimum spanning tree.
SPANNING FOREST	= Compute the spanning forest.
NEXT PERMUTATION	= Generate the next permutation of n letters.
RANDOM PERMUTATION	= Generate a set of random permutations.

Skiena (1998), "The Algorithm Design Manual", Telos.

Graph Theory

2009/1

 
dimension 100 columns
read edge1 edge2
2 3
4 7
1 9
7 11
5 8
2 5
6 10
2 8
3 8
4 11
end of data
.
let nvert = 14
let adj = adjacency matrix edge1 edge2 nvert
.
set write format 14F5.0
print adj