Calculadora de Matriz de Adjacência

Calculadora de Matriz de Adjacência

A Calculadora de Matriz de Adjacência é um utilitário de teoria dos grafos que converte entre as três representações canônicas de grafos — matriz de adjacência, lista de arestas e lista de adjacência — e enriquece o resultado com análise estrutural: sequência de graus, densidade do grafo, componentes conexos e potências da matriz. Ela detecta automaticamente se sua entrada descreve um grafo direcionado ou não direcionado e renderiza uma visualização SVG interativa junto com cada resultado.

O Que é uma Matriz de Adjacência?

Dado um grafo G = (V, E) com n vértices, sua matriz de adjacência é a matriz quadrada n × n, A, cuja entrada A[i][j] é 1 se houver uma aresta do vértice i para o vértice j, e 0 caso contrário.

Para um grafo não direcionado, a matriz de adjacência é sempre simétrica: cada aresta {u, v} contribui tanto para A[u][v] = 1 quanto para A[v][u] = 1. Para um grafo direcionado (digrafo), a matriz pode ser assimétrica, refletindo a direção de cada arco.

Três Representações — Escolha a que Melhor se Adapta ao seu Problema

Principais Métricas Computadas

Sequência de Graus

Para grafos não direcionados, o grau de um vértice é o número de arestas incidentes a ele (com self-loops contando duas vezes). Para grafos direcionados, cada vértice possui um grau de entrada (arcos chegando) e um grau de saída (arcos saindo). A lista ordenada de graus é um invariante de grafo clássico usado em testes de isomorfismo e no teorema de realizabilidade de Erdős–Gallai.

Densidade do Grafo

A densidade mede o quão "cheio" um grafo está em relação ao número máximo de arestas possíveis em n vértices.

Uma densidade de 0 significa nenhuma aresta, 1 significa que o grafo é completo, e valores abaixo de 0,1 indicam tipicamente um grafo esparso, onde uma lista de adjacência é mais eficiente em termos de espaço do que uma matriz.

Componentes Conexos

Um componente conexo é um subconjunto maximal de vértices tal que cada par é unido por um caminho. Para grafos direcionados, esta calculadora relata componentes fracamente conexos (ignorando as direções das setas) — os mesmos subconjuntos que você obteria ao tratar cada arco como uma aresta não direcionada.

Potências da Matriz (A², A³ ... )

Um teorema fundamental da teoria algébrica dos grafos afirma que a entrada (i, j) de A^k é igual ao número de percursos de exatamente comprimento k do vértice i para o vértice j. Consequentemente:

• A²[i][i] é igual ao grau do vértice i (não direcionado), já que um percurso de 2 passos de i para si mesmo é "ir a um vizinho e voltar".
• O traço de A³ dividido por 6 conta os triângulos em um grafo não direcionado.
• Se Aⁿ⁻¹ possui alguma entrada zero, isso informa se o grafo é conexo.

Formatos de Entrada Aceitos

1. Lista de arestas

Uma aresta por linha ou separada por vírgula. Qualquer um destes separadores funciona: A-B, A B, A,B, A->B, A--B. Use -> se quiser forçar uma interpretação direcionada.

2. Lista de adjacência

Uma linha por vértice, na forma vértice: vizinho1, vizinho2, .... A ordem não importa; vértices ausentes são adicionados automaticamente a partir das listas de vizinhos.

3. Matriz de adjacência

Uma linha por linha com valores 0/1 separados por espaço ou vírgula. A matriz deve ser quadrada. Opcionalmente, forneça rótulos personalizados no campo Rótulos da matriz (caso contrário, A, B, C… serão usados).

Como Usar Esta Calculadora

1. Escolha um formato de entrada usando o seletor de abas: lista de arestas, lista de adjacência ou matriz de adjacência.
2. Cole ou digite seu grafo na área de texto. Para entrada de matriz, adicione rótulos opcionais no campo Rótulos da matriz.
3. Selecione o tipo de grafo — deixe em Detecção automática e a calculadora inferirá o direcionamento a partir das setas (->) ou da simetria da matriz. Force para Direcionado ou Não direcionado se desejar sobrescrever.
4. Clique em Converter e Analisar Grafo. A página de resultados mostra a matriz de adjacência, uma renderização SVG interativa, as outras duas representações em texto, estatísticas de graus, componentes conexos e matrizes de contagem de percursos A² e A³ quando o grafo é pequeno o suficiente.
5. Passe o mouse sobre uma linha da matriz ou um nó do grafo para iluminar a linha/coluna correspondente e as arestas incidentes — uma prova visual instantânea de que cada formato codifica a mesma informação.

