Tudo está conectado. Mas como?

Uma introdução a grafos e redes complexas — a linguagem matemática por trás de epidemias, apagões, redes sociais e muito mais.

Olhe para as duas imagens de satélite do nordeste dos Estados Unidos tiradas em 13 e 14 de agosto de 2003.

Imagem 1.

a. Imagem de satélite do nordeste dos Estados Unidos em 13 de agosto de 2003, às 21h29 (EDT), 20 horas antes do apagão de 2003.

b. A mesma região, mas 5 horas após o apagão.

À primeira vista, elas parecem idênticas, mas ao olhar com atenção, algo muda. Toronto, Detroit, Cleveland, Columbus e Long Island aparecem apagadas na segunda. Essa é uma fotografia real do antes e depois de um blackout que deixou 45 milhões de pessoas nos EUA e outros 10 milhões no Canadá sem energia elétrica.

A causa? A quebra de um fusível em algum ponto de Ohio. Uma falha pequena, local, corriqueira. Mas a rede elétrica que conecta geradores e consumidores em todo o nordeste americano transformou esse evento trivial em colapso continental. Quando um nó da rede falhou, sua carga foi redistribuída para os vizinhos. Esses vizinhos, sobrecarregados, também falharam e redistribuíram a carga para os deles. Em nenhum momento estávamos diante de um acidente aleatório, estávamos diante de uma falha em cascata, um fenômeno com leis próprias, que pode ser estudado, modelado e até previsto.

O apagão de 2003 não é uma curiosidade histórica isolada. É um retrato do mundo em que vivemos, um mundo de sistemas interconectados, onde a falha local pode se tornar crise global.

Em 1997, o FMI pressionou os bancos centrais de países do Pacífico a limitar o crédito e a inadimplência em cadeia derrubou bolsas de valores no mundo todo. Em 2009, a crise de crédito americana paralisou economias na Europa. Na internet, roteadores com defeito redirecionam tráfego para outros, que colapsam sob a sobrecarga, criando os chamados ataques de negação de serviço.

O que todos esses fenômenos têm em comum? Uma estrutura de rede, e existe uma matemática elegante e poderosa para estudar essa estrutura.

O que é um grafo?

Para descrever uma rede de qualquer tipo, seja ela elétrica, social, biológica, entre outras, precisamos de uma linguagem matemática precisa. Essa linguagem chama-se teoria dos grafos, e ela nasceu de um problema sobre pontes em 1735.

O matemático Leonhard Euler foi desafiado com o seguinte enigma: a cidade de Königsberg tinha sete pontes ligando quatro pedaços de terra separados por rios. Era possível caminhar pela cidade cruzando cada ponte exatamente uma vez?

Imagem 2.

Esquema ilustrativo de Königsberg com suas quatro ilhas e sete pontes.

Euler provou que não. Ele demonstrou que tal caminho não existe. Sua prova baseava-se apenas na disposição física das pontes, mas ao fazê-la, ele estabeleceu sem querer o primeiro teorema da teoria dos grafos .

Definição

Um grafo é formalmente definido como um par G = (V, E) de dois conjuntos. O primeiro, V, reúne os vértices, também chamados de nós, que representam as entidades do sistema: pessoas, cidades, proteínas, páginas web, o que for. O segundo, E, reúne as arestas, que representam as relações entre essas entidades.

O que torna essa definição precisa é a condição E ⊆ [V]². A notação [V]² representa o conjunto de todos os pares possíveis de 2 elementos de V. Dizer que E é um subconjunto disso significa que cada aresta é, por definição, um par de vértices, nem mais, nem menos. Uma aresta não pode conectar três vértices ao mesmo tempo, nem pode "apontar para si mesma". Além disso, assumimos que V ∩ E = ∅: vértices e arestas são objetos de naturezas distintas e não se confundem.

A partir daí, dois vértices x e y são ditos adjacentes, ou vizinhos, se o par {x, y} pertence a E, isto é, se existe uma aresta entre eles. Chamamos de ordem do grafo o número total de vértices |V|, e de tamanho o número total de arestas |E|. (Diestel, 2017, p. 2).

De forma simplificada, um grafo é um conjunto de pontos e um conjunto de linhas que os conectam. Com essa estrutura mínima, conseguimos representar qualquer sistema onde entidades se relacionam, e aplicar as mesmas ferramentas matemáticas a domínios completamente diferentes.