A conjectura de Steiner e os caminhos mais curtos

Luiz Barco

Diz o ditado que todos os caminhos levam a Roma. Mas, se tomarmos uns e não outros, certamente chegaremos mais depressa. Dois fatos foram decisivos para que eu abordasse a questão de como descobrir os percursos mais curtos. Um deles aconteceu durante um congresso sobre adolescentes do qual participei no Recife. O outro, nos Estados Unidos, envolvendo dois pesquisadores chineses – Ding-Zhu Du, da Universidade de Princeton, e Frank Hwang, do laboratório AT&T Bell. No Recife, num dos intervalos entre duas palestras, vi um casal de adolescentes montando um jogo, cuja solução era equivalente a descobrir caminhos diferentes, mas com a mesma extensão.

Então, propus que resolvessem um clássico probleminha.

A figura mostra uma cidade bem regular e alguém quer ir da esquina X até a Y no menor percurso. A linha pontilhada indica um dos caminhos. Quantos existem?

Mais tarde, os jovens me apresentaram uma bela solução.

O número colocado em cada esquina indica quantos percursos de menor extensão existem partindo-se de X, e a resposta a que chegaram foi 70. O interessante é que os jovens resolveram o problema sem conhecer análise combinatória. Tenho minhas dúvidas se, quando forem estudá-la, da maneira como é ensinada, vão se lembrar de que os coeficientes que formam o triângulo de Pascal estão em cada esquina do problema que resolveram. Por vezes, tenho a sensação de mostrar algo aos alunos que espero que vejam, mas sem lhes dar tempo para enxergarem.

O outro fato que me leva a crer nas dificuldades em encontrar os caminhos mais curtos foi o resultado a que chegaram os chineses Du e Hwang. Eles resolveram um problema de otimização de redes, usando a chamada conjectura da razão de Steiner. Todos nós já deparamos, por exemplo, com crianças ligando pontos para formar figuras. Mas, ligar pontos para formar uma rede cujo comprimento seja o menor possível é um intricando problema matemático.

Para entendê-lo, considere um conjunto de pontos num plano. A menor rede que conecta esses pontos é a árvore mínima de Steiner, ou SMT (Steiner Minimum Tree). Foi o matemático suíço Jakob Steiner (1796-1863) quem introduziu novos pontos – os pontos de Steiner – usados como vértices de conexão. Considere o exemplo de três pontos apenas. Se eles são os vértices de um triângulo eqüilátero, será possível obter um SMT pela adição de um ponto de Steiner no centro do triângulo e então ligá-lo aos três vértices.

O problema de achar um SMT surge em áreas como desenho de circuitos de computador, de redes telefônicas, de estudos de locações de fábricas etc. Mas encontrar um algoritmo – processo de cálculo ou resolução de problemas semelhantes em que se estipulam regras para a obtenção do resultado – que possa calcular um SMT para um número grande de pontos é uma questão difícil. Cientistas da computação têm se contentado com soluções aproximadas. Uma delas é a árvore mínima medida entre dois – Minimum Spanning Tree -, ou MST do conjunto. É a menor rede cujos vértices são os pontos do conjunto (é proibido incluir vértices extras). No exemplo de três ponto formando um triângulo eqüilátero, um MST é o V formado pela conexão de dois vértices ao terceiro.
Em geral, um MST é maior que o SMT, mas em compensação já existem algoritmos muito eficientes para determiná-los. Encontrar um MST pode ser rápido, e aos pesquisadores interessa saber quão boa é essa aproximação. Uma medida usual dessa tolerância é a razão de Steiner ( o cociente entre a medida do SMT e a do MST):

Comprimento do SMT
Razão de Steiner = Comprimento do MST

No exemplo de três pontos, você pode usar o teorema de Pitágoras para verificar que essa razão é a metade da raiz quadrada de 3, ou 0,866. Em qualquer aplicação que se faça dessas medidas – como no caso dos desenhos de redes telefônicas -, seu custo é diretamente proporcional ao comprimento da rede. Como a obtenção da rede mínima é mais demorada e encarece a operação, a opção é o que se chama de melhor razão de Steiner.
Vimos que encontrar um SMT representaria uma economia potencial da ordem de 13%, já que a razão de Steiner foi de 87%. Em 1989, matemáticos provaram que a conjectura era verdadeira para qualquer conjunto com até sete pontos e conseguiram elevar o rendimento medido pela razão de Steiner, de 0,57, obtido em 1976, para 0,824 e acharam que essa seria a melhor aproximação. Usando esse mesmo método, os pesquisadores Du e Hwang transformaram a conjectura da razão de Steiner num problema da teoria dos jogos – o estudo das chances de ganhos e perdas em diferentes jogos – e esperam aplicá-lo na resolução de outros problemas que envolvam a procura de caminhos mínimos.

Luiz Barco é professor da Escola de Comunicações e Artes da Universidade de São Paulo

• Mais lidas

1

História

A Biblioteca de Alexandria não foi destruída pelo fogo, mas pelo esquecimento

2

Ciência

Seres vivos emitem uma luz que desaparece após a morte, sugere estudo

3

Saúde

O que é resiliência imunológica – e qual o seu papel no envelhecimento saudável

4

História

O que é e como surgiu a maçonaria?

5

Saúde

O domínio da linguagem pode prever longevidade em idosos

• Curiosidades
• Matemática