Exemplo Prático

Considere um grafo não direcionado nos vértices {A, B, C, D} com as arestas AB, BC, CA, CD. A matriz de adjacência é:

Fatos principais que a calculadora deriva:

• Simétrica? Sim — confirma que não é direcionado.
• Sequência de graus: (3, 2, 2, 1) — o vértice C é o centro.
• Densidade: 2·4 / (4·3) = 0,667 — um grafo moderadamente denso.
• Conexo? Sim, componente único.
• Triângulos: exatamente um (A–B–C), conforme confirmado por tr(A³) = 6.

Aplicações Comuns

• Análise de redes sociais — grafos de amizade / seguidores, centralidade.
• Grafos da Web e de citações — PageRank e HITS trabalham diretamente sobre A e A^T.
• Roteamento e redes — caminho mais curto, corte mínimo, fluxo máximo.
• Química — grafos moleculares com átomos como vértices e ligações como arestas.
• Agendamento e resolução de dependências — grafos acíclicos direcionados (DAGs) em sistemas de build.
• Cadeias de Markov — matrizes estocásticas por linha derivadas de grafos codificam probabilidades de transição.

Perguntas Frequentes

O que é uma matriz de adjacência?

Uma matriz de adjacência é uma matriz quadrada n × n usada para representar um grafo finito. Cada célula A[i][j] é 1 se houver uma aresta do vértice i para o vértice j, e 0 caso contrário. Para grafos não direcionados, a matriz é simétrica, então A[i][j] = A[j][i]. A matriz facilita a verificação se dois vértices estão conectados em tempo constante, e as potências da matriz codificam o número de percursos entre os vértices.

Como saber se um grafo é direcionado a partir de sua matriz de adjacência?

Se a matriz de adjacência for simétrica, significando que A[i][j] é igual a A[j][i] para cada par de índices, o grafo não é direcionado. Se houver pelo menos um par onde A[i][j] difere de A[j][i], o grafo é direcionado. Esta calculadora realiza essa verificação de simetria automaticamente quando você escolhe a opção Detecção automática.

O que a k-ésima potência de uma matriz de adjacência representa?

A entrada (i, j) de A^k conta o número de percursos de exatamente comprimento k do vértice i para o vértice j. Por exemplo, A²[i][j] é o número de caminhos de 2 passos, o que equivale ao número de vizinhos comuns entre i e j em grafos não direcionados. Essa propriedade é usada em algoritmos para contagem de triângulos, acessibilidade e computações do tipo PageRank.

O que é densidade do grafo?

A densidade do grafo é a razão entre o número de arestas presentes e o número máximo possível de arestas. Para um grafo simples não direcionado com n vértices, densidade = 2m / (n(n-1)). Para um grafo direcionado, densidade = m / (n(n-1)). Uma densidade próxima de 0 significa um grafo esparso; uma densidade de 1 significa um grafo completo.

Qual a diferença entre uma matriz de adjacência e uma lista de adjacência?

Uma matriz de adjacência armazena a conectividade para cada par de vértices usando n² bits, tornando a busca de vizinhos O(1), mas o uso de memória O(n²). Uma lista de adjacência armazena apenas os vizinhos reais de cada vértice, resultando em memória O(n + m), que é muito menor para grafos esparsos, mas a busca de vizinhos requer uma varredura linear. Matrizes são melhores para grafos densos e operações de álgebra matricial; listas são melhores para grafos esparsos e algoritmos de travessia como BFS/DFS.

Esta ferramenta suporta grafos ponderados?

A calculadora atual foca em matrizes de adjacência não ponderadas com entradas 0/1. Se você colar uma matriz com pesos numéricos diferentes de zero, cada célula diferente de zero é tratada como 1 para a análise estrutural. Para computações de grafos ponderados, como caminho mais curto, considere uma ferramenta dedicada a grafos ponderados.

Leitura Adicional

• Matriz de adjacência — Wikipedia
• Sequência de graus — Wikipedia
• Densidade do grafo — Wikipedia
• Componentes conexos — Wikipedia