Uma introdução à teoria dos grafos – Parte 1

Anteriormente foram apresentados alguns conceitos sobre o uso da redutibilidade e abstração para resolução de problemas.  Agora, será apresentado um conjunto de objetos que é largamente utilizado para resolver uma série enorme de problemas nos mais diversos campos do conhecimento: Grafos.Formalmente podemos definir um grafo como um par ordenado (V,A), onde V e A são conjuntos disjuntos, e cada elemento de A corresponde a um par não-ordenado de elementos (não necessariamente distintos) de V. Os elementos do conjunto V são chamados vértices e os elementos do conjunto A são chamados arestas.

Quando uma aresta a corresponde a um par {u, v} de vértices, denotamos isso escrevendo a = {u, v}. Também escrevemos simplesmente uv para nos referirmos a uma tal aresta, quando não há perigo de confusão

Se G é um grafo, então também denotamos o seu conjunto de vértices por V (G), e o seu conjunto de arestas por A(G). Assim, tendo o nome de um grafo, ainda que os nomes do seu conjunto de vértices e do seu conjunto de arestas não sejam explicitados, podemos sempre nos referir a esses objetos.

É considerado que a primeira menção formal aos grafos foi feita por Leonhard Euler em 1736 e tratava sobre o problema das Sete Pontes de Königsberg:

O problema é baseado na cidade de Königsberg  (território da Prússia até 1945, atual Kaliningrado, na Rússia), que é cortada pelo Rio Pregolia, onde há duas grandes ilhas que, juntas, formam um complexo que na época continha sete pontes, conforme mostra a figura ao lado.

Discutia-se nas ruas da cidade a possibilidade de atravessar todas as pontes sem repetir nenhuma. Havia-se tornado uma lenda popular a possibilidade da façanha quando Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições.

As sete pontes de Königsberg

Euler usou um raciocínio muito simples. Transformou os caminhos em retas e suas intersecções em pontos, criando possivelmente o primeiro grafo da história. Então percebeu que só seria possível atravessar o caminho inteiro passando uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de onde saísse um número ímpar de caminhos. A razão de tal coisa é que de cada ponto deve haver um número par de caminhos, pois será preciso um caminho para “entrar” e outro para “sair”. Os dois pontos com caminhos ímpares referem-se ao início e ao final do percurso, pois estes não precisam de um para entrar e um para sair, respectivamente. Se não houverem pontos com número ímpar de caminhos, pode-se (e deve-se) iniciar e terminar o trajeto no mesmo ponto, podendo esse ser qualquer ponto do grafo. Isso não é possível quando temos dois pontos com números ímpares de caminhos, sendo obrigatoriamente um o início e outro o fim.Este resultado também é considerado um dos primeiros resultados topológicos na geometria, o que demonstra que, desde o principio, a utilização de grafos está estreitamente relacionada à abstração para resolução de outros problemas.

Em breve um pouco mais de grafo para vocês. Aguardem!