ANÁLISE COMBINATÓRIA

Teoria dos grafos

A Teoria dos Grafos não é uma teoria: é uma coleção de problemas. Todos esses problemas são formulados sobre um objeto combinatório conhecido como grafo. Os problemas tornaram-se célebres porque ocorrem em diversas áreas da computação, da engenharia, e em muitas aplicações industriais.

O problema mais famoso da teoria dos grafos é conhecido como As pontes de Königsberg, que pode ser enunciado como:

Na cidade de Königsberg sete pontes cruzam o rio Pregel estabelecendo ligações entre duas ilhas e entre as ilhas e as margens opostas do rio, conforme a figura abaixo. É possível fazer um passeio pela cidade, começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma vez?

Euler resolveu o problema transformando-o num problema de grafos. Euler associou a esse problema o seguinte esquema:

Onde cada linha representa uma ponte e os círculos representam as margens e as ilhas. Em linguagem de grafos, as linhas são chamadas de arcos e os círculos, de nós. O esquema acima é chamado de circuito. Assim, o problema consiste em achar um circuito que percorra cada arco uma única vez. Os grafos os quais isto é possível são chamados de eulerianos. Definimos o grau de um nó como sendo o número de arcos incidentes no nó. Um resultado devido a Euler diz que um grafo conexo é euleriano se, e somente se, cada nó tem grau par. Portanto, o grafo acima não é euleriano. Logo, não é possível fazer o passeio pela cidade começando e terminando no mesmo lugar cruzando cada ponte uma única vez.