Grafos: Uma Linguagem para Modelar Conexões

Imagine que você está de férias na cidade de Königsberg, na Prússia do século XVIII. O rio Pregel divide a cidade em quatro regiões distintas, conectadas por sete pontes. O desafio que ocupa a mente dos moradores é aparentemente simples: seria possível dar um passeio pela cidade cruzando cada uma das sete pontes exatamente uma vez?

Essa pergunta, que parece um passatempo trivial, deu origem a um dos campos mais prolíficos e aplicados da matemática moderna: a teoria dos grafos.

O Problema das Pontes de Königsberg

#

Em 1736, o matemático suíço Leonhard Euler recebeu esse desafio e percebeu que a questão geográfica — as posições exatas das pontes, as distâncias entre as ilhas — era irrelevante. O que importava era apenas a estrutura das conexões: quais regiões estavam ligadas por pontes e quantas pontes as conectavam.

O mapa abaixo mostra a disposição real das sete pontes sobre o rio Pregel — o ponto de partida do raciocínio de Euler.

Euler abstraiu o problema: representou cada região como um ponto e cada ponte como uma linha conectando dois pontos. Com essa representação, a pergunta se tornou: é possível percorrer todas as linhas desse diagrama exatamente uma vez, em um único trajeto contínuo?

O grafo abaixo representa essa abstração — nós no lugar das regiões, arestas no lugar das pontes. As duas arestas paralelas entre A e B (e entre B e D) representam as duas pontes que existiam entre essas regiões.

A resposta de Euler foi não — e ele demonstrou isso com um argumento elegante. Observe que, a cada vez que o passeante entra numa região por uma ponte, ele precisa sair por outra. Toda passagem por uma região intermediária consome, portanto, um par de pontes. Isso significa que qualquer região que não seja ponto de partida nem de chegada precisa ter um número par de pontes. Apenas o início e o fim do percurso podem ter número ímpar. Em Königsberg, porém, todos os quatro pontos têm número ímpar de pontes — o que exigiria, simultaneamente, quatro pontos de início/fim. Impossível num único trajeto contínuo.

Mais precisamente: um percurso que atravessa cada aresta exatamente uma vez chama-se trajeto euleriano. Se retorna ao ponto de partida, é um circuito euleriano — e para existir, todos os vértices precisam ter grau par. Se começa e termina em pontos distintos, exatamente dois vértices podem ter grau ímpar. Em Königsberg, com quatro vértices de grau ímpar, nenhuma das duas condições é satisfeita. No artigo Caminhos, Ciclos e Conexidade, formalizaremos a distinção entre passeio, trajeto e caminho; em Grafos Eulerianos e Hamiltonianos, veremos a demonstração rigorosa desse resultado e suas generalizações.

Esse trabalho, publicado no artigo Solutio problematis ad geometriam situs pertinentis (1736), é considerado o nascimento da teoria dos grafos (veja o verbete Seven Bridges of Königsberg).

O Que É um Grafo?

#

A ideia central que Euler desenvolveu é extraordinariamente simples e poderosa:

Nada mais. Sem geometria, sem coordenadas, sem distâncias. Apenas a estrutura pura de quem está conectado a quem.

Essa abstração, que parece um empobrecimento, é na verdade uma riqueza: ela permite que a mesma teoria se aplique a domínios completamente diferentes.

Outro Exemplo: o Teorema das Quatro Cores

#

As Pontes de Königsberg não são o único problema clássico que a linguagem dos grafos esclarece. Considere um mapa geográfico qualquer — um mapa político, um mapa de bairros, um tabuleiro dividido em regiões. Queremos colorir as regiões de modo que dois países (ou bairros) que fazem fronteira nunca tenham a mesma cor. Quantas cores são necessárias?

Essa questão foi levantada em 1852 pelo matemático Francis Guthrie, enquanto coloria um mapa dos condados da Inglaterra, e ficou em aberto por 124 anos. Intuitivamente, parece que quatro cores deveriam ser suficientes para qualquer mapa planar — mas provar isso revelou-se extraordinariamente difícil.

