What is an Adjacency Matrix?

Question

Whenever read something in relation to graph theory I stumble upon a term called Adjacency matrix, it seems to me that this is strongly related to this theory. Therefore, I would like to know more about the subject.

Doubts

1. What is the Adjacency Matrix? Is it some kind of data structure?
2. What kind of relationship does it have with graph theory?
3. There’s some math behind that matrix?

Answer 1

What is the Adjacency Matrix?

Roughly speaking, it is a directly accessed Boolean matrix.

Given a graph with n vertices, the adjacency matrix is a Boolean matrix of n*n houses. If there are any edges connecting the vertices i,j (in that order), then matriz_adjacencias[i, j] == True; otherwise its value is false.

It fits into one of the graph representation strategies. Note that it applies to graphs finite and vertices acquaintances. What do I mean by that? Do there exist infinite graphs?

Yes, there are infinite graphs. They are described procedurally. I even spoke of an infinite graph in the my answer about the Parade Problem. In the specific case, the graph is described from an unrestricted grammar as follows::

1. whole vertex V graph is a sentential form
2. if V has some non-terminal in its composition, so there may be edge coming out of V towards another vertex
3. consider the edge Aijkl = (Vi, Vj), That means there’s a production Pk in grammar capable of transforming directly the sentential form Vi in sentential form Vj
   • the l in the edge index Aijkl to indicate that production Pk was applied in the position l in the sentential form Vi
4. S is a vertex that belongs to the graph

This description above respects the definition of graphs (a set of vertices and edges that contains two elements of the vertex set). Note that here determine whether a vertex V whether or not it belongs to the graph (i.e., it is within the vertex set of that graph) is a Turing-complete task, but by my understanding of set theory it does not preclude defining sets in this way. Similarly, the edges were also defined procedurally, but here it is deterministic and polynomial to determine whether the edge (Vi, Vj) exists.

In these cases, from graphs whose descriptions are procedural and an infinite set of data is generated, it is not possible to use adjacency matrices.

It would be some kind of data structure?

Attention, some code with a syntax similar to Python will be displayed below, but know that they are merely illustrative and could be done much more efficiently in Python; the idea is just to display a pseudo-code of what would be the implementation in an imperative language

Absolutely. As stated earlier, it indicates the existence or not of edges between two vertices.

The question to be asked to an adjacency matrix is: "there is an edge between the vertices Vi and Vj?" Programmatically it would be more or less G.adjacente(Vi, Vj).

The operation is more or less like this (using as v_origem and v_destino the indices of the vertices):

def adjacente(grafo, v_origem, v_destino):
  return grafo.matriz_adjacencias[v_origem, v_destino]

Other structures that serve as competitors to this structure (and that serve for finite graphs) are:

• distance matrix
  in the distance matrix you store the edge-related distance Aij = (Vi, Vj) and, if there is no such edge, you can store a value that indicates non-existence (such as null, NaN, infty or negative depending on the language and data storage protocol); whereas distances are stored as NaN to indicate that there are no edges, the following code addresses adjacencies (based on this):

  def adjacente(grafo, v_origem, v_destino):
    return not math.isnan(grafo.matriz_distancias[v_origem, v_destino])
  

• edge matrix
  similar to the model of adjacency matrix or of distance matrix, but here who is stored is an edge, not a boolean or a distance; in the absence of edge, or is stored null or an "invalid edge"; this model allows storing other data on the edges than just the distance between two points, but also other data types such as "color" edge; the mere existence of the (valid) edge in this matrix implies adjacency

  def adjacente(grafo, v_origem, v_destino):
    return grafo.matriz_arestas[v_origem, v_destino]) is not None
  

• adjacency list
  in this model, each vertex has its edges directly; for the graph G, ask G.adjacente(Vi, Vj) becomes a call to Vi.adjacente(Vj); in turn, Vi.adjacente(Vj) will consist of iteration of a list (linked or contiguous, at that point does not matter) but or less like this:

  def adjacente(grafo, v_origem, v_destino):
    # esse laço abaixo é equivalente a v_origem.adjacente(v_destino)
    for aresta in v_origem.arestas:
      if aresta.destino == v_destino:
        return True
    return False
  

When should I use this data structure?

Depends on the use =)

Particularly, I am not a fan of adjacency matrix per se, except if by chance your graph is a graph of unit distances. I prefer other models, mainly distance matrix. Sometimes people confuse the two matrices, so there’s a chance that someone’s talking about an adjacency matrix but is actually using a distance matrix.

Another possible case is when there is the possibility of several distinct edges between two points, each one good in one of the optimization objectives. In this case, indicating the existence of the link is not enough, as there may be several links between two vertices. And all these various links with various properties should be taken into account. For example, in that reply, there are two distinct links between (ap,ap) (yes, two self-incident edges of to ap).

What kind of relationship does it have with graph theory? / Is there any mathematics behind this matrix?

These two questions basically have the same answer. Graphs is pure mathematics. Basically, this is the relationship:

Some remarks

As stated earlier, be careful about the type of graph you are moving. If it allows the existence (and distinction) between different edges with the same origin and destination, then the adjacency matrix is not enough for your problem.

There is a distinction between distance matrices and adjacency matrices. The distance matrix can be transformed into adjacency matrix, but the reciprocal matrix is not true.

In directed graphs, it is common to find M[i,j] != M[j,i]. For example, in that matter I placed an automaton whose adjacency matrix is:

                  destino
o         | q0 | qb1 | qb2 | qa | damn
r    q0   | 1  | 1   | 0   | 0  | 0
i    qb1  | 1  | 0   | 1   | 0  | 0
g    qb2  | 1  | 0   | 1   | 1  | 0
e    qa   | 1  | 0   | 0   | 0  | 1
m    damn | 0  | 0   | 0   | 0  | 1

This happens because the graph is directed. If it were a graph undirected, then all reciprocals would be true.

There are cases where self-incident edges are not allowed.

The following questions can be answered by having only the adjacency matrix:

1. the graph is connected?
2. the graph G is isomorphic to the graph H? (Just because you can answer doesn’t mean that be easy to answer)
3. what are the bridges in that graph?
4. which path/which paths between vertices i and j with fewer jumps?¹
5. there is some "well" in relation to the vertex subset U? which vertices belong to this "well"?²

^{1: is the same as determining the shortest distance considering the unit distances =)
2: I took the terminology of well borrowed from automata; in automata theory, a well is a state from which it is impossible to go to a state of acceptance}

There are many other problems that are solved considering only the adjacencies, but I believe that the list is much more extensive than I am able to remember.

Adjacencies and clicks

A clique is a graph in which all the vertices are connected with each other (removing the auto-link). That is, an adjacency matrix of a 3-vertex click is this:

0  1  1
1  0  1
1  1  0

The only change that can be there is if there is some edge that has origin and destination at the same vertex, then on the main diagonal there will be the truth value for that link.

When it comes to a matrix indicating the distances between points in a plane (such as the existing matrix in that question), then we have a click, because at all times it is possible to leave one point and reach the other. For such cases, the adjacency matrix is redundant, and it is preferable to use the distance matrix.