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:
- todo vértice
V
do grafo é uma forma sentencial
- 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
- 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
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:
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:
- o grafo é conexo?
- o grafo
G
é isomorfo ao grafo H
? (só porque pode responder não quer dizer que seja fácil responder)
- quais são as pontes nesse grafo?
- qual o caminho/quais os caminhos entre os vértices
i
e j
com menos saltos?1
- 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.
Adjacências e cliques
Um clique é um grafo em que todos os vértices são ligados uns com os outros (retirando a auto-ligação). Ou seja, uma matriz de adjacências de um clique de 3 vértices é isto:
0 1 1
1 0 1
1 1 0
A única mudança que pode haver é se existe alguma aresta que tem origem e destino no mesmo vértice, então na diagonal principal vai haver o valor verdade para essa ligação.
Quando se trata de uma matriz indicando as distâncias entre pontos em um plano (como a matriz existente nessa pergunta), então temos um clique, pois sempre é possível sair de um ponto e chegar no outro. Para casos assim, a matriz de adjacências é redundante, sendo preferível usar a matriz de distâncias.