O que é a análise de redes pela teoria dos grafos?
A análise pela teoria dos grafos estuda uma rede transformando-a em um grafo: um conjunto de vértices conectados por arestas. Em linguagem cotidiana, os vértices são os elementos da rede, e as arestas são as relações ou conexões entre eles.
Um grafo pode representar muitos tipos de redes:
-
Cidades conectadas por estradas ou voos
-
Pessoas conectadas por amizades
-
Computadores conectados por cabos
-
Páginas da web conectadas por links
-
Tarefas conectadas por dependências
Em um grafo não direcionado e não ponderado, cada conexão funciona nos dois sentidos e todas as arestas têm o mesmo peso. Isso significa que uma aresta de A para B é igual a uma aresta de B para A, e o analisador mede os caminhos contando arestas, não distância, custo, tempo ou capacidade.
Esse tipo de análise ajuda a responder a perguntas práticas, como:
-
Quantos grupos separados a rede tem?
-
Quais nós têm mais conexões diretas?
-
Qual é a rota mais curta de um nó a outro?
-
Quais arestas ou nós são pontos únicos de falha?
-
O grafo contém um caminho euleriano, um circuito euleriano ou um caminho hamiltoniano?
A disposição visual pode tornar o grafo mais fácil de entender, mas a matemática depende das conexões, não de onde os nós são desenhados.
Por que a análise de redes em grafos é importante
A análise de grafos é útil porque muitos sistemas do mundo real são mais bem compreendidos por suas relações do que por sua aparência física. Um mapa rodoviário, uma rede de amizades escolares e uma rede de computadores podem parecer muito diferentes, mas todos podem ser estudados com as mesmas ideias básicas de grafos.
Para estudantes, a análise de grafos desenvolve a intuição sobre matemática discreta, algoritmos e estrutura de redes. Para educadores, ela oferece uma forma visual de explicar ideias abstratas, como componentes conexos, grau, caminhos mínimos, pontes e árvores geradoras. Para usuários em geral, ajuda a revelar se uma rede é robusta, centralizada, fragmentada ou dependente de poucas conexões importantes.
Por exemplo, uma rede com um componente é conexa: todo nó pode chegar a qualquer outro por algum caminho. Uma rede com vários componentes está dividida em grupos separados. Uma aresta ponte ou um nó crítico pode mostrar onde a remoção de uma conexão ou de um vértice tornaria a rede menos conexa.
Termos importantes
-
Grafo: Um modelo matemático formado por vértices e arestas.
-
Vértice ou nó: Um ponto no grafo, como uma cidade, pessoa, dispositivo ou item identificado.
-
Aresta ou conexão: Um vínculo entre dois vértices.
-
Aresta não direcionada: Uma conexão sem sentido único. A conexão A--B é igual a B--A.
-
Aresta não ponderada: Uma conexão sem valor de custo, comprimento, tempo ou prioridade. Cada aresta conta como um passo.
-
Grafo simples: Um grafo sem laços e sem arestas paralelas entre o mesmo par de vértices.
-
Grau: O número de arestas que tocam um vértice.
-
Componente conexo: Um grupo máximo de vértices em que todos podem alcançar uns aos outros.
-
Caminho mínimo: Um caminho entre dois vértices que usa o menor número de arestas.
-
Busca em largura: Um método de busca em grafos que explora primeiro os vértices a uma aresta de distância, depois a duas, depois a três e assim por diante.
-
Proximidade: Uma medida de centralidade baseada na distância de um nó em relação a outros nós alcançáveis.
-
Ponte: Uma aresta cuja remoção aumenta o número de componentes conexos.
-
Ponto de articulação: Um vértice cuja remoção aumenta o número de componentes conexos.
-
Árvore geradora: Um subgrafo em forma de árvore que inclui todos os vértices de um grafo conexo.
-
Floresta geradora: Uma coleção de árvores geradoras, uma para cada componente conexo.
-
Caminho euleriano: Uma rota que usa cada aresta exatamente uma vez.
-
Circuito euleriano: Um caminho euleriano que começa e termina no mesmo vértice.
-
Caminho hamiltoniano: Um caminho que visita cada vértice exatamente uma vez.
Como funciona a análise de grafos não direcionados e não ponderados
Um grafo simples e não direcionado costuma ser escrito como:
$$
G = (V, E)
$$
Em que:
-
\(G\) é o grafo.
-
\(V\) é o conjunto de vértices.
-
\(E\) é o conjunto de arestas.
Neste analisador, toda aresta é não direcionada e não ponderada. Essa escolha afeta todos os resultados. Os caminhos mínimos são medidos pela contagem de arestas, não pela distância desenhada. Uma aresta curva que parece longa e uma aresta que parece curta contam, ambas, como uma aresta.
Grau
O grau de um vértice é o número de vértices vizinhos diretamente conectados a ele. Se \(\operatorname{adj}(v)\) é o conjunto de vértices adjacentes ao vértice \(v\), então:
$$
\deg(v) = |\operatorname{adj}(v)|
$$
Um nó de alto grau tem muitas conexões diretas. Em uma rede social, isso pode representar uma pessoa com muitos contatos diretos. Em uma rede de transporte, pode representar um ponto de conexão com muitas rotas.
O grau máximo é o maior grau entre todos os nós do grafo:
$$
\Delta(G) = \max_{v \in V} \deg(v)
$$
Isso ajuda a identificar a parte da rede com mais conexões diretas.
Componentes conexos
Um componente conexo é um grupo de vértices em que cada vértice pode alcançar todos os outros vértices do mesmo grupo. Se o grafo tem exatamente um componente, ele é conexo. Se tem dois ou mais componentes, ele é desconexo.
A busca em largura ou a busca em profundidade pode ser usada para encontrar componentes: começa-se em um nó não visitado, marca-se tudo o que é alcançável a partir dele e repete-se o processo para o próximo nó não visitado.
Caminhos mínimos em um grafo não ponderado
Em um grafo não ponderado, o caminho mínimo entre dois vértices é o caminho com o menor número de arestas. Não é o caminho que parece mais curto na tela.
Para um vértice de origem \(s\) e um vértice de destino \(t\), a distância do caminho mínimo é:
$$
d(s,t) = \min\{\text{number of edges in an } s\text{-}t \text{ path}\}
$$
Se nenhum caminho conecta \(s\) e \(t\), não existe um caminho mínimo finito entre eles.
A busca em largura é adequada para esse cálculo porque explora o grafo de acordo com a distância em relação à origem. Ela verifica todos os vértices a uma aresta antes de verificar os vértices a duas arestas, e assim por diante. Quando todas as arestas têm o mesmo peso, na primeira vez que a BFS alcança um vértice, ela encontra um caminho mínimo até ele.
Proximidade
A proximidade é uma forma de estimar quão perto um nó está dos demais nós que consegue alcançar. A ideia é simples: um nó é mais central quando consegue alcançar outros nós usando, em média, menos passos.
Este analisador usa a normalização aprimorada de Wasserman--Faust para a proximidade. Seja \(R(v)\) o conjunto de vértices alcançáveis a partir de \(v\), excluindo o próprio \(v\), e seja \(n=|V|\) o número total de vértices do grafo. Então, a pontuação é:
$$
C_{WF}(v) = \frac{|R(v)|}{n-1}\cdot\frac{|R(v)|}{\sum_{u \in R(v)} d(v,u)}
$$
Se um nó não consegue alcançar nenhum outro nó, se a distância total é \(0\), ou se o grafo tem menos de dois vértices, sua proximidade é informada como \(0\). Em um grafo conexo, \(|R(v)|=n-1\), portanto o primeiro fator é \(1\) e isso coincide com a fórmula usual baseada nas distâncias alcançáveis.
Uma pontuação de proximidade maior significa que o nó está, em média, mais perto dos nós que consegue alcançar. Em um grafo desconexo, o primeiro fator também ajusta a pontuação pela proporção dos demais vértices que são alcançáveis, para que nós em componentes menores não sejam tratados como se seu componente fosse o grafo inteiro.
Pontes e pontos de articulação
Uma ponte é uma aresta que funciona como um gargalo. Se a remoção da aresta aumenta o número de componentes conexos, essa aresta é uma ponte.
Um ponto de articulação, também chamado de nó crítico ou vértice de corte, é um vértice cuja remoção torna o grafo menos conexo. Remover o vértice também remove todas as arestas incidentes nele.
Esses recursos são importantes porque revelam pontos únicos de falha. Em uma rede de comunicação, uma aresta ponte pode representar uma conexão cuja falha separaria dois grupos. Em uma rede rodoviária, um ponto de articulação pode representar um entroncamento do qual muitas rotas dependem.
A detecção eficiente de pontes e pontos de articulação costuma ser feita com busca em profundidade, usando tempos de descoberta e valores low-link. Em termos simples, o algoritmo acompanha quando cada nó é descoberto pela primeira vez e se uma subárvore consegue alcançar uma parte anterior do grafo sem depender da aresta para o pai.
Caminhos e circuitos eulerianos
A análise euleriana verifica se um grafo tem uma rota que usa cada aresta exatamente uma vez.
Para um grafo ativo conexo:
-
Se todo vértice ativo tem grau par, existe um circuito euleriano.
-
Se exatamente dois vértices ativos têm grau ímpar, existe um caminho euleriano.
-
Se mais de dois vértices ativos têm grau ímpar, não existe caminho euleriano.
O analisador aplica essa regra aos vértices ativos que têm pelo menos uma aresta. Nós isolados ainda contam para os componentes e para os cálculos da tabela, mas são ignorados na verificação da conectividade euleriana ativa.
Isso é importante porque os caminhos eulerianos tratam de usar todas as arestas, não de visitar todos os nós. Um grafo com um nó isolado ainda pode ter um caminho euleriano pela parte do grafo que contém arestas.
Caminhos hamiltonianos
Um caminho hamiltoniano visita cada vértice exatamente uma vez. Isso é diferente de um caminho euleriano, que usa cada aresta exatamente uma vez.
A verificação de caminhos hamiltonianos pode ficar cara à medida que o número de vértices cresce, pois pode ser necessário considerar muitas ordens possíveis. Por isso, este analisador procura um caminho hamiltoniano somente em grafos com \(9\) nós ou menos. Para grafos maiores, a verificação hamiltoniana é ignorada, em vez de produzir um resultado lento ou enganoso.
Árvores e florestas geradoras
Uma árvore é um grafo conexo sem ciclos. Uma árvore geradora de um grafo conexo inclui todos os vértices e usa arestas suficientes para manter o grafo conexo, sem ciclos.
Para um grafo conexo com \(n\) vértices, uma árvore geradora tem:
$$
n - 1
$$
arestas.
Se um grafo é desconexo, não existe uma única árvore geradora para o grafo inteiro. Em vez disso, cada componente conexo pode ter sua própria árvore geradora. Juntas, essas árvores formam uma floresta geradora.
Exemplos práticos de análise de redes em grafos
Exemplo 1: uma rede conexa com quatro nós
Suponha que um grafo tenha estas arestas:
O grafo tem \(4\) vértices e \(4\) arestas. Cada vértice tem grau \(2\):
$$
\deg(A)=2,\quad \deg(B)=2,\quad \deg(C)=2,\quad \deg(D)=2
$$
O caminho mínimo de A até D tem comprimento \(2\), porque A pode chegar a D por B ou por C:
$$
A \rightarrow B \rightarrow D
$$
or
$$
A \rightarrow C \rightarrow D
$$
Como todos os vértices têm grau par e o grafo é conexo, existe um circuito euleriano. Não há arestas ponte, porque toda aresta pertence a um ciclo. O grafo também tem caminhos hamiltonianos, como:
$$
B \rightarrow A \rightarrow C \rightarrow D
$$
Exemplo 2: uma rede desconexa
Suponha que um grafo tenha estas arestas:
Este grafo tem \(5\) vértices, \(3\) arestas e \(2\) componentes conexos:
-
Componente 1: A, B, C
-
Componente 2: D, E
Existe um caminho mínimo de A até C:
$$
A \rightarrow B \rightarrow C
$$
O comprimento do caminho é de \(2\) arestas.
Mas não existe caminho de A até E, porque A e E estão em componentes diferentes. Nesse caso, o resultado do caminho mínimo deve ser interpretado como “desconexo”, não como uma distância muito grande.
Este grafo também é frágil. A aresta A--B é uma ponte, a aresta B--C é uma ponte e a aresta D--E é uma ponte. O vértice B é um ponto de articulação, porque removê-lo separa A e C.
Exemplo 3: caso de um nó isolado
Suponha que um grafo tenha estas arestas:
Suponha também que exista um nó isolado D, sem arestas.
O grafo tem \(4\) vértices, \(2\) arestas e \(2\) componentes. O nó D tem grau \(0\) e não consegue alcançar nenhum outro nó, portanto sua pontuação de proximidade é \(0\).
A parte ativa do grafo que contém arestas é A--B--C. Os vértices A e C têm grau ímpar, enquanto B tem grau par:
$$
\deg(A)=1,\quad \deg(B)=2,\quad \deg(C)=1,\quad \deg(D)=0
$$
A parte ativa que contém arestas tem exatamente dois vértices de grau ímpar, portanto existe um caminho euleriano pelas arestas:
$$
A \rightarrow B \rightarrow C
$$
Este exemplo mostra por que os nós isolados precisam ser interpretados com cuidado. Eles afetam a contagem de componentes e as métricas dos nós, mas o status euleriano do analisador se concentra nos vértices que têm pelo menos uma aresta.
Como interpretar o resultado
A saída do analisador descreve a estrutura do grafo exibido atualmente na área de desenho.
-
Vértices: O número de nós do grafo.
-
Arestas: O número de conexões não direcionadas entre os nós.
-
Componentes: O número de grupos conexos separados.
-
Status de conexão: Se cada nó consegue alcançar todos os outros nós.
-
Grau máximo: O maior número de conexões diretas ligadas a um único nó.
-
Caminho mínimo: A rota com menos arestas entre a origem e o destino selecionados.
-
Proximidade: Uma pontuação normalizada do nó, baseada nas distâncias até os nós alcançáveis e na proporção do grafo que ele consegue alcançar.
-
Pontes: Arestas cuja remoção aumentaria a desconexão.
-
Nós críticos: Pontos de articulação cuja remoção pioraria a conectividade.
-
Resultado euleriano: Se o grafo ativo tem um caminho euleriano, um circuito euleriano, não tem caminho euleriano, não tem arestas ou é desconexo para a análise euleriana.
-
Verificação hamiltoniana: Se um caminho hamiltoniano foi encontrado, não foi encontrado, foi ignorado por causa do tamanho ou é impossível porque não há nós.
Uma contagem baixa de vértices ou arestas significa que o grafo é pequeno. Uma contagem alta de arestas geralmente indica mais rotas alternativas, embora a estrutura seja mais importante do que a contagem de arestas isoladamente. Um grau máximo alto identifica um hub direto, mas um nó de alto grau nem sempre é o mais central pela distância do caminho mínimo.
Uma pontuação de proximidade maior significa que o nó está, em média, mais perto dos outros nós alcançáveis e consegue alcançar uma parcela maior do grafo. A pontuação é exibida com \(3\) casas decimais, portanto diferenças muito pequenas podem ser resultado de arredondamento.
Os resultados de pontes e nós críticos são especialmente úteis para entender a vulnerabilidade. Eles não significam que uma aresta é fisicamente longa ou que um nó é visualmente central. Significam que o grafo fica mais desconexo se essa aresta ou esse nó for removido.
Erros comuns e equívocos
Erro 1: tratar a distância visual como comprimento do caminho
O caminho mínimo baseia-se no número de arestas, não na distância desenhada entre os nós. Mover os nós na área de desenho altera a disposição visual, mas não altera as medidas da teoria dos grafos, a menos que as próprias conexões mudem.
Erro 2: presumir que as arestas são direcionadas ou ponderadas
Este analisador trata todas as arestas como não direcionadas e com o mesmo peso. Ele não modela ruas de mão única, capacidades, tempos de viagem, custos, probabilidades ou distâncias.
Erro 3: confundir caminhos eulerianos com caminhos hamiltonianos
Um caminho euleriano usa cada aresta exatamente uma vez. Um caminho hamiltoniano visita cada vértice exatamente uma vez. Um grafo pode ter um, os dois ou nenhum deles.
Por exemplo, um grafo pode ter um circuito euleriano porque todos os graus são pares, mas ainda assim não ter um caminho hamiltoniano que visite cada vértice exatamente uma vez em uma ordem válida.
Erro 4: esperar várias arestas entre os mesmos nós
O grafo é simples. Se dois nós já estão conectados, conectá-los novamente remove a aresta existente em vez de criar uma aresta paralela. Isso impede que arestas duplicadas alterem os graus ou os resultados eulerianos.
Erro 5: comparar proximidade entre componentes desconexos de forma exagerada
A pontuação de proximidade usa as distâncias até os nós alcançáveis e é ajustada pela proporção de todos os outros vértices que podem ser alcançados. Considere os componentes e a alcançabilidade junto com a proximidade antes de tirar conclusões sobre a rede inteira.
Erro 6: esperar resultados hamiltonianos para grafos grandes
A verificação de caminhos hamiltonianos é intencionalmente limitada. Se o grafo tiver mais de \(9\) nós, o analisador ignora a busca hamiltoniana. Um resultado ignorado não significa que não exista caminho hamiltoniano; significa que o grafo está fora do limite de busca da calculadora.
Quando usar a análise de redes em grafos
Use esse tipo de análise de grafos quando quiser entender a estrutura de conexões de uma rede simples.
Ela é especialmente útil para:
-
Aprender visualmente conceitos da teoria dos grafos
-
Verificar se uma rede é conexa ou fragmentada
-
Encontrar caminhos mínimos com menos arestas
-
Identificar hubs pelo grau
-
Comparar a centralidade local por meio da proximidade
-
Encontrar arestas ponte e nós críticos
-
Explorar as regras de caminhos e circuitos eulerianos
-
Testar caminhos hamiltonianos em grafos pequenos
-
Demonstrar BFS, árvores geradoras e florestas geradoras
Ela é menos adequada quando a rede exige direção, pesos nas arestas, arestas repetidas, laços ou otimização em grande escala.
Limitações e pontos importantes
Esta análise é exata para o grafo que você desenha, mas só é tão significativa quanto o modelo de grafo escolhido.
As principais limitações incluem:
-
As arestas são não direcionadas.
-
As arestas não são ponderadas.
-
Laços não são compatíveis.
-
Arestas paralelas entre o mesmo par de nós não são compatíveis.
-
Os caminhos mínimos contam apenas arestas.
-
As posições dos nós afetam o desenho, mas não os cálculos.
-
A proximidade é exibida com \(3\) casas decimais.
-
Nós isolados são incluídos nos resultados de componentes e da tabela de nós.
-
Nós isolados são ignorados na verificação da conectividade euleriana ativa.
-
A busca por caminhos hamiltonianos é ignorada em grafos com mais de \(9\) nós.
-
Coordenadas numéricas personalizadas, rótulos personalizados, arestas direcionadas e pesos das arestas não fazem parte das entradas visíveis da calculadora.
Para explorações em sala de aula, essas limitações mantêm o modelo de grafo simples e mais fácil de analisar. Para projeto profissional de redes, planejamento de transporte, cibersegurança, engenharia ou pesquisa operacional, um grafo simples e não ponderado pode ser apenas uma primeira aproximação. Quando as decisões afetam dinheiro, segurança, infraestrutura ou registros oficiais, verifique o modelo de grafo e consulte um profissional qualificado ou um método específico da área.
Como usar esta calculadora
-
Carregue um grafo de exemplo ou comece com o grafo padrão exibido na área de desenho.
-
Escolha um modo de edição: mover nós, adicionar nós, conectar nós ou excluir nós.
-
Use a área de desenho para ajustar a estrutura da rede.
-
Selecione um vértice de origem e um vértice de destino para a análise do caminho mínimo.
-
Consulte o resumo do grafo, os cartões de métricas, o caminho mínimo, o status euleriano, o status hamiltoniano e a tabela de nós.
-
Use os botões de ação para destacar o caminho mínimo, animar a BFS, destacar uma árvore ou floresta geradora ou limpar o grafo.
-
Baixe a visualização atual do grafo como PNG se precisar de uma imagem da rede.
Perguntas frequentes
O caminho mínimo usa a distância desenhada entre os nós?
Não. O caminho mínimo usa o número de arestas entre a origem e o destino selecionados. Uma aresta visualmente longa e uma visualmente curta contam, ambas, como uma aresta.
O que significa não haver caminho entre dois vértices?
Isso significa que a origem e o destino selecionados estão em componentes conexos diferentes ou que um dos vértices selecionados está ausente. Nesse caso, o grafo não contém uma rota de um vértice selecionado ao outro.
O que significa uma pontuação de proximidade alta?
Uma pontuação de proximidade alta significa que o nó consegue alcançar outros nós alcançáveis usando, em média, menos arestas, além de alcançar uma parcela maior do grafo. Em grafos desconexos, o fator de Wasserman--Faust impede que um componente pequeno seja tratado como uma classificação global completa.
Qual é a diferença entre uma ponte e um nó crítico?
Uma ponte é uma aresta cuja remoção aumenta o número de componentes conexos. Um nó crítico, também chamado de ponto de articulação, é um vértice cuja remoção aumenta o número de componentes conexos.
Por que o resultado euleriano ignora nós isolados?
Caminhos e circuitos eulerianos tratam de usar as arestas exatamente uma vez. Um nó isolado não tem aresta para usar, por isso o analisador verifica o status euleriano na parte ativa do grafo que contém arestas.
Por que a verificação hamiltoniana é ignorada para mais de 9 nós?
A busca por caminhos hamiltonianos pode exigir a verificação de muitas ordens possíveis de vértices. O analisador limita a busca exata a grafos pequenos para manter a ferramenta responsiva. Um resultado ignorado não prova que um caminho hamiltoniano existe ou não existe.
Fontes e referências
Livros e manuais
-
Robert Sedgewick e Kevin Wayne. Algorithms. 4ª ed., Addison-Wesley, 2011. Seção 4.1, “Undirected Graphs”. Site do livro consultado em 4 de julho de 2026. https://algs4.cs.princeton.edu/41graph/
-
Jay Abramson et al. Contemporary Mathematics. OpenStax, 2023. Capítulo 12, “Graph Theory”, especialmente as seções 12.1, 12.5, 12.6, 12.10 e os conceitos principais do Capítulo 12. Consultado em 4 de julho de 2026. https://openstax.org/books/contemporary-mathematics/pages/12-1-graph-basics
-
Joy Morris. Combinatorics. Mathematics LibreTexts. Seção 13.2, “Hamilton Paths and Cycles”. Consultado em 4 de julho de 2026. https://math.libretexts.org/Bookshelves/CombinatoricsandDiscreteMathematics/Combinatorics%28Morris%29/03%3AGraphTheory/13%3AEulerandHamilton/13.02%3AHamiltonPathsand_Cycles
Documentação técnica e on-line
-
Desenvolvedores do NetworkX. “closeness_centrality”. NetworkX 3.6.1 Documentation. Consultado em 4 de julho de 2026. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.closeness_centrality.html
