O Problema de Minimizar Redes de Comunicação

Sueli Costa
Eduardo Sebastiani

Na RPM 10, p.52, propusemos o seguinte problema: Um professor sobrevive lecionando em três colégios. Qual é o melhor lugar para ele morar? Procura-se assim um ponto P que minimize a soma das distâncias a três pontos dados A1,A2, A3. Este problema é conhecido como problema de Fermat ou de Steiner e pode ser estendido para n pontos A1,... ,An. (O pobre professor leciona em n colégios!) Soluções exatas ou aproximadas para este problema são de enorme interesse quando se procura minimizar, por exemplo, o custo de redes telefônicas, rodovias ou redes de distribuição de água e esgoto.

Apresentamos aqui uma resolução do problema para três pontos, A, B e C não colineares, subdividindo a análise em dois casos:

Fig.0l: O triângulo ABC tem todos os ângulos menores do que 120°: Neste caso o ponto P que minimiza a soma das distâncias aos vértices é o ponto interior ao triângulo que "olha" os três lados sob ângulos iguais.

Fig.02: O triângulo ABC possui um ângulo CAB maior ou igual a 120°: Neste caso, o ponto que minimiza a soma das distâncias aos vértices é o vértice A.

A primeira observação a ser feita é que podemos neste problema nos restringir a procurar a solução em pontos da região triangular (formada pelo triângulo e seus pontos interiores). Isto é conseqüência do fato que, dado um ponto Q exterior ao triângulo é sempre possível encontrar um ponto Q' no triângulo ABC tal que

QA + QB + QC > Q'A + Q'B + Q'C.

A prova deste fato está esquematizada no desenho acima. Temos que considerar, separadamente, os pontos das duas regiões do plano (Q = Q1, Q = Q2)

I) Vamos considerar primeiramente o caso em que os ângulos do triângulo ABC não excedem 120° (Fig.4).

Queremos encontrar o valor mínimo para   d = AP + BP + CP, onde P é um ponto de região triangular fechada.

Girando o triângulo APB de 60° com centro em B, obtemos C'P'B. ABC e BPP' são triângulos equiláteros. Observamos que AP + BP + CP = CP' + P'P + PC, ou seja d é o comprimento da poligonal CP'PC. Concluímos então que d será mínima se os pontos C, F',P e C estiverem alinhados . Neste caso, teremos e .

Então o ponto, P, para o qual d é mínima é o que "olha" os lados AB,BC e AC de 120°. Nos triângulos com ângulos menores que 120°, é sempre possível determinar este ponto P, conhecido como ponto de Fermat. As construções serão dadas a seguir.

Observamos que, se o ângulo BAC é de 120°, obtemos CAC alinhados e portanto a solução para o nosso problema é P = A.

II) Suponhamos agora que o triângulo ABC tenha um ângulo, A, maior que 120°. Vamos mostrar que o ponto-solução para o problema de Steiner é o vértice A. Isto é:      AP + BP + CP> AB + AC.

Girando o triângulo APB em A de tal maneira que o triângulo obtido B'P'A tenha B',A e C alinhados, temos PÂP' < 60°. Isto implica que P'P < AP. Então d = AP + BP + CP > P'P + B'P + PC, ou seja, d é maior que o comprimento da poligonal B'P'PC, que por sua vez é maior que o segmento B'C.

Temos então:

AP + BP + CP > B'C = B'A + AC = AB + AC. Concluímos portanto as provas das afirmações feitas em i) e ii).

O Ponto de Fermat

Uma determinação do ponto de Fermat (para triângulos com ângulos menores que 120°) é feita a partir da construção feita em (I). Repetimos o processso para os demais vértices, a partir de triângulos equiláteros ABC, ACB' e BC A'.

Observamos que o valor mínimo para a soma das distâncias aos vértices é o comprimento de qualquer um dos segmentos AA', BB' ou CC.

Outra forma de se determinar o ponto de Fermat P ê baseada na constatação feita em (I) de que este "olha" todos os lados do triângulo sob um ângulo de 120° : P é determinado pela intersecção dos arcos-capazes correspondentes (Fig. 7).

     

A figura 8 ilustra a construção de Steiner utilizada nos algoritmos computacionais. Esta é uma combinação das duas anteriores.

Observações

- Usando propriedades da elipse, obtemos uma outra forma de concluir que, quando a solução P do problema de Steiner está na região interior do triângulo, este ponto tem que olhar os lados sob um ângulo de 120°.

