Skip to main content
3 de 4
Número correto.
Victor Stafusa
  • 64,9mil
  • 9
  • 120
  • 189

O que é a Matriz de Adjacência?

A grosso modo, é uma matriz de booleanos acessado de maneira direta.

Dado um grafo com n vértices, a matriz de adjacências é uma matriz booleana de n*n casas. Se há alguma aresta ligando os vértices i,j (nessa ordem), então matriz_adjacencias[i, j] == True; caso contrário, seu valor é falso.

Ela se encaixa em uma das estratégias de representação de grafos. Note que ela se aplica a grafos finitos e de vértices conhecidos. O que quero dizer com isso?, por acaso existem grafos infinitos?

Sim, existem grafos infinitos. Eles são descritos proceduralmente. Inclusive eu falei de um grafo infinito na minha resposta sobre o Problema da Parada. No caso em específico, o grafo é descrito a partir de uma gramática irrestrita da seguinte forma:

  1. todo vértice V do grafo é uma forma sentencial
  2. se V tem algum não-terminal em sua composição, então pode haver aresta saindo de V em direção a outro vértice
  3. considere a aresta Aijkl = (Vi, Vj), isso significa que há uma produção Pk na gramática capaz de transformar diretamente a forma sentencial Vi na forma sentencial Vj
  • o l no índice da aresta Aijkl serve para indicar que a produção Pk foi aplicada na posição l da forma sentencial Vi
  1. S é um vértice que pertence ao grafo

Essa descrição acima respeita a definição de grafos (um conjunto de vértices e arestas que contém dois elementos do conjunto de vértices). Note que aqui determinar se um vértice V pertence ou não ao grafo (ou seja, está dentro do conjunto de vértices daquele grafo) é uma tarefa Turing-completa, mas pelo meu entendimento de Teoria dos Conjuntos não inviabiliza definir conjuntos desse jeito. Similarmente, as arestas também foram definidas de maneira procedural, mas aqui é determinístico e polinomial determinar se a aresta (Vi, Vj) existe.

Nesses casos, de grafos cujas descrições são procedurais e se gera um conjunto infinito de dados, não é possível usar matrizes de adjacência.

Seria algum tipo de estrutura de dados?

Atenção, alguns códigos com uma sintaxe semelhante a Python vai ser exibido a seguir, mas saiba que eles são meramente ilustrativos e que poderiam ser feitos de maneira muito mais eficiente em Python; a ideia é apenas exibir um pseudo-código de como seria a implementação em uma linguagem imperativa

Com certeza. Como dito anteriormente, ela indica a existência ou não de arestas entre dois vértices.

A pergunta a ser feita a uma matriz de adjacência é: "há uma aresta entre os vértices Vi e Vj?" Programaticamente seria mais ou menos G.adjacente(Vi, Vj).

A operação é mais ou menos assim (usando como v_origem e v_destino os índices dos vértices):

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

Outras estruturas que servem de concorrentes a essa estrutura (e que servem para grafos finitos) são:

  • matriz de distâncias
    na matriz de distâncias você armazena a distância relacionada a aresta Aij = (Vi, Vj) e, caso não haja tal aresta, você pode armazenar um valor que indica a não existência (como null, NaN, infty ou negativos, dependendo da linguagem e do protocolo de armazenamento de dados); considerando que as distâncias são armazenadas como NaN para indicar que não há arestas, o código a seguir responde sobre as adjacências (baseado nisto):

      def adjacente(grafo, v_origem, v_destino):
        return not math.isnan(grafo.matriz_distancias[v_origem, v_destino])
    
  • matriz de arestas
    semelhante ao modelo de matriz de adjacência ou de matriz de distâncias, mas aqui quem é armazenado é uma aresta, não um booleano ou uma distância; na ausência de aresta, ou se armazena null ou uma "aresta inválida"; esse modelo permite armazenar outros dados nas arestas que não apenas a distância entre dois pontos, mas também outros tipos de dados, como a "cor" da aresta; a simples existência da aresta (válida) nessa matriz implica na adjacência

      def adjacente(grafo, v_origem, v_destino):
        return grafo.matriz_arestas[v_origem, v_destino]) is not None
    
  • lista de adjacências
    nesse modelo, cada vértices tem suas arestas diretamente; para o grafo G, perguntar G.adjacente(Vi, Vj) se torna uma chamada para Vi.adjacente(Vj); por sua vez, Vi.adjacente(Vj) vai consistir na iteração de uma lista (ligada ou contígua, nesse ponto não interessa) mas ou menos assim:

      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
    

Quando devo usar essa estrutura de dados?

Depende do uso =)

Particularmente, eu não sou fã de matriz de adjacência por si, exceto se por acaso o seu grafo for um grafo de distâncias unitárias. Prefiro outros modelos, principalmente de matriz de distâncias. As vezes as pessoas confundem as duas matrizes, então há a hipótese de alguém falar de matriz de adjacência mas na verdade estar usando matriz de distâncias.

Outro caso possível é quando há a possibilidade de existir diversas arestas distintas entre dois pontos, cada uma boa em um dos objetivos da otimização. Nesse caso, indicar a existência da ligação não é o suficiente, pois podem existir várias ligações entre dois vértices. E todas essas diversas ligações com diversas propriedades devem ser levadas em consideração. Por exemplo, nessa resposta, existem duas ligações distintas entre (ap,ap) (sim, duas arestas auto-incidentes de para ap).

Que tipo de relação ela tem com teoria dos grafos? / Há alguma matemática por traz dessa matriz?

Essas duas perguntas basicamente tem a mesma resposta. Grafos é matemática pura. Basicamente, a relação é essa:

se a matriz na posição (i,j) for verdade, então há aresta de i para j no grafo

Algumas observações

Como dito anteriormente, tome cuidado com o tipo de grafo que você está mexendo. Se ele permitir a existência (e a distinção) entre arestas diferentes com mesmos origem e destino, então a matriz de adjacências não é o suficiente para o seu problema.

Há distinção entre matrizes de distâncias e matrizes de adjacências. A matriz de distância pode ser transformada em matriz de adjacência, mas a recíproca não é verdadeira.

Em grafos direcionados, é comum encontrar M[i,j] != M[j,i]. Por exemplo, nessa questão eu coloquei um autômato cuja matriz de adjacência é:

                  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

Isso acontece pois o grafo é direcionado. Se fosse um grafo não-direcionado, então todas as recíprocas seriam verdadeiras.

Existem casos em que não é permitido ter arestas auto-incidentes.

As seguintes questões podem ser respondidas tendo somente a matriz de adjacências:

  1. o grafo é conexo?
  2. o grafo G é isomorfo ao grafo H? (só porque pode responder não quer dizer que seja fácil responder)
  3. quais são as pontes nesse grafo?
  4. qual o caminho/quais os caminhos entre os vértices i e j com menos saltos?1
  5. existe algum "poço" em relação ao subconjunto de vértices U? quais os vértices que pertencem a esse "poço"?2

1: é o mesmo que determinar a menor distância considerando as distâncias unitárias =)
2: tomei a terminologia de poço emprestado dos autômatos; na teoria dos autômatos, um poço é um estado que, do qual, é impossível ir para um estado de aceitação

Existem outros muitos problemas que são resolvidos considerando-se apenas as adjacências, mas creio que a lista é muito mais extensa do que eu sou capaz de lembrar.

Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158