A conexão com a teoria dos grafos é imediata: basta representar cada região como um vértice e traçar uma aresta entre dois vértices sempre que as regiões correspondentes compartilham uma fronteira. O problema de coloração de mapas torna-se então um problema de coloração de grafos — atribuir cores aos vértices de modo que vértices adjacentes recebam cores diferentes.

A figura a seguir ilustra essa abstração com um mapa de quatro regiões (A, B, C e D) mutuamente adjacentes, cada uma colorida com uma cor distinta, e o grafo correspondente onde todas as arestas refletem as adjacências do mapa.

Nesse exemplo específico, as quatro regiões são todas mutuamente adjacentes: A faz fronteira com B, C e D; B faz fronteira com A, C e D; e assim por diante. O grafo resultante é o K₄ — o grafo completo em quatro vértices — em que todo par de vértices está conectado por uma aresta. Para colori-lo, precisamos obrigatoriamente de quatro cores.

O que torna esse teorema notável é a sua prova. Em 1976, Kenneth Appel e Wolfgang Haken publicaram uma demonstração que reduziu o problema a um conjunto finito (mas enorme) de casos a verificar — e usaram um computador para checar todos eles. Foi a primeira prova matemática importante dependente de computador, e gerou um debate filosófico sobre o que significa “provar” algo em matemática que se estende até hoje (veja o verbete Four color theorem).

Dois fatos geométricos estão por trás do enunciado:

• Em qualquer mapa planar, é impossível ter cinco regiões mutuamente adjacentes (o que exigiria o grafo K₅, que não é planar).
• O grafo K₄ que vimos acima é planar — pode ser desenhado no plano sem cruzamentos — e mostra que quatro cores são às vezes necessárias.

Esses dois fatos, porém, não provam que quatro cores bastam: um mapa pode precisar de mais cores do que o seu maior grupo de regiões mutuamente vizinhas sugere. Um exemplo pequeno é uma região central cercada por um anel de cinco regiões. Nesse mapa não há quatro regiões mutuamente vizinhas, e mesmo assim são necessárias quatro cores — o anel, com um número ímpar de regiões, já gasta três, e a região central, vizinha de todas elas, precisa de uma quarta. É justamente essa intuição fácil, a de que tudo se resume a quantas regiões se tocam ao mesmo tempo, que ninguém conseguiu transformar em prova durante os 124 anos em que o problema ficou aberto.

A teoria dos grafos planares e o critério de planaridade de Kuratowski serão discutidos em detalhes no artigo Grafos Planares, que também volta à coloração: o Teorema das Quatro Cores enunciado para grafos, uma prova de que seis cores sempre bastam e aplicações em escalonamento.

Por Que Grafos São Tão Úteis?

#

A teoria dos grafos é uma linguagem universal para modelar relações entre objetos. A chave é perceber que, em muitos problemas reais, o que importa não são os objetos em si, mas as conexões entre eles.

Ciência da Computação

#

• Redes de computadores: roteadores são vértices, cabos são arestas. Encontrar o caminho mais curto entre dois roteadores é um problema de grafos.
• Sistemas operacionais: grafos de dependência entre processos ajudam a detectar situações de bloqueio mútuo (deadlocks).
• Compiladores: a análise de fluxo de controle de um programa usa grafos direcionados.
• Banco de dados: o modelo entidade-relacionamento é essencialmente um grafo.
• Algoritmos de busca: BFS (busca em largura) e DFS (busca em profundidade) são algoritmos sobre grafos.

Engenharia e Logística

#

• Redes elétricas: identificar circuitos, analisar fluxo de energia.
• Planejamento de rotas: o famoso Problema do Caixeiro Viajante pergunta qual é o ciclo hamiltoniano de menor custo em um grafo ponderado.
• Projetos de construção: grafos de precedência determinam a ordem das atividades (método PERT/CPM — Program Evaluation and Review Technique / Critical Path Method).

Ciências Naturais e Sociais

#

• Química: moléculas são grafos onde átomos são vértices e ligações químicas são arestas. Isômeros estruturais têm os mesmos átomos ligados de formas diferentes — seus grafos não são isomorfos —, e reconhecer se duas fórmulas estruturais descrevem a mesma molécula é um problema de isomorfismo de grafos.
• Biologia: redes de interação proteína-proteína, redes tróficas (quem come quem), árvores filogenéticas.
• Sociologia: redes sociais, onde pessoas são vértices e amizades são arestas. O conceito de “seis graus de separação” é uma afirmação sobre o diâmetro de um grafo.
• Epidemiologia: modelagem da propagação de doenças em redes de contato.

Internet e Redes Sociais

#

A própria World Wide Web é um grafo enorme — mas com uma diferença crucial em relação ao grafo de Königsberg e ao grafo de coloração de mapas, ambos não-dirigidos: é um grafo dirigido. Cada página é um vértice e cada hyperlink é uma aresta com direção. Se a Página A aponta para a Página B, isso não implica que B aponta para A. A direção importa: o número de páginas que apontam para um vértice (seu grau de entrada) é uma medida direta de quão referenciada — e potencialmente relevante — aquela página é.

O grafo a seguir ilustra uma mini-web com cinco páginas. As setas indicam a direção dos hyperlinks, e o tamanho de cada nó é proporcional ao PageRank calculado pelo algoritmo — antecipando um resultado que não é imediatamente óbvio.

Nesse exemplo, a Página \(B\) recebe links de três páginas distintas (\(A\), \(C\) e \(E\)) — é a mais referenciada em termos de grau de entrada. Já a Página \(E\) não recebe nenhum link de entrada. Existe ainda um ciclo: seguindo \(A \to C \to D \to A\), o navegante retorna ao ponto de partida. Essas propriedades — grau de entrada, ausência de links de entrada e ciclos — são exatamente o que o PageRank modela, com resultados que às vezes surpreendem.

O PageRank é o algoritmo desenvolvido por Larry Page e Sergey Brin na Universidade de Stanford em 1996, que se tornou a base do mecanismo de busca do Google. A ideia central é o modelo do surfista aleatório: imagine um internauta que, a cada passo, escolhe aleatoriamente um dos links da página atual e o segue. O PageRank de uma página é a probabilidade de esse surfista estar nela após um número muito grande de passos — ou seja, uma medida de quão frequentemente a página é visitada no longo prazo.

onde \(d \approx 0{,}85\) é o fator de amortecimento (a probabilidade de continuar clicando em vez de “recomeçar” numa página aleatória), \(N\) é o total de páginas e \(L(v)\) é o número de links que saem de \(v\). Páginas que recebem muitos links de páginas elas próprias bem ranqueadas acumulam alto PageRank — um processo iterativo que converge para uma distribuição estável.

A animação abaixo mostra esse processo de convergência: os círculos representam páginas, o tamanho de cada círculo indica o PageRank calculado na iteração atual e as setas representam os hyperlinks.

Calculando o PageRank da nossa mini-web. Para aplicar o algoritmo ao grafo do diagrama acima, precisamos construir a matriz de transição \(M\), uma matriz \(5 \times 5\) onde a entrada \(M_{ij}\) representa a fração do PageRank da página \(j\) que é transferida para a página \(i\) a cada passo. A regra de construção é direta: se a página \(j\) possui \(k\) links de saída e um deles aponta para \(i\), então \(M_{ij} = \frac{1}{k}\); caso contrário, \(M_{ij} = 0\). Como cada página distribui integralmente seu peso entre seus links de saída, cada coluna de \(M\) soma 1.

Numerando os nós como \(A=0\), \(B=1\), \(C=2\), \(D=3\), \(E=4\) e lendo as arestas do grafo:

• Coluna \(A\) (\(A\) tem 2 links de saída: para \(B\) e \(C\)): \(M_{BA} = 0{,}5\), \(M_{CA} = 0{,}5\), demais = 0.
• Coluna \(B\) (\(B\) tem 1 link de saída: para \(D\)): \(M_{DB} = 1{,}0\).
• Coluna \(C\) (\(C\) tem 2 links de saída: para \(B\) e \(D\)): \(M_{BC} = 0{,}5\), \(M_{DC} = 0{,}5\).
• Coluna \(D\) (\(D\) tem 1 link de saída: para \(A\)): \(M_{AD} = 1{,}0\).
• Coluna \(E\) (\(E\) tem 1 link de saída: para \(B\)): \(M_{BE} = 1{,}0\).

A linha de \(E\) é inteiramente zero — ninguém aponta para \(E\), de modo que \(E\) só recebe o “piso” de teleportação \(\frac{1-d}{N}\).

Conexão com a fórmula anterior. Lembre-se da fórmula do PageRank apresentada acima:

A matriz \(M\) foi construída exatamente para representar essa somatória. A entrada \(M_{ij}\) captura o termo \(\frac{PR(j)}{L(j)}\): quando \(j\) linka para \(i\), \(M_{ij} \cdot PR(j) = \frac{PR(j)}{L(j)}\); caso contrário é zero. O produto \(M \cdot \mathbf{PR}\) na linha \(i\) soma todas essas contribuições — que é precisamente \(\sum_{v \to i} \frac{PR(v)}{L(v)}\). Portanto, a fórmula escalar acima é equivalente à equação vetorial

onde \(\mathbf{1}\) é o vetor de uns e \(\mathbf{PR}\) é o vetor de ranks. O algoritmo a seguir resolve essa equação pelo método de iteração de potência: começa com a distribuição uniforme \(\mathbf{w} = \tfrac{1}{N}\mathbf{1}\) e aplica repetidamente \(\mathbf{v} = d M \mathbf{w} + \tfrac{1-d}{N}\mathbf{1}\) até convergir — o que corresponde exatamente à linha v = M_hat @ w + (1 - d) / N no código abaixo.

Com a matriz em mãos, podemos aplicar o algoritmo à nossa mini-web. O vetor resultante contém os PageRanks normalizados (soma = 1) de \(A\), \(B\), \(C\), \(D\) e \(E\), respectivamente:

import numpy as np

def pagerank(M, d=0.85):
    N = M.shape[1]
    w = np.ones(N) / N        # distribuição uniforme inicial
    M_hat = d * M
    v = M_hat @ w + (1 - d) / N
    while np.linalg.norm(w - v) >= 1e-10:
        w = v
        v = M_hat @ w + (1 - d) / N
    return v

# M[i][j] = fração dos links de j que apontam para i
M = np.array([
    [0.0, 0.0, 0.0, 1.0, 0.0],  # A recebe 100 % de D
    [0.5, 0.0, 0.5, 0.0, 1.0],  # B recebe 50 % de A, 50 % de C e 100 % de E
    [0.5, 0.0, 0.0, 0.0, 0.0],  # C recebe 50 % de A
    [0.0, 1.0, 0.5, 0.0, 0.0],  # D recebe 100 % de B e 50 % de C
    [0.0, 0.0, 0.0, 0.0, 0.0],  # E não recebe de ninguém
])

pages = ["A", "B", "C", "D", "E"]
ranks = pagerank(M)
for page, rank in sorted(zip(pages, ranks), key=lambda x: -x[1]):
    print(f"Página {page}: {rank:.4f}")

Página D: 0.2974
Página A: 0.2828
Página B: 0.2395
Página C: 0.1502
Página E: 0.0300

O resultado é contraintuitivo: \(B\) tem o maior grau de entrada (recebe links de \(A\), \(C\) e \(E\)), mas não é o nó de maior PageRank. \(D\) e \(A\) ficam à frente. Por quê? \(B\) repassa 100% do seu rank a \(D\) (pois seu único link de saída aponta para \(D\)). \(D\), por sua vez, repassa 100% a \(A\). E \(A\) redistribui para \(B\) e \(C\) — que realimentam \(D\). O ciclo \(D \to A \to C \to D\) e \(D \to A \to B \to D\) cria um laço de retroalimentação que acumula rank em \(D\) e \(A\) ao longo das iterações. \(B\) recebe muito, mas também distribui muito, sem guardar nada para si.

