What is the adjacency matrix?

Roughly speaking, it is an array of booleans accessed directly.

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 finite and Vertex graphs known . What do I mean by that?, are there infinite graphs?

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

1. every vertex V of the 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), this means that there is a production Pk in the grammar capable of transforming directly the Sentential form Vi into the Sentential Form Vj
   • the l in the index of the edge Aijkl serves to indicate that the production Pk was applied at the position l of 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 determining whether or not a vertex V belongs to the graph (that is, it is within the vertex set of that graph) is a Turing-complete task, but by my understanding of Set Theory it does not make it impossible to define sets in this way. Similarly, the edges were also procedurally defined, but here it is deterministic and polynomial to determine whether the edge (Vi, Vj) exists.

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

Would it be some kind of data structure?

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

For sure. As said earlier, it indicates the existence or not of edges between two vertices.

The question to be asked to an adjacency matrix is: "Is there 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 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:

• Array of distances
  in the array of distances you store the distance related to edge Aij = (Vi, Vj) and if there is no such edge, you can store a value indicating non-existence (such as null, NaN, infty depending on the language and the data storage protocol); whereas the distances are stored as NaN to indicate that there are no edges, the following code responds about 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 array of distances , but here who is stored is an edge, not a Boolean or a distance; in the absence of an edge, or if stored null or an "invalid edge" ; this model allows you to store other data on the edges that not only the distance between two points, but also other data types, such as the "color" of the edge; the simple existence of the (valid) edge in this Matrix implies the adjacency

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

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

  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 usage=)

Particularly, I'm not a fan of adjacency matrix per se, unless by chance your graph is a graph of unit distances . I prefer other models, mainly from array of distances . Sometimes people confuse the two matrices, so there is a chance that someone will talk about adjacency matrix but actually be using array of distances.

Another possible case is when there is the possibility of several distinct edges between two points, each good at one of the optimization objectives. In this case, indicating the existence of the link is not enough, since there may be several links between two vertices. And all these diverse bindings with diverse properties must be taken into account. For example, in this response , there are two links distinct between (ap,ap) (yes, two self-incident edges from 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, the relationship is this:

Some observations

As stated earlier, take care of the type of graph you are stirring. If it allows existence (and distinction) between different edges with same origin and destination, so the matrix of adjacencies is not enough for your problem.

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

In directed graphs, it is common to find M[i,j] != M[j,i]. For example, in this question I put 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 an undirected graph , then all reciprocals would be true.

There are cases where it is not allowed to have self-incident edges.

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

1. is the graph connected?
2. is the graph G isomorphic to the graph H? (just because you can answer doesn't mean is easy to answer )
3. What are the bridges in this graph?
4. which path/which paths between vertices i and j with minus jumps ?¹
5. is there any "pit" in relation to the subset of vertices U? what vertices belong to this"well"?²

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

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

Adjacencies and clicks

A click is a graph in which all vertices are connected with each other (removing the self-linking). That is, an array of 3-Vertex click adjacencies is this:

0  1  1
1  0  1
1  1  0

The only change there can be is if there is some edge that has origin and destination on the same Vertex, then on the main diagonal there will be the true value for that connection.

When it comes to an array indicating the distances between points in a plane (like the existing array in this question ), then we have a click, since always it is possible to exit a point and reach on the other. For such cases, the adjacency matrix is redundant, and it is preferable to use the distance matrix.