Clique e Assine SUPER por R$ 9,90/mês
Continua após publicidade

A conjectura de Steiner e os caminhos mais curtos

Artigo do professor Luiz Barco, explicando como resolver problemas matemáticos usando a conjectura de Steiner.

Por Da Redação Materia seguir SEGUIR Materia seguir SEGUINDO
Atualizado em 31 out 2016, 18h46 - Publicado em 31 jul 1991, 22h00

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.

Continua após a publicidade

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):

Continua após a publicidade

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

Publicidade

Matéria exclusiva para assinantes. Faça seu login

Este usuário não possui direito de acesso neste conteúdo. Para mudar de conta, faça seu login

Domine o fato. Confie na fonte.

10 grandes marcas em uma única assinatura digital

MELHOR
OFERTA

Digital Completo
Digital Completo

Acesso ilimitado ao site, edições digitais e acervo de todos os títulos Abril nos apps*

a partir de 9,90/mês*

ou
Impressa + Digital
Impressa + Digital

Receba Super impressa e tenha acesso ilimitado ao site, edições digitais e acervo de todos os títulos Abril nos apps*

a partir de 14,90/mês

*Acesso ilimitado ao site e edições digitais de todos os títulos Abril, ao acervo completo de Veja e Quatro Rodas e todas as edições dos últimos 7 anos de Claudia, Superinteressante, VC S/A, Você RH e Veja Saúde, incluindo edições especiais e históricas no app.
*Pagamento único anual de R$118,80, equivalente a 9,90/mês.

PARABÉNS! Você já pode ler essa matéria grátis.
Fechar

Não vá embora sem ler essa matéria!
Assista um anúncio e leia grátis
CLIQUE AQUI.