5

Sempre que leio algo em relação a teoria dos grafos eu esbarro com um termo chamado Matriz de Adjacência, me parece que isso esta fortemente relacionado com esta teoria. Sendo assim, eu gostaria de saber mais a respeito do assunto.

Dúvidas

  1. O que é a Matriz de Adjacência? Seria algum tipo de estrutura de dados?
  2. Que tipo de relação ela tem com a teoria dos grafos?
  3. Há alguma matemática por traz dessa matriz?
4
  • 1
    Sim, é uma estrutura de dados. Ela basicamente é um grafo, e sim, tem muita matemática envolvida.. já estudou sobre Dijkstra? Commented 12/04/2018 às 12:47
  • @DiegoRafaelSouza nem é a parte matemática o mais importante, mas sim o uso dela na teoria dos grafos.
    – gato
    Commented 12/04/2018 às 12:58
  • 3
    @DiegoRafaelSouza , não sei se é porque eu já ensinei e expliquei tanto o que é isso que levaria uma pessoa à exaustão, mas para mim ela é perfeitamente clara e objetiva. Poderia caber no Mathematics sim, mas como também é um termo relacionado a programação é extensamente usado em problemas de grafos finitos de uma aresta (no máximo) entre dois vértices, é perfeitamente cabível dentro do SOpt. Tão cabível quanto perguntar o que é a classe de complexidade NPI (assunto mais direcionado ao Computer Science) Commented 12/04/2018 às 13:08
  • 2
    Abri uma discussão no meta sobre o assunto - e a questão. Conto com a porticipação, obrigadão! Commented 12/04/2018 às 18:46

1 Resposta 1

5

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
  4. 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.

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.

3
  • 1
    Olhe que problema interessante eu bolei: "Tenho duas matrizes A e B quadradas de mesmo tamanho cheias de números. Devo decidir se é ou não possível transformar A em B por meio de alguma sequência qualquer de operações de permuta, onde em cada operação, eu posso permutar as linhas i e j desde que também permutando as colunas i e j." - Esse problema é provavelmente NPI, vez que o problema do isomorfismo de grafos é reduzido a ele ao transformar os dois grafos em matrizes de adjacência. Commented 15/04/2018 às 6:02
  • 2
    Nessa resposta, você só está esquecendo o caso das arestas paralelas, onde ao invés de booleano temos um inteiro não-negativo. De qualquer forma, já tem o meu +1 garantido fácil. Commented 15/04/2018 às 6:13
  • @VictorStafusa adicionar essa observação sobre arestas paralelas está no meu roadmap desta resposta, mas acabou que como a prioridade para tal é baixa, ainda estou devendo... e muito interessante sua observação do NPI, isomorfismo de matrizes xD Commented 23/04/2018 às 16:42

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .