Caminhos, Ciclos e Conexidade

Como saber se dois pontos de uma rede estão conectados, e por qual caminho mais curto? Até agora estudamos grafos como objetos estáticos — conjuntos de vértices e arestas. Mas a pergunta mais comum que fazemos sobre um grafo não é sobre sua estrutura em si: é sobre navegar por ele, partindo de um vértice e percorrendo arestas para chegar a outros.

Isso nos leva aos conceitos de passeios, trajetos, caminhos e ciclos — e à fundamental noção de conexidade.

Por que Caminhos e Ciclos Importam?

#

Navegar em um grafo — e saber se essa navegação é sequer possível — é a base de problemas centrais em ciência da computação e matemática aplicada:

• Roteamento de redes: protocolos de roteamento (como os usados na internet) precisam encontrar caminhos entre roteadores, e o conceito de distância mais curta define diretamente o custo de uma rota.
• Sistemas distribuídos: antes de rodar qualquer algoritmo distribuído, é comum verificar se a rede de máquinas é conexa — se não for, o sistema se divide em partições que não conseguem se comunicar.
• Alocação de recursos: problemas de emparelhamento (como designar operários a máquinas, ou candidatos a vagas) são modelados como grafos bipartidos, e resolvê-los depende de entender a estrutura desses grafos.
• Verificação de circuitos e protocolos: detectar ciclos em um grafo de dependências é o que evita, por exemplo, deadlocks em sistemas concorrentes ou referências circulares em builds de software.

Passeios, Trajetos e Caminhos

#

Existem diferentes maneiras de percorrer um grafo, e as distinções entre elas importam:

A hierarquia é: todo caminho é um trajeto, e todo trajeto é um passeio. O inverso não é necessariamente verdadeiro.

Para fixar essas ideias, vamos usar o mesmo grafo \(G\) em vários exemplos ao longo deste artigo — a ideia é observar como os mesmos oito vértices sustentam conceitos cada vez mais específicos, de passeio até centro do grafo. Partimos do grafo \(G\) a seguir:

A figura abaixo destaca \(P_1\) sobre o grafo \(G\), evidenciando onde o vértice \(c\) e a aresta \(\{c,d\}\) se repetem:

Passeios e Trajetos Fechados

#

Um passeio (ou trajeto, ou caminho) é fechado se o vértice inicial coincide com o vértice final, isto é, \(v_0 = v_k\).

O comprimento de um ciclo é dado pelo seu número de arestas (equivalente ao seu número de vértices distintos).

Ciclos de comprimento 3 são triângulos.

O grafo \(G\) tem exemplos dos dois tipos: um ciclo de comprimento 4 (\(a,b,g,h,a\)) e um triângulo, que é um ciclo de comprimento 3 (\(a,b,h,a\)):

Aplicação: detectando dependências circulares

Ciclos não são só um conceito abstrato — eles aparecem (e causam dor de cabeça) sempre que um sistema de software modela dependências entre componentes como um grafo dirigido: se o módulo \(A\) depende de \(B\), desenhamos uma aresta \(A \to B\). Um projeto só compila (ou importa, ou instala) se esse grafo de dependências não tiver ciclos — caso contrário, “o que carregar primeiro” vira uma pergunta sem resposta.

import networkx as nx

deps = nx.DiGraph()
deps.add_edges_from([
    ("app", "auth"),
    ("app", "database"),
    ("auth", "database"),
    ("database", "config"),
    ("config", "utils"),
    ("utils", "auth"),  # fecha o ciclo auth -> database -> config -> utils -> auth
])

try:
    ciclo = nx.find_cycle(deps)
    print("Dependência circular encontrada:")
    for origem, destino in ciclo:
        print(f"  {origem} -> {destino}")
except nx.NetworkXNoCycle:
    print("Nenhum ciclo — grafo de dependências é um DAG, build seguro.")

Dependência circular encontrada:
  auth -> database
  database -> config
  config -> utils
  utils -> auth

O grafo abaixo mostra as dependências declaradas, com o ciclo encontrado destacado em laranja:

O ciclo não é óbvio de enxergar módulo por módulo: auth importa database, que importa config, que importa utils, que por sua vez importa auth de volta. É exatamente esse tipo de dependência circular indireta que ferramentas como pip, npm ou sistemas de build detectam automaticamente com busca de ciclos em um grafo, em vez de depender de alguém perceber o problema manualmente.

O que cada ferramenta faz ao encontrar um ciclo varia: cargo (Rust) e a maioria dos build systems compilados recusam o build direto, já que compilar exige uma ordem estrita entre dependências; o make clássico detecta, avisa e quebra o ciclo arbitrariamente para seguir em frente; e linguagens interpretadas como Python e Node.js toleram o import circular em tempo de execução, entregando um módulo parcialmente inicializado no ponto em que o ciclo fecha — uma fonte clássica de bugs sutis. Por trás de todas essas estratégias está o mesmo fato de teoria dos grafos: uma ordem válida de build, instalação ou import é uma ordenação topológica, e ordenação topológica só existe se o grafo dirigido for acíclico — por isso a primeira coisa que essas ferramentas fazem é checar se ordenar é sequer possível.

Conexidade

#

Até aqui falamos em “existe um caminho entre \(v\) e \(w\)” de forma solta. Vamos formalizar essa ideia par a par antes de aplicá-la ao grafo inteiro.

Considere agora o grafo \(H\) abaixo, formado por um agrupamento de seis vértices \(\{p,q,r,s,t,u\}\) e, separadamente, um triângulo \(\{x,y,z\}\):

O grafo \(H\) do exemplo acima é desconexo — mas cada uma de suas duas partes, isoladamente, é conexa. Isso nos leva à definição de componente conexo.

Denotamos por \(\omega(G)\) o número de componentes conexos de \(G\). Um grafo é conexo se e somente se \(\omega(G) = 1\).

Voltando ao grafo \(H\), destacamos abaixo seus dois componentes conexos:

A figura abaixo mostra \(G’\), com cada componente conexo em uma cor:

E o grafo \(G\) que vimos na seção anterior (vértices \(\{a,\ldots,h\}\))? Todo par de vértices de \(G\) é conexo — por exemplo, \(P_4\) já mostrou um caminho entre \(g\) e \(d\) passando por todos os demais vértices. Logo \(G\) é conexo e \(\omega(G) = 1\).

Distância, Excentricidade e Diâmetro

#

Com o conceito de conexidade em mãos, podemos medir “distâncias” dentro de um grafo:

As definições a seguir — excentricidade, diâmetro e centro — pressupõem que \(G\) é um grafo conexo (caso contrário, algum \(e(v)\) poderia ser infinito).

Vamos calcular essas três medidas no grafo \(G\) (vértices \(\{a,\ldots,h\}\)) que já usamos nas seções anteriores.

A figura a seguir mostra a excentricidade de cada vértice e destaca o centro:

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    ("a","b"), ("a","h"), ("b","h"), ("b","g"), ("g","h"),
    ("b","c"), ("b","f"), ("c","f"), ("c","e"), ("e","f"), ("c","d"),
])

print("Excentricidades:", nx.eccentricity(G))
print("Diâmetro:", nx.diameter(G))
print("Centro:", nx.center(G))

Excentricidades: {'a': 3, 'b': 2, 'h': 3, 'g': 3, 'c': 2, 'f': 2, 'e': 3, 'd': 3}
Diâmetro: 3
Centro: ['b', 'c', 'f']

Calculando distâncias: a busca em largura

#

Nos exemplos acima, lemos as distâncias no desenho de \(G\), e o networkx fez a mesma conta em uma linha. Mas como se calcula a distância entre dois vértices de um grafo com milhões deles? Quando as arestas não têm pesos, a resposta é a busca em largura (BFS, do inglês breadth-first search).

A ideia é explorar o grafo em camadas a partir de uma origem \(v\): primeiro o próprio \(v\), à distância 0; depois todos os seus vizinhos, à distância 1; depois os vizinhos desses vizinhos que ainda não apareceram, à distância 2; e assim por diante. Uma fila garante essa ordem: cada vértice descoberto entra no fim da fila, e os vértices são processados na ordem em que entraram.

Por que a distância marcada é a menor possível? Os vértices saem da fila em ordem crescente de distância — todos os da camada \(k\) antes de qualquer um da camada \(k+1\) —, então a primeira vez que um vértice \(w\) aparece é a partir de um vértice da camada mais próxima possível da origem. E o custo é baixo: cada vértice entra na fila uma única vez, e cada aresta é examinada duas vezes, uma a partir de cada extremo, o que dá tempo \(O(n + m)\).

Aplicada ao grafo \(G\) a partir de \(a\), a BFS reproduz as distâncias que calculamos à mão:

from collections import deque

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    ("a", "b"), ("a", "h"), ("b", "h"), ("b", "g"), ("g", "h"),
    ("b", "c"), ("b", "f"), ("c", "f"), ("c", "e"), ("e", "f"), ("c", "d"),
])


def distancias(G, origem):
    """Distância de origem a cada vértice alcançável, pela busca em largura."""
    dist = {origem: 0}
    fila = deque([origem])
    while fila:
        v = fila.popleft()
        for w in G.neighbors(v):
            if w not in dist:  # primeira vez que w aparece
                dist[w] = dist[v] + 1
                fila.append(w)
    return dist


d_a = distancias(G, "a")
print(d_a)
# Saída: {'a': 0, 'b': 1, 'h': 1, 'g': 2, 'c': 2, 'f': 2, 'e': 3, 'd': 3}
print(max(d_a.values()))  # 3, a excentricidade de a

A figura abaixo desenha \(G\) nessas camadas. As arestas grossas são as que a busca usou para descobrir cada vértice; as tracejadas foram examinadas e descartadas, porque o vértice do outro lado já tinha distância marcada:

A maior distância encontrada é a excentricidade de \(a\). Rodando a BFS a partir de cada vértice, obtemos todas as excentricidades — e, com elas, o diâmetro e o centro — em tempo \(O(n(n + m))\). A mesma busca volta mais adiante, neste artigo, para testar se um grafo é bipartido, e no artigo sobre árvores, onde produz uma árvore geradora. Ela foi descrita por Konrad Zuse em 1945, numa tese que só seria publicada em 1972, e reinventada por Edward F. Moore em 1959 para achar a saída de labirintos (veja o verbete Breadth-first search).

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([("A", "B", 4), ("A", "C", 1), ("C", "D", 1), ("D", "B", 1)])

print(nx.shortest_path(G, "A", "B"))         # ['A', 'B'] (sem pesos: BFS)
print(nx.dijkstra_path(G, "A", "B"))         # ['A', 'C', 'D', 'B']
print(nx.dijkstra_path_length(G, "A", "B"))  # 3

Grafos Especiais

#

Alguns grafos aparecem com tanta frequência em aplicações e exemplos que vale a pena nomeá-los e reconhecê-los de imediato.

Os dois casos extremos, lado a lado:

Ciclos e Caminhos

#

Os primeiros ciclos da família \(C_n\):

E os primeiros caminhos da família \(P_n\):

Grafos Bipartidos

#

Uma classe importante de grafos é aquela em que os vértices podem ser divididos em dois grupos, com arestas apenas entre os grupos.

Uma forma útil de visualizar um grafo bipartido é desenhar \(V_1\) e \(V_2\) como duas colunas separadas, deixando explícito que toda aresta cruza de uma coluna para a outra:

Um exemplo pequeno é \(K_{2,3}\), com todas as \(2 \times 3 = 6\) arestas possíveis entre os dois lados:

Exemplos de grafos bipartidos:

• Caminhos \(P_n\) (para \(n \geq 2\)): vértices de posição par em \(V_1\), ímpares em \(V_2\)
• Ciclos pares \(C_{2k}\): vértices alternados em \(V_1\) e \(V_2\)

A figura a seguir mostra \(C_4\) desenhado de duas formas — como polígono e como bipartição — e traz \(C_5\) como desafio: tente achar uma bipartição válida para ele (spoiler: não existe, como o teorema a seguir vai explicar).

Caracterização de Grafos Bipartidos

#

É um problema importante decidir se um grafo é bipartido ou não. O teorema a seguir mostra que basta procurar por ciclos ímpares.

Prova (\(\Rightarrow\)): Seja \(G\) um grafo bipartido com bipartição \((V_1, V_2)\), e seja \(C = v_1, v_2, \ldots, v_k, v_1\) um ciclo em \(G\). Suponha \(v_1 \in V_1\). Como \(V_1\) e \(V_2\) são independentes, cada aresta do ciclo troca de lado: \(v_2 \in V_2\), \(v_3 \in V_1\), \(v_4 \in V_2\), e assim sucessivamente — de forma geral, \(v_{2i-1} \in V_1\) e \(v_{2i} \in V_2\). Como \((v_k, v_1) \in E\) e \(v_1 \in V_1\), o vértice \(v_k\) precisa estar em \(V_2\) (pois \(G\) é bipartido, e uma aresta nunca liga dois vértices do mesmo lado). Logo \(k = 2i\) para algum \(i\), ou seja, \(k\) é par — e portanto \(C\) é um ciclo par. Portanto, como isso vale para qualquer ciclo de \(G\), um grafo bipartido não contém ciclo ímpar.

Prova (\(\Leftarrow\)): Suponha agora que \(G\) não contém nenhum ciclo ímpar. Podemos supor \(G\) conexo: se não for, construímos uma bipartição para cada componente conexo e juntamos os lados correspondentes, já que nenhuma aresta liga componentes diferentes. Vamos construir uma bipartição de \(G\) explicitamente.

Seja \(v\) um vértice qualquer de \(G\), e defina:

Como \(G\) é conexo, todo vértice está a uma distância finita de \(v\), par ou ímpar (nunca as duas coisas), temos \(V_1 \cup V_2 = V(G)\) e \(V_1 \cap V_2 = \emptyset\). Falta mostrar que \((V_1, V_2)\) é de fato uma bipartição, isto é, que não existe aresta dentro de \(V_1\) nem dentro de \(V_2\).

Suponha, por contradição, que isso seja falso: existe uma aresta \((w_i, w_j)\) com \(w_i, w_j \in V_1\) (o caso de uma aresta dentro de \(V_2\) é análogo). Sejam \(P_i\) e \(P_j\) os caminhos mais curtos de \(v\) até \(w_i\) e de \(v\) até \(w_j\), respectivamente — ambos de comprimento par, já que \(w_i, w_j \in V_1\). Seja \(z\) o vértice comum a \(P_i\) e \(P_j\) mais distante de \(v\) (existe pelo menos o próprio \(v\) em comum). A figura abaixo esquematiza essa construção:

O subcaminho de \(P_i\) que vai de \(v\) até \(z\), denotado \(P_i(v{-}z)\), tem o mesmo comprimento do subcaminho \(P_j(v{-}z)\) — caso contrário, um dos dois caminhos não seria o mais curto até seu respectivo destino (bastaria trocar o trecho mais longo pelo trecho mais curto do outro caminho para obter um atalho). Como \(P_i\) e \(P_j\) têm comprimento par no total, e as partes de \(v\) até \(z\) têm o mesmo comprimento, os subcaminhos restantes \(P_i(z{-}w_i)\) e \(P_j(z{-}w_j)\) têm a mesma paridade entre si — ambos pares ou ambos ímpares.

Mas existe a aresta \((w_i, w_j)\) por hipótese. Logo o percurso \(P_i(z{-}w_i) \cup (w_i,w_j) \cup P_j(z{-}w_j)\) — de \(z\) até \(w_i\), depois até \(w_j\) pela aresta, e de volta a \(z\) por \(P_j\) — forma um ciclo de comprimento \(\text{comp}(P_i(z{-}w_i)) + 1 + \text{comp}(P_j(z{-}w_j))\). Como as duas parcelas têm a mesma paridade, essa soma é sempre ímpar (par + par + 1, ou ímpar + ímpar + 1). Isso produz um ciclo ímpar em \(G\) — contradizendo a hipótese de que \(G\) não contém ciclo ímpar.

Essa contradição mostra que a aresta \((w_i, w_j)\) não pode existir (e, de forma análoga, nenhuma aresta dentro de \(V_2\) pode existir). Logo \((V_1, V_2)\) é de fato uma bipartição de \(G\), ou seja, \(G\) é bipartido.

Portanto, com as duas direções, um grafo é bipartido se e somente se não contém nenhum ciclo de comprimento ímpar, que é o que queríamos demonstrar. \(\blacksquare\)

Aplicação: a prova vira algoritmo