Consideramos a elipse de focos B e C passando pela solução P. Entre os pontos da elipse, P tem que ser o mais próximo de A.  Para que isso aconteça e tem que ser iguais (propriedade reflexiva da elipse).

Fazendo o mesmo raciocínio para a elipse de focos A e B passando por P, concluímos que os ângulos , e são iguais. (Esta é a idéia de nossa primeira resolução para o problema e também da solução enviada por Eduardo Wagner.)

-   A procura de um ponto que minimize a soma das distâncias a  n pontos dados já aparece nos trabalhos de Jacob Steiner (1786-1863), professor de Matemática na Universidade de Berlin. A generalização mais significativa para o problema aqui apresentado (também conhecida como problema de Steiner generalizado) é a procura da rede mínima de comunicação entre n pontos dados. Ou seja: Dados n pontos, determinar um sistema conexo de segmentos retilínios que os una e que tenha comprimento mínimo (Fig.  10).

A solução nem sempre é univocamente determinada. Atualmente existem programas computacionais capazes de resolver este problema para quinze pontos em apenas uma hora, utilizando-se um computador de grande porte. Entretanto, ao se aumentar o número de pontos para, por exemplo, 100, verifica-se que, com os algoritmos atuais, mesmo o mais rápido computador levaria milhares de anos para encontrar soluções. Este fato tem levado à procura de  processos que dão soluções aproximadas para o problema, em geral um tanto mais longas que a ótima, mas factíveis de serem obtidas computacionalmente. Um artigo recente que discute este assunto é The Shortest-Network Problem, Scientific American, janeiro de 1989, p. 66 a 71.

-   Vários leitores chamaram nossa atenção para o fato de que o problema aqui apresentado foi proposto por  Pierre de Fermat (1601-1665)  a Evangelista Torricelli (1608-1647) e não o contrário, como consta em Onde Morar? , RPM 10. "De fato, na maior parte da bibliografia que consultamos posteriormente é esta a versão que aparece. (A afirmação que fizemos no artigo foi retirada do livro: C. De Comberouse, Cours dAlgèbre Supérieure, Gauthier-Villars, 1904.)

O primeiro registro conhecido de solução para este problema no caso de três pontos é de cerca de 1640, com resoluções independentes de Evangelista Torricelli e Francesco Cavalieri.

Foi o leitor João Linneu de Almeida Prado, Jaú, SP, quem primeiro nos alertou para a grande contribuição de J. Steiner para o caso geral do problema que hoje leva seu nome.

-   Outras duas bonitas resoluções do problema de Steiner para três pontos são as que se utilizam do teorema de Viviani (discípulo de Galileu e Torricelli) e do teorema de Ptolomeu (Alexandria, séc. II). Referências: Dõrrie, H., 100 great problems of elementary Mathematics, New York Dover, 1965, p. 361-365; Padoc, D. A course oí Geometry for colleges and universities, Cambridge Univ.   Press, 1970 (Sugestões de Sérgio Rodrigues, São Carlos, SP).

A simplicidade da resolução que apresentamos neste trabalho envolveu um trabalho de síntese de muitas consultas. Principais referências: Courant, C. e Robbins, H., Qué es Ja Matemática.?; H. S. Coxeter, Introduction to Geometry, Wiley, New York, 1969; D. Sokplowsky, A note on the Fermat Ptoblem, The American Mathematical Monthly, vol. 83, 1976, p. 276.

-     Também enviaram sugestões para a solução do problema Onde Morar. Francisco Mauro, Fortaleza, CE; Pedro Paulo Martins, Três Corações, MG; Marcelo Lower, SP.

-     Os dois artigos a seguir complementam este trabalho.   O primeiro traz uma interessantíssima resolução mecânica para o problema, enviada por Eduardo Wagner. O segundo, enviado por Sérgio Rodrigues, utiliza cálculo diferencial para fazer um rastreamento das soluções possíveis para o problema de Steiner no caso de n pontos. Não percam!

-     Registramos aqui a participação de Sérgio Rodrigues, Sávio Rodrigues, Marcelo Firer e do grupo editorial da RPM que discutiram o problema conosco e deram importantes sugestões.

 

Sueli R. Costa, doutora pela UNICAMP, trabalha na área de Geometria. Professora da UNICAMP, atua também em cursos de aperfeiçoamento para professores.

Eduardo Sebastiani é doutor pela Universidade Grenoble, França, na área de Geometria. Professor da UNICAMP, sua área de pesquisa atual é a Etno-matemática com ênfase em educação indígena.