\(E\) confirma o caso oposto: sem links de entrada, seu PageRank é apenas o “piso” de teleportação, \(\frac{1 - 0{,}85}{5} = 0{,}03\), independentemente de para onde aponta.

Redes sociais também se modelam como grafos, mas com uma distinção importante quanto à direção das arestas. No Facebook, amizade é mútua por definição: se Alice é amiga de Bob, Bob é amigo de Alice — o grafo é não-dirigido. Já no Instagram ou no Twitter/X, seguir alguém não implica ser seguido de volta: o grafo é dirigido, com a aresta A→B indicando “A segue B”.

O grafo a seguir modela uma pequena rede social com seis usuários e relações de amizade — portanto, não-dirigido.

Alice e David têm grau 3 — a maior conectividade local da rede — e formam, junto com Bob, um triângulo: os três são mutuamente amigos. Carol está ligada apenas a Alice e Eve; Frank, apenas a David e Eve. Já é possível perceber que alguns vértices concentram mais conexões do que outros e que a posição de um vértice na rede influencia sua capacidade de “alcançar” os demais em poucos saltos. Essa noção de centralidade — o quanto um vértice é estrategicamente posicionado na rede — é uma das métricas centrais na análise de redes sociais.

Um resultado famoso nesse contexto é a hipótese dos seis graus de separação: a ideia de que quaisquer duas pessoas no mundo estão a no máximo seis “saltos” de distância na rede social global. Em 2011, pesquisadores do Facebook analisaram o grafo social da plataforma — então com mais de 700 milhões de usuários — e encontraram uma distância média de apenas 4,74 graus entre quaisquer dois usuários, confirmando empiricamente a hipótese para uma rede em escala real.

A Beleza da Abstração

#

O que torna a teoria dos grafos fascinante é que ela opera no nível puro da estrutura. Uma molécula de benzeno, uma rede social com dez mil usuários e o mapa de metrô de São Paulo podem todos ser modelados como grafos e estudados com as mesmas ferramentas matemáticas.

Euler não sabia, em 1736, que estava fundando uma teoria que seria central para a computação, as telecomunicações, a bioinformática e a análise de redes sociais nos séculos seguintes. Ele apenas queria resolver um quebra-cabeça sobre pontes.

Às vezes, a matemática mais útil começa com uma pergunta aparentemente frívola.

No próximo artigo, formalizaremos a linguagem da teoria dos grafos — definições, notações e os primeiros exemplos fundamentais.

Uma Jornada pela Teoria dos Grafos

#

Ao longo desta série, vamos construir os fundamentos da teoria dos grafos de forma sistemática. Começaremos pelas definições básicas e avançaremos até resultados profundos e suas aplicações:

1. Grafos: Uma Linguagem para Modelar Conexões — este artigo
2. Definições e Notações em Teoria dos Grafos — a linguagem formal: vértices, arestas, vizinhança, subgrafos, grafos completos
3. Grau de um Vértice e o Lema do Aperto de Mãos — grau, grafos regulares e o elegante teorema que relaciona graus e arestas
4. Isomorfismo e Representação por Matrizes — quando dois grafos são “iguais” e como representá-los computacionalmente
5. Caminhos, Ciclos e Conexidade — como navegar em um grafo; grafos bipartidos e sua caracterização
6. Árvores — a estrutura mais importante da computação: acíclica, conexa e elegante
7. Grafos Eulerianos e Hamiltonianos — percursos especiais: percorrer todas as arestas ou todos os vértices
8. Grafos Planares — quando é possível desenhar um grafo sem cruzamento de arestas
9. Grafos Direcionados — quando a direção das conexões importa