Pontos, Linhas e Métricas #05: O Grafo de Konigsberg

[O texto a seguir faz parte de uma série que pode ser visualizada em “Pontos, Linhas e Métricas: introdução à análise estrutural de redes sociais”]

O “Surgimento” dos Grafos, em 1736

No século XVIII, mais precisamente em 1736, Leonhard Euler resolveu um dos clássicos problemas matemáticos: “As Sete Pontes de Königsberg”. Esta cidade, que fazia parte da Prússia na época, hoje é chamada de Kaliningrado, é capital de uma província de mesmo nome na Rússia e possui uma estrutura bem particular.

A charada era proveniente desta estrutura física de Königsberg. A cidade era cortada pelo rio Pregel de um modo que tinha quatro partes, conectadas por sete pontes. O desafio consistia em pensar um caminho para passar entre as sete pontes, mas sem passar duas vezes pela mesma ponte. O que o matemático conseguiu foi, através da representação da topologia das regiões e pontes cidade, provar que não existia uma solução para o problema.

Se olharmos cada ponte como uma aresta e cada região como um nó, podemos representar a cidade como um grafo. A ilustração abaixo representa bem este processo:

 

Como Duncan Watts explica, “desde Euler, a teoria dos grafos cresceu continuamente, até se tornar um dos principais ramos da matemática e transbordar para economia. Cada área, portanto, tem sua própria versão de uma teoria das redes, assim como cada área tem sua própria forma de agregar comportamento individual e coletivo” (WATTS, p.11). É importante frisar isto para entender que não se trata apenas de aprender apenas uma perspectiva como teoria da complexidade, por exemplo, mas de associar diversas perspectivas para entender os fenômenos – e não apenas gerar dados sem contexto ou interpretação apoiados por óticas de diversas disciplinas.

Euler não menciona “grafo” na resolução do problema, mas em seu artigo fala de “geometria da posição”. Em retrospectiva hoje se fala da solução de Euler como uma aplicação dos grafos e inclusive se contesta esta afirmação (HOPKINS & WILSON, 2004). Mas, independente da posição específica deste matemático, o fato é que seu trabalho influenciou outros que vieram depois e começaram a estuturar problemas e suas soluções em questões de dados relacionais. Algumas das métricas de redes que veremos em breve, como distância média de caminho, só são possíveis de serem processadas a partir de equações matemáticas que levam em conta ideias de topologia.

Nos próximos textos, veremos algumas perspectivas das ciências sociais e psicológicas, como os trabalhos de Simmel, Moreno e Milgram, que analisaram características das redes sociais muito antes da existência dos métodos modernos de processamento de dados.

Referências e Fontes

– Story of Mathematics – 18th Century Mathematics – Euler http://www.storyofmathematics.com/18th_euler.html

– HOPKINS, Brian; WILSON, Robin. The Truth about Konigsberg. The College Mathematics Journal, 2004. Disponível em  http://www.gss.ucsb.edu/Hopkins1.pdf

– WATTS, Duncan J. Seis Graus de Separação: a evolução da ciência de redes em uma era conectada. São Paulo: Leopardo, 2009. [compre]