A construção usada na prova (\(\Leftarrow\)) — colorir cada vértice pela paridade de sua distância até um vértice de referência — não é só um argumento teórico: é literalmente o algoritmo que bibliotecas de grafos usam para testar bipartição. Implementando a mesma ideia com a busca em largura (BFS) que vimos na seção de distâncias:

from collections import deque
import networkx as nx

def bipartir(G, origem):
    """V1 = distância par até origem, V2 = distância ímpar — a mesma
    construção usada na prova do teorema."""
    cor = {origem: 0}
    fila = deque([origem])
    while fila:
        v = fila.popleft()
        for viz in G.neighbors(v):
            if viz not in cor:
                cor[viz] = 1 - cor[v]
                fila.append(viz)
            elif cor[viz] == cor[v]:
                return None  # aresta dentro do mesmo lado: não é bipartido
    V1 = sorted(v for v, c in cor.items() if c == 0)
    V2 = sorted(v for v, c in cor.items() if c == 1)
    return V1, V2

print("C6:", bipartir(nx.cycle_graph(6), 0))
print("C5:", bipartir(nx.cycle_graph(5), 0))

C6: ([0, 2, 4], [1, 3, 5])
C5: None

Para \(C_6\) (ciclo par), a função devolve exatamente a bipartição alternada esperada: vértices em posição par de um lado, ímpar do outro — mostrada na figura abaixo. Para \(C_5\) (ciclo ímpar), a BFS eventualmente encontra uma aresta entre dois vértices da mesma cor — a mesma contradição explorada na prova — e a função retorna None, confirmando que não existe bipartição.

A biblioteca networkx já traz essa checagem pronta em nx.is_bipartite, que concorda com a nossa implementação:

import networkx as nx

print(nx.is_bipartite(nx.cycle_graph(6)))  # True
print(nx.is_bipartite(nx.cycle_graph(5)))  # False

import networkx as nx

G = nx.karate_club_graph()

print("Conexo:", nx.is_connected(G))
print("Diâmetro:", nx.diameter(G))
print("Centro:", nx.center(G))
print("Bipartido:", nx.is_bipartite(G))

Conexo: True
Diâmetro: 5
Centro: [0, 1, 2, 3, 8, 13, 19, 31]
Bipartido: False

Exercícios

#

Os exercícios a seguir aplicam os conceitos de passeio, trajeto, caminho e bipartição vistos neste artigo, em ordem crescente de dificuldade.

Exercício 1: Classificação de sequências

Enunciado: Classifique cada sequência abaixo como passeio, trajeto, caminho ou nenhum desses, em um grafo com vértices \(\{1,2,3,4,5\}\) e arestas \(\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{1,3\}, \{3,5\}\):

(a) \(1, 2, 3, 4, 5, 3, 1\) (b) \(1, 3, 2, 4\) (c) \(1, 2, 3, 5, 4\) (d) \(1, 3, 5, 4, 3, 2\)

Solução: (a) É um trajeto (fechado) — a sequência percorre as 6 arestas do grafo, cada uma exatamente uma vez: \(\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{3,5\}, \{1,3\}\). Como nenhuma aresta se repete, é um trajeto — e como \(v_0 = v_6 = 1\), é fechado. Não é um caminho nem um ciclo, pois o vértice 3 é visitado duas vezes (nas posições 3 e 6). (b) Não é válido — não existe aresta \(\{2,4\}\). (c) É um caminho — nenhum vértice se repete e todas as arestas existem: \(\{1,2\}, \{2,3\}, \{3,5\}, \{5,4\}\). ✓ (d) É um trajeto — nenhuma aresta se repete, mas o vértice 3 aparece duas vezes.

O grafo usado no exercício, para visualizar as sequências acima:

Resumo

#

Próximos Passos

#

Respondemos à pergunta de abertura: sabemos agora reconhecer se dois pontos de um grafo estão conectados, medir a distância mais curta entre eles e decidir se a estrutura inteira é bipartida. Mas passeios, ciclos e conexidade não respondem a uma pergunta igualmente importante: qual é a menor quantidade de arestas capaz de manter um grafo conexo, sem nenhum ciclo sobrando? Essa é a pergunta que motiva as árvores, tema do próximo artigo da série — a estrutura mais fundamental da ciência da computação.