JOSÉ LUIZ PASTORE MELLO

ESPECIAL PARA A FOLHA

Um dos quebra-cabeças mais antigos e populares é tentar ligar água, luz e telefone em três casas sem que haja cruzamento entre as ligações. Na figura 1, você pode observar uma tentativa de resolução do problema malsucedida devido ao cruzamento da ligação de luz da casa 3 com a de telefone da casa 2. Se você ainda não conhece esse quebra-cabeça, sugiro que pegue um papel e faça suas tentativas antes de prosseguir na leitura deste artigo.
Problemas semelhantes a esse são estudados em um ramo da matemática chamado teoria dos grafos, com aplicações no planejamento de rotas aéreas, malha rodoviária das grandes cidades etc. Um dos mais antigos problemas de grafos que se conhece foi estudado pelo matemático suíço Leonhard Euler (1707-1783) durante o período em que ele morava na cidade de Köningsberg, antiga Prússia. O problema consistia em decidir se existia ou não um caminho no qual os moradores da cidade pudessem passear pelas sete pontes que ligavam as margens do rio Pregel a duas ilhas sem passar duas vezes pela mesma ponte. Na ocasião, Euler demonstrou a não-existência de tal caminho, introduzindo algumas idéias que estão na origem do que se chama hoje teoria dos grafos.
O problema que propomos é de natureza semelhante ao resolvido por Euler, o que implica dizer que não possui solução no plano. Mesmo que levemos em consideração a forma aproximadamente esférica da Terra, ele continua sem solução. Um fato surpreendente resgata o interesse do problema se tentarmos resolvê-lo sobre uma superfície semelhante à câmara cheia de um pneu. Como mostra a figura 2, se vivêssemos em um planeta em forma de "pneu", o problema das ligações teria uma belíssima solução sem cruzamento de linhas.