Uma Abordagem ao Problema de Steiner

Uma Abordagem ao Problema de Steiner Elisabete Olívia Monteiro de Matos Mestrado em Matemática para Professores Departamento de Matemática Orientador: Maria Leonor Nogueira Coelho Moreira, Professora Auxiliar, FCUP Coorientador: Samuel António de Sousa Dias Lopes, Professor Auxiliar, FCUP Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/________ 3 Agradecimentos Agrade¸co aos orientadores Leonor Moreira e Samuel Lopes pela dedica¸c˜ao, paciˆencia, apoio e ajuda durante estes meses de trabalho. Jamais esquecerei toda a disponibilidade destes dois professores que ultrapassou largamente as suas obriga¸c˜oes. `a minha m˜ae Concei¸c˜ao e ao meu marido Pedro pelo incentivo para concluir este trabalho e por toda a disponibilidade durante este ´ultimo ano. aos meus filhotes, Ant´onio e Amadeu, por aguentarem uma m˜ae algo ausente durante os ´ultimos dois anos. aos amigos de longa data, pelo apoio, compreens˜ao e est´ımulo. 4 Resumo O tema central desta disserta¸c˜ao ´e usualmente designado por Problema de Steiner e pode ser assim enunciado “Dado um conjunto finito de pontos num espa¸co m´etrico, encontrar uma rede de comprimento m´ınimo que conecte todos os pontos desse conjunto”. Ele pode ser visto como um problema de optimiza¸c˜ao geom´etrico que mostramos estar relacionado com o problema, de optimiza¸c˜ao combinat´oria, da determina¸c˜ao da ´arvore geradora minimal de um grafo dado, que tamb´em ´e aqui abordado. No entanto, as solu¸c˜oes dos dois problemas divergem quando constatamos que, por vezes, ao acrescentar pontos ao conjunto de pontos dado conseguimos diminuir o comprimento da rede que os liga, como acontece com a resolu¸c˜ao do Problema de Fermat, que pode ser visto como o problema de Steiner para 3 pontos do plano euclideano. Uma das dificuldades da resolu¸c˜ao deste problema ´e saber se estes pontos existem e qual ´e a sua localiza¸c˜ao. Neste trabalho, para al´em de descrevermos a solu¸c˜ao do Problema de Fermat e a constru¸c˜ao de uma ´arvore geradora minimal de um grafo dado, definimos e mostramos algumas das carater´ısticas e propriedades das chamadas ´arvores de Steiner que podem ser solu¸c˜ao do nosso problema central, quando tratado no plano euclideano. Descrevemos ainda um processo recursivo de constru¸c˜ao de uma ´arvore de Steiner fixado o conjunto de pontos iniciais e a topologia da ´arvore, isto ´e, fixadas todas as liga¸c˜oes entre os pontos iniciais e os pontos de Steiner dessa ´arvore. Para al´em disso, abordamos alguns dos resultados que permitem obter, em casos particulares, a chamada raz˜ao de Steiner ´otima, que compara o comprimento de uma solu¸c˜ao com o de uma ´arvore geradora minimal. O valor desta raz˜ao ´e uma medida de qualidade para as solu¸c˜oes aproximadas. Conclu´ımos o trabalho com uma breve resenha de algumas das aplica¸c˜oes do problema que pode despertar nos mais diversos leitores motivo para o estudar. Palavras-chave: Problema de Steiner, ´ Arvore de Steiner, ´ Arvore Geradora Minimal, Raz˜ao de Steiner, Ponto de Steiner, Problema de Fermat, Ponto de Torricelli 5 Abstract The main focus of this thesis is known as the Steiner problem and may be posed as follows “Given a finite set of points in a metric space, determine e minimal network connecting all the points in the set”. This can be viewed as a geometric optimization problem which will be shown to be related to the combinatorial problem of determine a minimal spanning tree in a weighted graph. Nevertheless, the solutions to these problems diverge when it is realized that often the length of the network can be shortened by adding additional points to the initial set, as occurs when solving Fermat’s problem, which can be seen as a special case of Steiner’s problem for 3 points in euclidean space. One of the difficulties of Steiner’s problem is to determine the location of the additional points. In this thesis, we describe a solution to Fermat’s problem, review the construction of a minimal generating tree in a weighted graph, define and prove some of the main properties of the so-called Steiner trees, among which a solution to the euclidean Steiner problem lies. Additionally, we describe an algorithmic procedure for constructing a Steiner tree, given the initial set of points and the topology of the tree, i.e., given the connections between the initial set of pints and the additional points of the tree. Furthermore, we discuss some of the results that lead to obtaining, in particular cases, the so-called optimal Steiner ratio, which compares the length of an optimal solution to the Steiner problem to the length of a minimal spanning tree. This ratio measures how good an approximate solution is. We conclude this work with a brief summary of some of the applications of Steiner’s problem, which might motivate some of the readers to pursue the study of this problem further. Keywords: Steiner problem, Steiner tree, Minimal spanning tree, Steiner ratio, Steiner point, Fermat problem, Torricelli point. 6 Conte´udo Resumo 5 Abstract 6 1 Introdu¸c˜ao 15 2 Apresenta¸c˜ao do Problema 17 2.1 ProblemadeFermat ................................ 17 2.2 Ocasogeral..................................... 30 3´ Arvores geradoras minimais 33 3.1 Conceitos e resultados iniciais em teoria de grafos . . . . . . . . . . . . . . . . 34 3.2 Constru¸c˜ao da ´ Arvore Geradora Minimal de um grafo . . . . . . . . . . . . . 40 3.3 Algoritmos e Complexidade Computacional . . . . . . . . . . . . . . . . . . . 49 4´ Arvores de Steiner 51 4.1 Alguns conceitos preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Tipos de ´ Arvores.................................. 56 4.3 Propriedades b´asicas das ´ Arvores de Steiner . . . . . . . . . . . . . . . . . . . 58 4.3.1 ˆ Angulos numa ´ Arvore de Steiner . . . . . . . . . . . . . . . . . . . . . 59 4.3.2 Graudosv´ertices.............................. 59 4.3.3 N´umero de Pontos de Steiner . . . . . . . . . . . . . . . . . . . . . . . 60 4.3.4 N´umero de topologias de Steiner . . . . . . . . . . . . . . . . . . . . . 61 4.4 Unicidade das ´arvores relativamente m´ınimas em que os pontos de Steiner tˆem grau3 ........................................ 64 7 4.5 Constru¸c˜ao de ´arvores relativamente m´ınimas . . . . . . . . . . . . . . . . . . 65 5 Raz˜ao de Steiner 73 5.1 Raz˜ao de Steiner ´ Otima .............................. 74 5.1.1 O primeiro limite inferior . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.1.2 Raz˜ao de Steiner ´ Otima para qualquer conjunto de trˆes pontos de R276 5.1.3 Raz˜ao de Steiner ´ Otima para qualquer conjunto de quatro pontos de R277 5.2 Alguns casos particulares da Raz˜ao de Steiner . . . . . . . . . . . . . . . . . . 102 6 Aplica¸c˜oes do problema 105 7 Conclus˜ao 112 8 Lista de Tabelas 4.1 N´umero de topologias completas em fun¸c˜ao do n´umero de v´ertices iniciais v. 63 5.1 Limites Inferiores para a Raz˜ao de Steiner ´ Otima at´e 1990 . . . . . . . . . . . 74 5.2 Valores da Raz˜ao de Steiner at´e 2000 . . . . . . . . . . . . . . . . . . . . . . . 103 9 um problema proposto por Gauss a Schuhmacher, em 1836, quando coloca a quest˜ao de como construir uma rede ferrovi´aria de comprimento m´ınimo que ligue quatro cidades alem˜as. O artigo [14] permite ter uma ideia da grande aplicabilidade do Problema de Steiner na ´area da Ind´ustria, por exemplo. Nos ´ultimos cinquenta anos a comunidade cient´ıfica obteve resultados muito interessantes relativos ao Problema de Steiner e a uma boa parte deles ´e feita referˆencia nas obras [23, 35]. Neste trabalho pretendemos, primeiro que tudo conseguir interessar o leitor pelo tema e em seguida permitir-lhe rapidamente conhecer as suas bases e a bibliografia que lhe permitam, caso queira, rapidamente avan¸car. A estrutura desta disserta¸c˜ao foi pensada de modo a permitir que qualquer pessoa com conhecimentos b´asicos de matem´atica pudesse embrenhar-se nas teias do Problema de Steiner. No cap´ıtulo 2, come¸camos por tratar completamente o Problema de Fermat de determina¸c˜ao de um ponto que minimize a distˆancia aos v´ertices de um triˆangulo, um problema geom´etrico cl´assico, cuja solu¸c˜ao remonta ao s´eculo XVII mas que pode ser interpretada como uma ´arvore de Steiner de pontos iniciais os trˆes v´ertices do triˆangulo; e conclu´ımos com uma breve apresenta¸c˜ao do caso geral. No terceiro cap´ıtulo s˜ao introduzidos conceitos e resultados b´asicos de teoria de grafos que permitem compreender o que ´e uma ´arvore geradora minimal e os algoritmos de constru¸c˜ao destas ´arvores. O quarto cap´ıtulo ´e dedicado `as ´ Arvores de Steiner. ´ E neste cap´ıtulo que o conceito de ´arvore e ponto de Steiner s˜ao introduzidos com rigor e s˜ao deduzidas algumas das suas propriedades e carater´ısticas fundamentais bem como a no¸c˜ao de topologia de uma ´arvore de Steiner e um m´etodo recursivo de constru¸c˜ao de uma ´arvore de Steiner minimal para uma topologia dada num conjunto de pontos iniciais fixado. A Raz˜ao de Steiner tem sido estudada ao longo das ´ultimas d´ecadas, aparecendo constantemente reultados cada vez mais satisfat´orios. No cap´ıtulo 5 apresentamos uma s´ıntese deste estudo, tratando completamente alguns dos resultados iniciais de determina¸c˜ao desta raz˜ao para conjuntos com poucos pontos, cuja prova real¸ca a complexidade do problema. A disserta¸c˜ao termina com a apresenta¸c˜ao no cap´ıtulo 6 de uma revis˜ao bibliogr´afica que permite ficar com uma ideia da diversidade das aplica¸c˜oes deste problema. 16 Cap´ıtulo 2 Apresenta¸c˜ao do Problema O estudo do Problema de Steiner tem as suas ra´ızes no estudo de um outro problema, tamb´em este muito conhecido, o Problema de Fermat. Na realidade, este ´ultimo ´e um caso particular do Problema de Steiner, uma vez que pretende, em R2, dados trˆes pontos iniciais, lig´a-los de tal modo que os comprimentos das liga¸c˜oes entre esses pontos seja m´ınima, isto ´e, encontrar uma rede de comprimento m´ınimo entre os trˆes pontos dados. O Problema de Fermat por vezes resolve-se com recurso a um quarto ponto, Ponto de Torricelli, que veremos mais adiante tratar-se de um Ponto de Steiner. Portanto, n˜ao h´a d´uvidas que o Problema de Fermat ´e um antecessor do Problema de Steiner. Ao longo deste cap´ıtulo ser˜ao apresentados alguns resultados que impulsionaram o estudo do Problema de Steiner explorando, na primeira sec¸c˜ao, o Problema de Fermat e um pouco do caso geral, na segunda sec¸c˜ao. Para al´em das referˆencias feitas ao longo do cap´ıtulo apoiamo-nos em [31]. 2.1 Problema de Fermat No in´ıcio do s´eculo XVII, Pierre de Fermat, no final do seu ensaio sobre m´aximos e m´ınimos, Methodus ad disquirendam maximam et minimam. De tangentibus linearum curvarum, desafiou a comunidade cient´ıfica da ´epoca colocando o seguinte problema: Dados trˆes pontos do plano, encontrar um quarto ponto tal que a soma da sua distˆancia aos trˆes pontos dados ´e m´ınima. Atualmente, podem ser encontradas v´arias resolu¸c˜oes distintas para o Problema de Fermat (por exemplo, em [59], cap´ıtulo 7), no entanto, a maior parte destas foi inspirada na resolu¸c˜ao de Evangelista Torricelli, que por volta de 1640, foi o primeiro a propor uma resolu¸c˜ao geom´etrica para o Problema de Fermat: As circunferˆencias que circunscrevem os triˆangulos equil´ateros constru´ıdos externamente sobre os lados do triˆangulo dado intersetamse num ponto, o ponto de Torricelli (ver Figura 2.1). Torricelli afirmava que o ponto de interse¸c˜ao das trˆes circunferˆencias, tamb´em conhecido como ponto isog´onico, era o ponto procurado no Problema de Fermat. No entanto, esta solu¸c˜ao geom´etrica nem sempre ´e o ponto que minimiza as distˆancias. Quando o ponto de 17 Figura 2.1: Resolu¸c˜ao Geom´etrica do Problema de Fermat, proposta por Torricelli Torricelli n˜ao est´a no interior do triˆangulo formado pelos trˆes pontos dados, o que acontece sempre que um dos ˆangulos do triˆangulo ´e igual ou superior a 120o, este n˜ao ´e a solu¸c˜ao do Problema de Fermat. Esta falha da proposta de Torricelli foi descoberta por Heinen em 1834, que propˆos a seguinte solu¸c˜ao para o Problema de Fermat: Se um dos ˆangulos do triˆangulo formado pelos trˆes pontos dados for igual ou superior a 120o, o ponto que minimiza a soma das distˆancias ´e o v´ertice desse ˆangulo, caso contr´ario, a solu¸c˜ao ´e o ponto de Torricelli. Em primeiro lugar devemos considerar a hip´otese de os trˆes pontos dados serem colineares. Ora, nestas circunstˆancias ´e f´acil verificar que o ponto que minimiza a soma das distˆancias ´e o ponto que se encontra entre os outros dois (ver Figura 2.2). Figura 2.2: Quando os trˆes pontos A,BeCs˜ao colineares Comecemos ent˜ao por verificar que o ponto que ´e solu¸c˜ao do Problema de Fermat n˜ao 18 pode estar no exterior do triˆangulo formado pelos trˆes pontos dados. Quando os trˆes pontos dados n˜ao s˜ao colineares comp˜oem um triˆangulo. As retas definidas por cada par de pontos dividem o plano em sete regi˜oes: o triˆangulo propriamente dito mais seis regi˜oes exteriores a esse triˆangulo (ver Figura 2.3). Figura 2.3: As retas AB,AC eBC dividem o plano em sete regi˜oes Consideremos um ponto Zpertencente a uma dessas seis regi˜oes exteriores ao triˆangulo. No que se segue, consideremos a regi˜ao delimitada por duas semirretas com origem no v´ertice B, como indicado na Figura 2.4. Seja Xo ponto de interse¸c˜ao de [AZ] com BC. Figura 2.4: Regi˜oes do plano exteriores ao triˆangulo [ABC] AZ +BZ +CZ > AZ +CZ =AX +XZ +CZ ≥AX +CX ≥AB +CB. Logo, Zn˜ao ´e o ponto que minimiza a distˆancia aos trˆes pontos dados. Usando argumentos da mesma natureza pode-se provar, para as outras cinco regi˜oes exteriores ao triˆangulo, que a distˆancia m´ınima n˜ao ´e atingida nessa regi˜ao, o que permite concluir que o ponto procurado pertence ao interior ou `a fronteira do triˆangulo formado pelos trˆes pontos dados. Provemos ent˜ao que as trˆes circunferˆencias da constru¸c˜ao de Torricelli se intersetam num ponto. Consideremos o triˆangulo formado pelos trˆes pontos dados no problema de Fermat, A, BeC. Centremos, de momento, a nossa aten¸c˜ao apenas em triˆangulos cujos ˆangulos s˜ao menores que 120o, de modo a assegurar que o ponto de Torricelli se encontra dentro deste 19 triˆangulo inicial [ABC]. De facto, ´e f´acil de ver que duas das circunferˆencias s˜ao tangentes se o ˆangulo nesse v´ertice ´e igual a 120o. Assim, se todos osˆangulos internos do triˆangulo forem inferiores a 120oent˜ao o ponto de Torricelli pertence ao interior de [ABC]. Seja C1a circunferˆencia que circunscreve o triˆangulo equil´atero [ACQ] constru´ıdo externamente sobre o lado [AC] do triˆangulo inicial [ABC], C2a circunferˆencia que circunscreve o triˆangulo equil´atero [ABR] constru´ıdo externamente sobre o lado [AB] e C3a circunferˆencia que circunscreve o triˆangulo equil´atero [BCP] constru´ıdo externamente sobre o lado [BC]. Comecemos por provar que as circunferˆencias C1,C2eC3se intersetam num ponto (ver Figura 2.1). Seja T6=Co ponto de interse¸c˜ao das circunferˆencias C1eC3. Note-se que de facto C n˜ao ´e o ´unico ponto de intersec¸c˜ao das duas circunferˆencias, visto que se C1eC3fossem tangentes no ponto C, o ˆangulo em Cteria 120ode amplitude, o que contraria as nossas condi¸c˜oes iniciais. Acresce que Test´a no interior do triˆangulo [ABC], porque os ˆangulos em A,BeCs˜ao inferiores a 120o. Os v´ertices de cada um destes triˆangulos equil´ateros acrescidos deste novo ponto T comp˜oem quadril´ateros. O que pretendemos averiguar ´e se o quadril´atero [AT BR] se inscreve numa circunferˆencia. Se assim for, como h´a uma ´unica circunferˆencia contendo os pontos A,BeR, ficar´a provado que Tpertence `a circunferˆencia C2e assim que as trˆes circunferˆencias se intersetam no ponto T(ver Figura 2.5). Figura 2.5: C1,C2eC3intersetam-se em T Como o quadril´atero [BT CP] est´a inscrito na circunferˆencia C3, ent˜ao a soma dos ˆangulos opostos em TeP´e 180o:∠BTC +∠P= 180o. De modo an´alogo, ∠ATC +∠Q= 180o. Como ∠P+∠Q+∠R= 180o, visto que s˜ao ˆangulos internos de triˆangulos equil´ateros, 20 temos ∠P+∠Q+∠R= 180o⇔180o−∠BT C + 180o−∠AT C +∠R= 180o ⇔∠BT C +∠AT C −∠R= 180o ⇔360o−∠ATB −∠R= 180o ⇔∠ATB +∠R= 180o. Ent˜ao, ∠AT B +∠R= 180o, o que prova que o quadril´atero [ATBR] se inscreve numa circunferˆencia, necessariamente a circunferˆencia C2. Est´a assim provado que as trˆes circunferˆencias se intersetam num ponto T.´ E f´acil constatar que este ponto T´e ´unico. Falta agora provar que T´e solu¸c˜ao do Problema de Fermat, isto ´e, que AT +BT +CT ´e m´ınimo, e que esta solu¸c˜ao ´e ´unica. Observe-se que ∠CT B =120o+120o 2= 120o, e que, de forma an´aloga, ∠ATB =∠ATC = 120o. Consideremos ent˜ao um ponto Squalquer no interior ou na fronteira do triˆangulo [ABC] (continuamos a considerar que o triˆangulo [ABC] n˜ao tem nenhum ˆangulo igual ou superior a 120o, o que implica que o ponto Test´a dentro do triˆangulo). Com este novo ponto S ´e poss´ıvel obter um triˆangulo (possivelmnente degenerado) de v´ertices A,BeS. Efetue-se uma rota¸c˜ao deste triˆangulo [ABS] de centro em Be amplitude 60ono sentido de [SB] para [AB] (ver Figura 2.6). Sejam A0eS0as imagens de Ae de S, respetivamente, pela rota¸c˜ao referida. Figura 2.6: Rota¸c˜ao do triˆangulo [ABS] de centro em Be amplitude 60o Por constru¸c˜ao, o triˆangulo [BSS0] ´e equil´atero, uma vez que ∠SBS0´e o ˆangulo de rota¸c˜ao, e por conseguinte ∠SBS0= 60o, e BS =BS0, porque [BS0] ´e a imagem de [BS] pela rota¸c˜ao referida, e como num triˆangulo, a lados iguais op˜oem-se ˆangulos iguais, ∠BS0S= ∠BSS0=120o 2= 60o(ver Figura 2.7). Para al´em disso, AS =A0S0. Ent˜ao, SA +SB +SC =S0A0+S0S+SC. A imagem do ponto A pela rota¸c˜ao referida n˜ao depende da posi¸c˜ao do ponto S, e SA +SB +SC ≥CA0 21 Figura 2.7: O triˆangulo [BSS0] ´e equil´atero porque o comprimento da linha poligonal [CSS0A0]S0A0+S0S+SC´e superior ou igual ao do segmento de reta com os mesmos extremos. Portanto, SA+SB+SC atinge seu m´ınimo se SeS0pertencerem a [CA0] (ver Figura 2.8). Para um tal S,∠CSB = 180o−∠BSS0= 120◦ e∠BSA =∠BS0A0= 180o−∠BS0S= 120o. Logo, ∠ASC = 360o−∠BSA−∠CSB = 120o. Reciprocamente, se ∠CSB =∠BSA = 120oent˜ao SeS0pertencem a [CA0]. Figura 2.8: Linha poligonal e segmento de reta de extremos CeA0 Como para uma escolha diferente e S,e SA +e SB +e SC > CA0, podemos ent˜ao concluir que o ponto que minimiza a soma das distˆancias determina ˆangulos com 120ode amplitude com os v´ertices do triˆangulo [ABC], logo este ponto ´e o ponto de Torricelli. Esta propriedade foi publicada por Bonaventura Cavalieri na obra Excercitationes Geometricae: Os ˆangulos entre os segmentos de reta formados pelos v´ertices do triˆangulo e o ponto de Torriceli s˜ao iguais entre si, e iguais a 120o. Considerando ainda a constru¸c˜ao de Torricelli, os segmentos de reta que se obtˆem unindo os v´ertices externos de cada triˆangulo equil´atero que se construiu aos respetivos v´ertices 22 opostos do triˆangulo inicial contˆem o ponto de Torricelli. Ora, ∠PTC +∠CTA =120o 2+ 240o 2= 180o, logo P,TeAs˜ao colineares. Analogamente, Q,TeBs˜ao colineares, e tamb´em R,TeC. Estes segmentos s˜ao conhecidos como segmentos de reta de Simpson , uma vez que foi Thomas Simpson quem provou que os mesmos se intersetam no ponto de Torricelli, em 1750, no livro Doctrine and Application of Fluxions [62](ver Figura 2.9). Figura 2.9: Segmentos de Simpson Em 1834, Franz Heinen provou que os segmentos de reta de Simpson tˆem todos o mesmo comprimento, comprimento este igual `a soma das distˆancias entre o ponto de Torricelli e os trˆes pontos dados. De facto, quando mostramos que o ponto de Torricelli ´e o ponto que minimiza as distˆancias aos v´ertices do triˆangulo inicial, provamos que o comprimento de cada segmento de Simpson ´e exatamente igual `a soma das distˆancias entre o ponto de Torricelli e os trˆes pontos dados (ver Figura 2.10). Figura 2.10: Rota¸c˜ao do triˆangulo [AT B] de centro em Be amplitude 60ono sentido de TB para AB eCR =AT +BT +CT 23 Vejamos uma prova direta de que os segmentos de Simpson tˆem todos o mesmo comprimento. Consideremos o triˆangulo formado pelos trˆes pontos dados e os triˆangulos equil´ateros constru´ıdos externamente sobre os lados do triˆangulo inicial. Cada um destes novos triˆangulos acrescidos do triˆangulo inicial comp˜oe um quadril´atero. Consideremos ent˜ao as diagonais desses trˆes quadril´ateros (segmentos de Simpson) (ver Figura 2.9). Figura 2.11: Rota¸c˜ao de centro em A e amplitude 60odo triˆangulo [ABQ] Se efetuarmos uma rota¸c˜ao com centro em A de 60ono sentido de [AQ] para [AB] do triˆangulo assinalado na figura 2.11, verificamos que a primeira diagonal vai coincidir com a segunda. E de modo an´alogo, com a terceira, o que permite afirmar que as trˆes diagonais tˆem o mesmo comprimento. Fica assim provado que os segmentos de reta de Simpson tˆem todos o mesmo comprimento e que este comprimento ´e igual `a soma das distˆancias entre o ponto de Torricelli e os trˆes pontos dados. Todos os resultados apresentados at´e agora nesta sec¸c˜ao partiram, como foi referido, do pressuposto que os ˆangulos internos do triˆangulo formado pelos trˆes pontos dados no Problema de Fermat tˆem amplitude inferior a 120o. O que acontece ent˜ao quando o triˆangulo inicial tem um ˆangulo interno com amplitude 120o? Consideremos o triˆangulo [ABC] em que o ∠CAB = 120o. Qual ser´a a solu¸c˜ao do Problema de Fermat nestas circunstˆancias? Ser´a poss´ıvel seguir a linha de pensamento de Torricelli? Vejamos. Seja C1a circunferˆencia que circunscreve o triˆangulo equil´atero [ACQ] constru´ıdo externamente sobre o lado [AC] do triˆangulo inicial [ABC], C2a circunferˆencia que circunscreve o triˆangulo equil´atero [ABR] constru´ıdo externamente sobre o lado [AB] e C3a circunferˆencia que circunscreve o triˆangulo equil´atero [BCP] constru´ıdo externamente sobre o lado [BC]. Comecemos por ver que as circunferˆencias C1eC2s˜ao tangentes no ponto A. A mediatriz de qualquer corda de uma circunferˆencia cont´em o centro dessa circunferˆencia, portanto a mediatriz de [CQ] cont´em o centro de C1e a mediatriz de [BR] cont´em o centro de C2. 24 Figura 2.12: C1,C2eC3intersetam-se em A Para al´em disso, facilmente se constata que a mediatriz de [CQ] cont´em o ponto A, visto [CQ] ser o lado oposto a Ado triˆangulo equil´atero [ACQ]. De modo an´alogo, a mediatriz de [BR] cont´em tamb´em o ponto A. Ent˜ao, falta apenas aver´ıguar se os centros de C1eC2e o ponto As˜ao pontos colineares, o que implicar´a que as circunferˆencias s˜ao tangentes em A. Designemos o centro da circunferˆencia C1por O1e o centro da circunferˆencia C2por O2. Ora, uma das condi¸c˜oes iniciais ´e que ∠CAB = 120o. Por outro lado, ∠O1AC =∠BAO2= 30o. Ent˜ao, ∠O1AC +∠CAB +∠BAO2= 180o. Logo, O1,O2eAs˜ao colineares, o que permite concluir que as circunferˆencias C1eC2s˜ao tangentes no ponto A. Falta agora mostrar que C3interseta C1eC2tamb´em no ponto A. Se a soma dos dois ˆangulos opostos num quadril´atero for 180o, ent˜ao o quadril´atero pode ser inscrito numa circunferˆencia.Ora, ∠CAB +∠CPB = 120o+ 60o= 180o. Como h´a uma ´unica circunferˆencia contendo os pontos C,BeP,C3cont´em o ponto A. Como j´a foi referido atr´as, C1eC2apenas se intersetam em A, logo C1,C2eC3intersetam-se no ponto A. Posto isto, quando o triˆangulo inicial tem um ˆangulo com amplitude de 120o, as circunferˆencias que circunscrevem os triˆangulos equil´ateros constru´ıdos externamente sobre os lados do triˆangulo dado intersetam-se no v´ertice onde ocorre o ˆangulo de 120o. Ser´a que a propriedade que Cavalieri apresentou para o ponto de Torricelli tamb´em se verifica para este novo ponto? “Os ˆangulos entre os segmentos de reta formados pelos v´ertices do triˆangulo e o ponto de Torriceli s˜ao iguais entre si, e iguais a 120o?”Nestas circunstˆancias, o nosso novo ponto ´e exatamente um v´ertice do triˆangulo, o que implica que s´o se obtenham dois segmentos de reta, que realmente formam um ˆangulo de 120o. E segmentos de Simpson? Far´a sentido consider´a-los? 25 Figura 2.20: Problema de Steiner com quatro pontos aaa “Dados npontos, encontrar um sistema de segmentos de reta, tal que a soma dos seus comprimentos seja m´ınima, de tal forma que quaisquer dois dos pontos dados possam ser unidos por um conjunto de segmentos de reta do sistema.” [18] Estes pontos que se acrescentaram nas situa¸c˜oes da Figura 2.20 (ii) e 2.20 (iii) designamse por Pontos de Steiner. 32 Cap´ıtulo 3 ´ Arvores geradoras minimais No cap´ıtulo anterior ficou claro que, quer para o caso particular de trˆes pontos (Problema de Fermat), quer para qualquer conjunto de npontos, a resolu¸c˜ao do Problema de Steiner passa pela constru¸c˜ao de uma estrutura de comprimento m´ınimo, estrutura esta que poder´a ligar somente os pontos dados, ´ Arvore Geradora Minimal, ou abranger alguns pontos extra. A Figura 3.1 apresenta a liga¸c˜ao de menor comprimento entre 29 cidades americanas. Como se pode constatar pela observa¸c˜ao da imagem, esta minimiza¸c˜ao do comprimento foi conseguida com recurso a outros pontos que n˜ao as 29 cidades iniciais. A apresenta¸c˜ao, an´alise e discuss˜ao do Problema de Steiner necessita de um conhecimento b´asico de teoria de grafos, de algoritmos e de complexidade computacional. A leitura deste cap´ıtulo permite a aquisi¸c˜ao de conceitos b´asicos nestas trˆes ´areas, facilitando assim o acompanhamento dos restantes cap´ıtulos. As principais referˆencias utilizadas para este cap´ıtulo foram [8, 17, 30, 45]. Figura 3.1: Liga¸c˜ao entre 29 cidades com recurso a uma ´arvore - retirada de [4] 33 3.1 Conceitos e resultados iniciais em teoria de grafos Os conceitos apresentados nesta sec¸c˜ao, para al´em das obras j´a referidas, tˆem por base os apontamentos da disciplina de M´etodos Finitos do Professor Samuel Lopes e da Professora Leonor Moreira. Um grafo G´e um par (V, E), onde V´e um conjunto finito e n˜ao vazio e E´e um conjunto de pares n˜ao ordenados de elementos de V. Os elementos de Vs˜ao chamados v´ertices e os elementos de Es˜ao chamados arestas . Se uevs˜ao v´ertices em Ve{u, v}, ou simplesmente uv, ´e uma aresta em E, ent˜ao ue vdizem-se as extremidades da aresta uv. Dizemos, ent˜ao que uevs˜ao adjacentes ou vizinhos. Qualquer grafo pode ser representado no plano por um diagrama, em que cada v´ertice ´e representado por um ponto e cada aresta por uma linha, de tal modo que dois pontos est˜ao ligados por uma linha se e s´o se os v´ertices que lhe correspondem s˜ao adjacentes (ver Figura 3.2). Figura 3.2: Representa¸c˜ao no plano do grafo G1 G1= (V, E) V={v1, v2, v3, v4, v5, v6} E={v1v2, v1v3, v1v4, v2v3, v2v5, v3v4, v3v5, v4v6, v5v6} aaaaaa aaa aaa aaa Uma outra representa¸c˜ao de grafos muito utilizada ´e a representa¸c˜ao pela matriz de adjacˆencia do grafo. Dado um grafo G, com nv´ertices, designa-se por matriz de adjacˆencia de G,AG= (aij), a matriz de dimens˜ao n×n, tal que aij ´e igual ao n´umero de arestas que ligam os v´ertices vievj. AG1=         011100 101010 110110 101001 011001 000110         Matriz de Adjacˆencia do grafo G1. Ograu de um v´ertice v´e o n´umero de arestas incidentes em v, e designa-se por deg(v). 34 Asequˆencia de graus de G´e a sequˆencia dos graus dos v´ertices de G, ordenados por ordem decrescente. Por exemplo, a sequˆencia de graus do grafo G1, representado na figura 3.2, ´e (4,3,3,3,3,2). AAA Teorema 1. Em qualquer grafo Ga soma dos graus dos v´ertices ´e igual ao dobro do n´umero de arestas: Pv∈V(G)deg(v)=2|E(G)|. Demonstra¸c˜ao. Consideremos o grafo G(V, E) onde V(G) = {v1, v2, ..., vn}eE(G) = {e1, e2, ..., ek}, e a respetiva matriz de adjacˆencia AG= (aij). A soma das entradas da linha correspondente ao v´ertice vi´e igual a deg (vi), ent˜ao, a soma de todas as entradas da matriz AG´e igual a Pv∈V(G)deg(v). Por outro lado, a soma de todas as entradas da matriz AG´e igual ao dobro do n´umero de arestas. A aresta eique liga os v´ertices vievi+1 ´e contabilizada na linha correspondente ao v´ertice vie novamente contabilizada na linha correspondente ao v´ertice vi+1. Ent˜ao, Pv∈V(G)deg(v)=2|E(G)|. Dois grafos GeG’ dizem-se isomorfos se existir uma bijec¸c˜ao f:V(G)→V(G0) tal que ∀x, y ∈V(G)({x, y} ∈ E(G)⇔ {f(x), f(y)} ∈ E(G0)) (ver Figura 3.3). Figura 3.3: Dois grafos isomorfos G∼ =G0 f:V(G)→V(G0) a ,→1 b ,→3 c ,→2 d ,→5 e ,→4 Se G= (V, E) ´e um grafo, dizemos que G0= (V0, E0) ´e um subgrafo de (V, E) se V0´e um subconjunto de VeE0um subconjunto de EeG0´e grafo. Um subgrafo G’ diz-se gerador do grafo Gse ´e um subgrafo de GeV(G0) = V(G). Um subgrafo G0= (V0, E0) diz-se induzido de G= (V, E) se E’ for o conjunto de todas as arestas de Gcom ambas as extremidades em V’. Um grafo diz-se completo , e designa-se por Kn, se |V|=ne se cada par de v´ertices distintos formar uma aresta (ver Figura 3.4). aaa aaa aaa 35 Figura 3.4: Grafo completo K5 Dado um grafo G, designa-se por passeio em Gqualquer sequˆencia n˜ao vazia P= v0e1v1e2...eivi, em que v0, v1, ..., vi∈V(G), e1, e2, ..., ei∈E(G) e os v´ertices vk−1evks˜ao extremos da aresta ek. Consideremos o grafo G2= (V2, E2) representado na figura 3.5, onde V2={v1, v2, v3, v4} eE2={e1, e2, e3, e4, e5}. Figura 3.5: Grafo G2 A sequˆencia P=v1e2v3e4v2e1v1e3v4define um passeio em G2. Quando n˜ao h´a repeti¸c˜ao de arestas, um passeio designa-se por atalho. Quando n˜ao h´a repeti¸c˜ao de v´ertices um passeio diz-se um caminho. A sequˆencia C=v1e2v3e4v2e5v4define um caminho em G2. Um circuito ´e um atalho fechado, isto ´e, em que o v´ertice inicial e o terminal coincidem. Sempre um circuito cont´em todas as arestas do grafo dizemos tratar-se de um circuito euleriano. Um ciclo ´e um grafo com o mesmo n´umero de v´ertices e de arestas, cujos v´ertices podem ser dispostos em c´ırculo, de forma que dois v´ertices s˜ao adjacentes se e s´o se s˜ao consecutivos no c´ırculo. A sequˆencia C1=v1e1v2e5v4e3v1define um ciclo em G2. Um grafo Gdiz-se conexo se, para qualquer par dos seus v´ertices existir um caminho que os liga. Caso contr´ario diz-se desconexo. Qualquer grafo desconexo Gpode ser expresso como uni˜ao de subgrafos conexos maximais designados por componentes conexas de G. Na verdade Gtem exatamente duas componentes conexas. 36 AAA Teorema 2. Seja G(V, E)um grafo conexo com nv´ertices. Ent˜ao, Gtem, pelo menos, (n−1) arestas. Demonstra¸c˜ao. Provemos, por indu¸c˜ao em n: Para n= 1, s´o h´a um grafo, conexo, e a propriedade referida atr´as verifica-se, pois Gn˜ao tem arestas. Admitamos, por hip´otese de indu¸c˜ao, que todo o grafo conexo G(V, E), tal que |V(G)|=n tem, pelo menos, (n−1) arestas e seja G0(V0, E0), um grafo conexo tal que |V0(G0)|=n+ 1. Admitamos, por redu¸c˜ao ao absurdo, que |E0(G0)| ≤ n−1; neste caso, se todos os v´ertices de G0tiverem grau 2 ou superior, pelo Teorema 1, obt´em-se 2(n+ 1) ≤2(n−1) ⇔2≤ −2; portanto G0tem pelo menos um v´ertice de grau 1. Ao eliminarmos este v´ertice obtemos um grafo conexo com nv´ertices. Por hip´otese de indu¸c˜ao, Gtem pelo menos (n−1) arestas. Logo, G0tem pelo menos (n−1 + 1) = narestas. Em Teoria de Grafos podemos definir diversas opera¸c˜oes, nomeadamente a remo¸c˜ao de arestas ou v´ertices. Seja G= (V, E) um grafo qualquer. Designamos por G\vo grafo que se obt´em ao remover o v´ertice vdo grafo Ge todas as arestas que lhe s˜ao incidentes: G\v= (V\{v}, E \{ todas as arestas incidentes em v}). Designamos por G\eo grafo que se obt´em ao remover a aresta edo grafo G: G\e= (V, E \{e}). Um v´ertice vde um grafo conexo G= (V, E) diz-se um v´ertice de corte se G\vfor desconexo. De modo an´alogo, uma aresta ede um grafo conexo Gdiz-se aresta de corte (ou ponte) se G\efor desconexo. Vejamos, a t´ıtulo de exemplo, o que acontece ao grafo G3 (ver Figura 3.6) quando removemos o v´ertice v5. Ora, ao removermos o v´ertice v5temos que remover tamb´em todas as arestas que lhe s˜ao incidentes. Assim, obt´em-se um novo grafo, desconexo, com duas componentes conexas. Logo, v5´e um v´ertice de corte de G3. De modo an´alogo, quando removemos a aresta e1de G3obtemos um novo grafo, desconexo, com duas componentes conexas. Ent˜ao, e1´e aresta de corte de G3. Figura 3.6: Grafo G3 37 Observemos ainda que se Gn˜ao tem ciclos e e∈E(G) ent˜ao G\e´e desconexo porque se existisse um caminho a ligar xayem G\e, esse caminho juntamente com a aresta eformam um ciclo de G.(2) Um grafo com peso ´e um grafo em que a cada aresta ´e associado um n´umero real, isto ´e, ao qual est´a associada uma fun¸c˜ao ω:E→R. Este peso pode representar comprimento, tempo, custo, ou outra coisa qualquer que a modela¸c˜ao do problema em quest˜ao exija. A soma dos pesos de todas as arestas ´e o peso total do grafo. Assim, ω(G) = Pei∈E(G)ω(ei). Ao longo do texto ser˜ao usadas as express˜oes “peso do grafo”, “custo do grafo”e “comprimento do grafo”, todas elas com o mesmo significado. Figura 3.7: Grafo com peso Um grafo simples G´e uma ´arvore se e s´o se for um grafo conexo sem ciclos, como no exemplo da Figura 3.8. Figura 3.8: Exemplo de uma ´arvore Como veremos a seguir as ´arvores gozam de v´arias propriedades interessantes que as tornam num tipo de grafo muito especial. aaa aaa Teorema 3. Seja G(V, E)um grafo finito e |V(G)|=n. As afirma¸c˜oes seguintes s˜ao equivalentes: 1. G´e uma ´arvore; 2. Gn˜ao cont´em ciclos e tem n−1arestas; 3. G´e conexo e tem n−1arestas; 38 4. G´e conexo e toda a aresta ´e uma aresta de corte; 5. Todo o par de v´ertices de G´e ligado por um ´unico caminho; 6. Gn˜ao cont´em ciclos, mas a adi¸c˜ao de uma aresta produz um ciclo. Demonstra¸c˜ao. (1) ⇒(2) Por indu¸c˜ao matem´atica sobre o n´umero de v´ertices n: Para n= 1, a implica¸c˜ao verifica-se uma vez que a ´unica ´arvore com 1 v´ertice tem 0 arestas. Suponhamos que a implica¸c˜ao ´e verdadeira para todas as ´arvores com menos de n≥2 v´ertices. Por defini¸c˜ao, Gn˜ao cont´em ciclos, logo, como observamos em (2), a remo¸c˜ao de qualquer aresta, subdivide o grafo em duas componentes, G0eG00, que s˜ao ´arvores. Suponhamos agora que G0tem n0v´ertices e que G00 tem n00 v´ertices, tal que n0+n00 =n. Por hip´otese de indu¸c˜ao, |E(G0)|=n0−1 e |E(G00)|=n00 −1. Ent˜ao, o n´umero total de arestas ´e dado por |E(G)|=|E(G0)|+|E(G00)|+ 1 = n0−1 + n00 −1 + 1 = n−1. (2) ⇒(3) Suponhamos que Gn˜ao ´e conexo. Ent˜ao, cada componente de G´e um grafo conexo sem ciclos, pelo que, por hip´otese, o n´umero de v´ertices de cada componente excede em uma unidade o n´umero de arestas. Logo, o n´umero total de v´ertices de G, excede o n´umero total de arestas de Gem pelo menos duas unidades, o que contradiz a hip´otese de Gter n−1 arestas. (3) ⇒(4) Como G´e conexo, com n−1 arestas, a remo¸c˜ao de qualquer aresta produz um grafo com nv´ertices e n−2 arestas. Mas, um grafo conexo com nv´ertices tem, pelo menos, n−1 arestas, como j´a foi provado no teorema 2. Ent˜ao, o grafo que se obt´em ap´os a remo¸c˜ao da aresta n˜ao ´e conexo. (4) ⇒(5) Dados dois v´ertices quaisquer v1ev2, por defini¸c˜ao de grafo conexo, existe um caminho Pque liga v1av2. Por hip´otese, qualquer aresta do caminho P´e uma aresta de corte, ent˜ao, esse caminho ´e ´unico. (5) ⇒(6) Suponhamos que Gcont´em um ciclo. Ent˜ao, quaisquer dois v´ertices desse ciclo est˜ao ligados por, pelo menos, dois caminhos. Logo, existem pelo menos dois v´ertices de Gque est˜ao ligados por mais do que um caminho. Assim, podemos concluir que se entre quaisquer dois v´ertices de Gexiste um ´unico caminho, ent˜ao Gn˜ao cont´em ciclos. Al´em disso, se juntarmos uma nova aresta e=xy a ligar dois v´ertices distintos de G, essa aresta juntamente com o caminho que os liga forma um ciclo. (6) ⇒(1) Suponhamos que Gsatisfaz a hip´otese, mas n˜ao ´e conexo (o contr´ario do que pretendemos mostrar). Se acrescentarmos uma aresta a Gque ligue dois v´ertices que perten¸cam a componentes distintas, n˜ao se forma nenhum ciclo, o que ´e uma contradi¸c˜ao. AAA Teorema 4. Cada ´arvore n˜ao trivial cont´em pelo menos dois v´ertices de grau um. Demonstra¸c˜ao. Seja Guma ´arvore n˜ao trivial com nv´ertices e com a sequˆencia de graus d1≤d2≤... ≤dn. Suponhamos, por redu¸c˜ao ao absurdo, que Gtem no m´aximo um v´ertice de grau 1. Ent˜ao, d1≥1 e ∀2≤i≤n, di≥2.Ent˜ao, 39 2(n−1) = 2 |E(G)| e, como se provou no Teorema 1, 2|E(G)|=P1≤j≤ndj=d1+P2≤j≤ndj≥1 + 2(n−1) o que ´e absurdo. Assim, pelo menos dois dos v´ertices de Gtˆem grau 1. 3.2 Constru¸c˜ao da ´ Arvore Geradora Minimal de um grafo Dado um grafo G, designa-se por ´arvore geradora de G, todo o subgrafo gerador de Gque ´e uma ´arvore. Na figura 3.9 podemos observar um grafo G4seguido de duas ´arvores geradoras para esse mesmo grafo. Figura 3.9: Um grafo G4e duas das suas ´arvores geradoras T1eT2 Quando estamos perante grafos com pesos podemos qualificar as suas ´arvores geradoras atrav´es da soma total dos pesos das arestas. Claro que esta carateriza¸c˜ao conduz a um problema muito interessante e fulcral para o estudo em quest˜ao nesta disserta¸c˜ao: como identificar uma ´arvore que minimiza essa soma? Uma tal ´arvore designa-se por ´ Arvore Geradora Minimal. Ent˜ao, se G(V, E) ´e um grafo finito conexo e cada aresta possui um peso conhecido ω(e), o problema da ´arvore geradora minimal ´e encontrar uma ´arvore geradora, G0(V, E0), para a qual a soma dos pesos das arestas seja m´ınima. AAA aaa Teorema 5. Todo o grafo conexo admite uma ´arvore geradora. Demonstra¸c˜ao. Seja G(V, E) um grafo conexo. Procuremos ent˜ao uma aresta em Gque possa ser removida sem que o grafo fique desconexo. Bem , ou tal aresta n˜ao existe e, por conseguinte, j´a encontr´amos uma ´arvore geradora, ou, a tal aresta existe e ent˜ao procedemos `a sua remo¸c˜ao. Vamos repentindo o processo at´e ocorrer a primeira situa¸c˜ao. 40 O estudo do Problema de Steiner envolve o estudo de ´arvores geradoras. O teorema seguinte, conhecido como Teorema de Cayley, conta o n´umero de ´arvores geradoras de um grafo completo. Teorema 6. O n´umero de ´arvores geradoras do grafo completo de ordem n∈N´e dado por nn−2. Figura 3.10: Todas as ´arvores geradoras de 4 v´ertices O diagrama da Figura 3.10 comporta todas as ´arvores geradoras com 4 v´ertices. Observese que as ´arvores est˜ao etiquetadas. Rapidamente se constata que os elementos de cada coluna podem ser obtidos a partir de uma rota¸c˜ao dos elementos da primeira coluna. Todos os grafos do diagrama s˜ao diferentes, uma vez que cada um tem um conjunto diferente de adjacˆencias. Vejamos, por exemplo, 1 ´e adjacente a 3 no primeiro grafo, o que j´a n˜ao se verifica no segundo. O resultado do Teorema 6, deduzido por Arthur Cayley, em 1889, pode ser demonstrado de diversas formas (consultar [1]). Nesta disserta¸c˜ao opt´amos por fazer uma prova estabelendo uma bije¸c˜ao entre o conjunto das ´arvores geradoras e um outro conjunto cujo n´umero de elementos seja j´a conhecido. O que se pretende ´e encontrar uma bije¸c˜ao entre o conjunto das sequˆencias compostas por n−2 elementos escolhidos entre n, (p1, p2, ..., pn−2) tais que 1 ≤pi≤n, de que sabemos o cardinal (n×n×... ×n | {z } n−2 ) e o conjunto das ´arvores geradoras com nv´ertices. Seja T= (V, E) uma ´arvore. Iniciemos uma sequˆencia Sde v´ertices vazia. Comecemos 41 AAA AAA Algoritmo de Prim O algoritmo de Prim, tamb´em conhecido como algoritmo do vizinho mais pr´oximo, come¸ca por escolher um v´ertice arbitr´ario v, a partir do qual se escolhe a aresta ede menor peso de entre as que lhe s˜ao incidentes. Em cada fase ´e adicionada `a ´arvore a aresta de custo m´ınimo com um v´ertice pertencente `a ´arvore do passo anterior e outro n˜ao. Assim, em cada passo temos uma ´arvore (grafo conexo com n−1 arestas). O processo termina quando todos os v´ertices do grafo inicial est˜ao inseridos na ´arvore. Procedimento: 1. Escolher um v´ertice arbitr´ario v. 2. Escolher a aresta de menor peso incidente num dos v´ertices da ´arvore e noutro v´ertice que ainda n˜ao perten¸ca `a ´arvore. Esta aresta e este novo v´ertice s˜ao anexados `a ´arvore referida. 3. a) Se a ´arvore obtida contiver todos os v´ertices do grafo inicial, o algoritmo p´ara. b) Se a ´arvore obtida n˜ao contiver todos os v´ertices do grafo inicial, repete-se o passo anterior. AAA Grafo inicial G= (V, E). O algoritmo de Prim come¸ca por escolher um v´ertice arbitr´ario. Seja A esse v´ertice. T0({A}, φ) AAA AAA Efetua-se o segundo passo: escolher a aresta de menor peso incidente num dos v´ertices da ´arvore e noutro v´ertice que ainda n˜ao perten¸ca `a ´arvore. T1({A, B},{AB}) Como a ´arvore T1ainda n˜ao cont´em todos os v´ertices de G, o processo repete-se. AAA AAA Repete-se o segundo passo. T2({A, B, C},{AB, BC}) Como a ´arvore T2ainda n˜ao cont´em todos os v´ertices de G, o processo repete-se. AAA AAA Repete-se o segundo passo. T3({A, B, C, D},{AB, BC, CD}) Como a ´arvore T3ainda n˜ao cont´em todos os v´ertices de G, o processo repete-se. AAA 48 AAA Repete-se o segundo passo. T4({A, B, C, D, E},{AB, BC, CD, DE}) Como a ´arvore T4ainda n˜ao cont´em todos os v´ertices de G, o processo repete-se. AAA AAA Repete-se o segundo passo. T5({A, B, C, D, E, F},{AB, BC, CD, DE, EF }) Como V(T5) = V(G) o algoritmo p´ara. AAA AAA T5´e a ´arvore geradora minimal obtida a partir da aplica¸c˜ao do Algoritmo de Prim. AAA 3.3 Algoritmos e Complexidade Computacional A Complexidade Computacional ´e uma ´area de estudo que alia a Matem´atica `a Ciˆencia da Computa¸c˜ao e que estuda a classifica¸c˜ao de problemas com base na complexidade dos algoritmos que os resolvem. Designamos por problemas computacionais, ou problemas algor´ıtmicos, uma vez que todos s˜ao resolvidos com recurso a algoritmos, aqueles que s˜ao adequados para ser resolvidos recorrendo ao computador e que tˆem um conjunto de resultados claramente definido. Na sec¸c˜ao anterior s˜ao apresentados alguns algoritmos para obter ´arvores geradoras minimais. Mas o que ´e afinal um algoritmo? Um algoritmo ´e uma sequˆencia finita de instru¸c˜oes, n˜ao amb´ıguas, que podem ser executadas num computador para se resolver um determinado problema. Por vezes, os algoritmos n˜ao devolvem a resposta exata ao problema dado e nestas circunstˆancias assumem a designa¸c˜ao de heur´ısticas. Recorremos a heur´ısticas sempre que o tempo gasto pelo melhor algoritmo que existe para o problema ´e maior do que o dispon´ıvel ou a quantidade de mem´oria necess´aria para resolver o problema ´e maior do que a quantidade de mem´oria dispon´ıvel ou ainda quando n˜ao se sabe como resolver o problema de forma exata. No que concerne `a complexidade dos algoritmos averigua-se quais s˜ao os requisitos de tempo e de mem´oria de um determinado algoritmo em fun¸c˜ao do tamanho dos dados. Relativamente `a complexidade de problemas averigua-se qual ´e a complexidade do algoritmo de menor complexidade que resolve o problema. A complexidade de um algoritmo ou de um problema ´e dita polinomial se ´e limitada por um polin´omio, e ´e dita exponencial se cresce de acordo com a fun¸c˜ao exponencial. 49 Os problemas computacionais podem ser agrupados em trˆes tipologias distintas, mediante a resposta que se procura: •Problema de decis˜ao Um problema de decis˜ao ´e um problema onde as ´unicas respostas poss´ıveis s˜ao sim ou n˜ao (ou 1 ou 0). •Problema de busca Um problema de pesquisa ´e um problema em que o objetivo ´e encontrar umas das muitas respostas poss´ıveis. •Problema de otimiza¸c˜ao Um problema de otimiza¸c˜ao ´e um problema em que o objetivo ´e encontrar a melhor resposta poss´ıvel, a solu¸c˜ao ´otima. Um algoritmo designa-se por algoritmo determin´ıstico se a cada instante, o passo seguinte ´e especificado, isto ´e, se o c´alculo do passo seguinte depende apenas do valor que o algoritmo est´a a ler naquele instante e da pr´oxima instru¸c˜ao algor´ıtmica. Os problemas computacionais podem ainda ser agrupados em classes mediante a sua complexidade computacional. Consideremos duas dessas classes: a classe Pe a classe NP . Um problema computacional pertence `a classe de complexidade Pquando ´e pass´ıvel de ser resolvido com recurso a uma fun¸c˜ao polinomial, o que implica uma resolu¸c˜ao num curto per´ıodo de tempo (tempo polinomial). Este tipo de problemas s˜ao resolvidos por algoritmos determin´ısticos e s˜ao, geralmente, designados por problemas de resolu¸c˜ao eficiente. Um problema computacional pertence `a classe de complexidade NP se se trata de um problema de resolu¸c˜ao polinomial, mas que apenas pode ser resolvido por um algoritmo n˜ao determin´ıstico. Dois problemas tˆem complexidade teoricamente semelhante quando pertencem `a mesma classe de complexidade. Garey, Graham e Johnson [27] mostraram que o Problema de Steiner ´e NP-dif´ıcil e re´une tanto carater´ısticas de um problema cont´ınuo quanto de um problema discreto. Posto isto, ´e pertinente a utiliza¸c˜ao de algoritmos heur´ısticos. 50 Cap´ıtulo 4 ´ Arvores de Steiner Ao longo deste cap´ıtulo estudaremos as ´ Arvores de Steiner: tipos de ´arvores, propriedades b´asicas, unicidade, metodologia de constru¸c˜ao e outros resultados pertinentes. Para al´em das referˆencias feitas ao longo do cap´ıtulo recomenda-se a leitura de [13, 25]. 4.1 Alguns conceitos preliminares Na sec¸c˜ao 2.2 foi enunciado o Problema de Steiner generalizado, segundo Courant e Robbins [18]: “Dados vpontos, encontrar um sistema de segmentos de reta, tal que a soma dos seus comprimentos seja m´ınima e de tal forma que quaisquer dois dos pontos dados possam ser unidos por um conjunto de segmentos de reta do sistema.” Foi referido que o Problema de Steiner tem diversas vers˜oes, mediante o conjunto a que pertencem os pontos iniciais. Assim, o Problema de Steiner pode, por exemplo, ser estudado em teoria de grafos ou como um problema geom´etrico. Figura 4.1: Resolu¸c˜ao do Problema de Steiner em Grafos para os quatro v´ertices iniciais A, B,CeD Assim o Problema de Steiner em Grafos consiste em, dado um grafo e uma fun¸c˜ao peso associada `as suas arestas, determinar uma ´arvore geradora minimal desse grafo (ver Figura 4.1). A resolu¸c˜ao deste problema foi descrita no cap´ıtulo anterior. Para uma leitura 51 complementar recomendamos [15, 43, 53, 55]. Ao estudarmos o Problema de Steiner como um problema geom´etrico em Rntemos que explicitar a m´etrica que ser´a considerada. A t´ıtulo de exemplo referimos as m´etricas euclideana e retil´ınea. O Problema de Steiner Retil´ıneo [28, 33] tem como objetivo encontrar um sistema de segmentos de reta que ligue os pontos dados inicialmente utilizando apenas liga¸c˜oes horizontais ou verticais e tal que a soma dos seus comprimentos seja m´ınima. J´a o Problema de Steiner Euclideano tem como objetivo encontrar a rede de comprimento m´ınimo que ligue os vpontos dados em Rn, em que a distˆancia entre os pontos ´e determinada recorrendo `a distˆancia euclideana [34, 71, 75]. A figura 4.2 apresenta duas resolu¸c˜oes do Problema de Steiner para cinco pontos dados, uma na m´etrica euclideana e a outra na m´etrica retil´ınea. Figura 4.2: Resolu¸c˜ao do Problema de Steiner para cinco pontos iniciais para as m´etricas Euclideana e Retil´ınea Defini¸c˜ao 1. Distˆancia euclideana entre os pontos X= (x1, x2, ..., xn)eY= (y1, y2, ..., yn) em Rn´e: d(X, Y ) = XY =p(x1−y1)2+ (x2−y2)2+... + (xn−yn)2. Este cap´ıtulo tratar´a, essencialmente, a resolu¸c˜ao do Problema de Steiner Euclideano. Assim, ser´a corrente considerar grafos mergulhados no plano cujas arestas s˜ao segmentos de reta. Estes grafos ser˜ao designados por Grafos Euclideanos. Defini¸c˜ao 2. Designamos por Grafo associado a um Problema de Steiner Euclideano, ou simplesmente, Grafo Euclideano, uma representa¸c˜ao de um grafo no espa¸co euclideano cujos v´ertices s˜ao representados por pontos desse espa¸co e cujas arestas s˜ao representadas por segmentos de reta entre os respetivos pontos. Assim, pensaremos numa ´arvore como um grafo euclideano que tem a estrutura de ´arvore. Ao longo deste cap´ıtulo, se nada for dito em contr´ario, os termos grafo e ´arvore ser˜ao sin´onimos de grafo euclideano e ´arvore euclideana, respetivamente. Neste contexto, o peso ou comprimento de uma ´arvore ´e a soma dos comprimentos das suas arestas. Ao longo do cap´ıtulo utilizaremos para as ´arvores de Steiner as nota¸c˜oes utilizadas em grafos. Sempre que existir a possiblidade de confus˜ao, ser´a feita a chamada de aten¸c˜ao para a distin¸c˜ao entre grafo e grafo euclideano. Quando for feita referˆencia a v´ertices da ´arvore de 52 Steiner estamo-nos a referir aos pontos iniciais. O peso de uma aresta da ´arvore de Steiner corresponde `a distˆancia euclideana entre os pontos que definem a respetiva aresta. Defini¸c˜ao 3. Dado um conjunto finito Xde pontos de um espa¸co euclideano designamos por ´ Arvore Geradora Minimal de X, denotado por T(X), uma ´arvore geradora minimal do grafo euclideano completo K|X|cujos pesos das arestas correspondem `as distˆancias entre os respetivos pontos de X. Realmente, a resolu¸c˜ao do problema da ´arvore de custo m´ınimo associada a um certo n´umero de pontos, que ser˜ao os v´ertices do grafo e onde o custo de cada aresta ´e a distˆancia euclideana entre os pontos correspondentes, pode ser uma solu¸c˜ao do Problema de Steiner para um determinado conjunto de pontos iniciais, como na figura 4.3 (i). No entanto, tamb´em se verificou no cap´ıtulo 2 que h´a situa¸c˜oes em que o peso da rede m´ınima s´o ´e alcan¸cado quando se acrescentam alguns pontos, como na figura 4.3 (ii) e (iii). Defini¸c˜ao 4. Dado um conjunto de pontos Vde um espa¸co euclideano Rne uma ´arvore geradora minimal Tpara um conjunto de pontos Xque cont´em o conjunto de pontos iniciais Vdefinimos Ponto de Steiner como um ponto de X\Vde grau maior ou igual a 3. Note-se que para a resolu¸c˜ao do Problema de Steiner nunca ser´a necess´ario considerar ´arvores com v´ertices adicionais de grau 0, 1 ou 2. Pontos adicionais de grau zero n˜ao contribui em nada para a resolu¸c˜ao do problema. Vejamos o que aconteceria se um ponto adicional tivesse grau 1. Um ponto adicional tamb´em n˜ao d´a origem a uma rede de custo m´ınimo, uma vez que podemos eliminar esse ponto e a aresta que lhe ´e adjacente sem desconectar a rede. Ent˜ao, e se o ponto adicional tiver grau 2? Bem, se o ponto adicional tem grau 2, significa que s´o ´e adjacente a dois pontos, pontos estes que podem ser unidos entre si por uma aresta que, pela desigualdade triangular, permite reduzir o custo da ´arvore. Figura 4.3: Exemplos de ´ Arvores com ou sem Pontos de Steiner Neste cap´ıtulo interessa-nos estudar uma opera¸c˜ao que permite aumentar o n´umero de v´ertices do grafo, de modo a obter os j´a referidos Pontos de Steiner, a opera¸c˜ao divis˜ao de um v´ertice. Uma divis˜ao de um v´ertice vconsiste em criar um novo v´ertice v0que passar´a a ser a extremidade de duas ou mais arestas incidentes em ve em unir vav0por um segmento de reta. Dizemos que a divis˜ao ´e uma δ-divis˜ao, onde δ > 0, se d(v, v0)< δ. 53 Figura 4.4: Divis˜ao do v´ertice v1 A Figura 4.4 mostra a divis˜ao do v´ertice v1, tendo surgido um novo v´ertice v0. As arestas incidentes em v1, (v1v4)e(v1v00) passam a estar incidentes em v0surgindo assim as arestas (v4v0) e (v00v0). Por ´ultimo, o v´ertice que se dividiu, v1, e o v´ertice criado, v0, s˜ao ligados por uma aresta (v1v0). Repare-se que o grafo resultante da divis˜ao de um v´ertice vdepende da escolha das arestas incidentes em vque s˜ao usadas na divis˜ao e o peso das suas arestas depende da localiza¸c˜ao do novo v´ertice v0. Uma divis˜ao de um v´ertice pode alterar o peso total do grafo, mas se o grafo inicial for ´arvore, o que resulta de uma divis˜ao ainda ser´a ´arvore. Na verdade, esta opera¸c˜ao n˜ao forma ciclos porque a ´unica aresta realmente acrescentada liga vav0que ´e um v´ertice novo. Se houvesse um ciclo contendo vou v0, ele j´a existia na estrutura antes da divis˜ao. Seja V⊆Rno conjunto dos vpontos iniciais e Xum subconjunto de pontos tamb´em do espa¸co euclideano, subconjunto este que cont´em o conjunto V:X⊇V. Ao procurar a solu¸c˜ao do Problema de Steiner para V, estamos a procurar uma ´arvore geradora minimal T(X) para conjuntos de pontos Xtal que X⊇V. Na Figura 4.5 podemos observar os quatro pontos iniciais v1, v2, v3ev4, bem como uma ´arvore geradora minimal do grafo completo K6, de v´ertices iniciais e mais dois v´ertices s1es2. Figura 4.5: K6e respetiva ´arvore geradora minimal 54 Defini¸c˜ao 5. Dado um conjunto de pontos Vde um espa¸co euclideano Rn, designa-se por ´ Arvore de Steiner para Vqualquer ´arvore geradora minimal Tpara um conjunto de pontos Xque contenha o conjunto dos pontos iniciais Ve tal que: ω(T)n˜ao pode ser localmente melhorado, isto ´e, para todo o δ > 0se T0se obtiver de T(X)por uma δ-divis˜ao de algum dos seus v´ertices, ou se algum dos pontos x∈X\Vfor deslocado por uma distˆancia inferior a δ, ent˜ao ω(T(X)) ≤ω(T0). Na Figura 4.6 temos trˆes ´ Arvores de Steiner. Figura 4.6: ´ Arvores de Steiner para 4 pontos iniciais Aquando da an´alise geom´etrica do Problema de Fermat conclu´ımos que a posi¸c˜ao do Ponto de Torricelli e n˜ao apenas o facto de estar ligado aos trˆes v´ertices iniciais era fundamental para minimizar a soma das distˆancias entre os quatro pontos. Dizemos que o grafo (n˜ao euclideano) subjacente a uma ´arvore euclideana apenas especifica as liga¸c˜oes e n˜ao as posi¸c˜oes dos pontos de Steiner. A matriz de adjacˆencia desta ´arvore, juntamente com a indica¸c˜ao dos pontos de Steiner, define aquilo que designamos por topologia da ´arvore. Defini¸c˜ao 6. Atopologia de uma ´arvore Tassociada ao conjunto Vde v´ertices iniciais e ao conjunto Sde pontos de Steiner para V´e o conjunto das conex˜oes entre os pontos iniciais, devidamente etiquetados, e os pontos de Steiner n˜ao etiquetados, isto ´e, a classe de isomorfismos de Tpara isomorfismos que fixam os v´ertices do conjunto V. Figura 4.7: ´ Arvores com a mesma topologia Defini¸c˜ao 7. A topologia associada a uma ´arvore de Steiner designa-se por Topologia de Steiner. 55 Vejamos que as ´arvores representadas na Figura 4.7 tˆem a mesma topologia. Em primeiro lugar, as duas ´arvores tˆem quatro v´ertices fixos e dois pontos de Steiner. Para al´em disso, na ´arvore representada na Figura 4.7(i) os v´ertices v1ev4est˜ao ligados a um mesmo ponto de Steiner, o mesmo acontece para os v´ertices v2ev3. Na ´arvore representada na Figura 4.7 (ii) verifica-se exatamente o mesmo. Estas duas ´arvores apenas diferem na posi¸c˜ao e na etiqueta dos pontos de Steiner. A(i)=         000010 000001 000001 000010 100101 011010         A(ii)=         000001 000010 000010 000001 011001 100110         Ao analisar as matrizes de adjacˆencia das duas ´arvores representadas na Figura 4.7 constatamos que ao permutarmos as duas ´ultimas colunas e as duas ´ultimas linhas da matriz A(ii)se obt´em a matriz a(i), isto porque se trocarmos a designa¸c˜ao atribu´ıda aos pontos de Steiner (designa¸c˜ao esta atribuida apenas para facilitar as eventuais referˆencias aos pontos de Steiner), por exemplo na Figura 4.7 (ii), obtemos exatamente a mesma ´arvore da Figura 4.7 (i) (entenda-se ´arvore como um grafo). Dito de outro modo, estas duas ´arvores s˜ao isomorfas por um isomorfismo que deixa fixo os v´ertices iniciais, isto ´e o mesmo que dizer que tˆem a mesma topologia. Figura 4.8: ´ Arvores com topologias diferentes Na ´arvore representada na Figura 4.8 (i) verificamos que os v´ertices v1ev4est˜ao ligados ao mesmo ponto de Steiner, enquanto que na ´arvore representada na Figura 4.8 (ii) v1est´a ligado a um ponto de Steiner e v4est´a ligado a outro ponto de Steiner distinto. Apesar de serem ´arvores isomorfas definem topologias distintas. 4.2 Tipos de ´ Arvores Como j´a referimos atr´as na Defini¸c˜ao 5, uma ´ Arvore de Steiner ´e uma ´arvore geradora minimal, T, para um conjunto de pontos Xque cont´em o conjunto dos pontos iniciais Ve tal que ω(T) n˜ao pode ser localmente melhorado. Ao analisar a Figura 4.9 constatamos que, das seis ´arvores apresentadas apenas duas s˜ao 56 ´ Arvores de Steiner: (i) e (ii), uma vez que as outras quatro podem originar ´arvores geradoras com menor custo efetuando a divis˜ao de um ou mais v´ertices. Observemos, por exemplo, a ´arvore (iii). Se efetu´assemos a divis˜ao do v´ertice v1colocando o novo v´ertice pr´oximo de v1 e na posi¸c˜ao do Ponto de Torricelli para v1,v2es1, obter´ıamos uma ´arvore com menor peso que a inicial. Esta situa¸c˜ao ser´a novamente abordada e mais explorada na sec¸c˜ao 4.3.1. Figura 4.9: ´ Arvores para 4 pontos iniciais A an´alise da Figura 4.9 permite ainda constatar que temos v´arias ´arvores com uma mesma topologia, por exemplo, Figura 4.9 (i) e Figura 4.9 (iv). Faz assim sentido perguntarmo-nos, para uma determinada topologia, qual das ´arvores tem menor peso. Defini¸c˜ao 8. Designamos por ´ Arvore Relativamente M´ınima a ´arvore com menor peso para uma determinada topologia. Na figura 4.9, as ´arvores (i) e (iv) tˆem a mesma topologia, mas pode ser mostrado que a ´arvore (i) ´e a ´arvore com menor peso no conjunto das ´arvores com a mesma topologia. Assim, a ´arvore (i) designa-se ´ Arvore Relativamente M´ınima. Defini¸c˜ao 9. A ´arvore de Steiner com menor peso, que se obt´em ap´os a an´alise de todas as topologias, designa-se por ´ Arvore M´ınima de Steiner. Das duas ´ Arvores de Steiner j´a identificadas na Figura 4.9, (i)e(ii), (ii) ´e a ´ Arvore M´ınima de Steiner para os quatro pontos iniciais v1,v2,v3ev4, (iii) ´e ´arvore relativamente m´ınima e (v) e (vi) s˜ao ´arvores relativamente m´ınimas tamb´em. Gilbert e Pollak [29] referem que esta ´e uma das raz˜oes para as ´arvores m´ınimas de Steiner (solu¸c˜ao do Problema de Steiner) serem dif´ıceis de determinar, o facto de uma ´arvore de comprimento m´ınimo local nem sempre representar um m´ınimo global. Observemos as ´arvores das Figuras 4.10 e 4.11. Estas duas ´arvores s˜ao ´arvores relativamente m´ınimas, isto ´e, minimais na topologia a que pertencem. No entanto, a ´arvore da Figura 4.11 tem menor peso do que a ´arvore da Figura 4.10. A ´arvore da Figura 4.11 57 mais rapidamente que a fun¸c˜ao exponencial, tornando impratic´avel o m´etodo de exaust˜ao para a procura de ´arvores m´ınimas de Steiner. 4.4 Unicidade das ´arvores relativamente m´ınimas em que os pontos de Steiner tˆem grau 3 Consideremos os vv´ertices iniciais de uma ´arvore de Steiner Te os spontos de Steiner. Designemos estes (v+s) pontos por r1, r2, ..., rv+s. Consideremos uma topologia da ´arvore Tconsiderada e a respetiva matriz de adjacˆencia: aij =1 se rirj´e aresta 0 se rirjn˜ao ´e aresta O peso da ´arvore T, n˜ao depende dos v´ertices iniciais uma vez que estes est˜ao fixos e apenas vamos mudar a posi¸c˜ao dos pontos de Steiner, e ´e dado por: ω=Pi<j aij |ri−rj| Para provar a unicidade das ´arvores relativamente m´ınimas podemos definir uma fun¸c˜ao que aplica a localiza¸c˜ao dos pontos de Steiner no conjunto dos n´umeros reais: ω:Rn×... ×Rn | {z } svezes →R Vamos come¸car por provar que se existirem duas ´arvores relativamente m´ınimas elas tˆem o mesmo peso, usando o facto desta fun¸c˜ao ser convexa. Para tal consideremos trˆes ´arvores com a mesma topologia, T,T0eT00, com v´ertices ri,r0 ier00 itais que r00 i=pri+qr0 i,p≥0, q≥0 e p+q= 1, respetivamente. Isto ´e, cada v´ertice de T00 pertence ao segmento que liga os v´ertices correspondentes de TeT0. Sejam ω,ω0eω00, respetivamente, os pesos das trˆes ´arvores T,T0eT00. Ent˜ao, ω00 =Paij r00 i−r00 j ω00 =Paij p(ri−rj) + q(r0 i−r0 j) ω00 ≤Paijp|ri−rj|+qr0 i−r0 j, ω00 ≤pω +qω0. Se TeT0fossem m´ınimos locais com pesos distintos, por exemplo, ω0< ω, ent˜ao, como q= 1 −p, ω00 ≤pω +qω0⇔ ω00 ≤pω + (1 −p)ω0⇔ ω00 ≤pω +ω0−pω0⇔ ω00 < pω0+ω0−pω0⇔ ω00 < ω0. 64 Logo, ω00 < ω, o que implicaria que Tn˜ao fosse m´ınimo local, j´a que a ´arvore T00 pode ser t˜ao pr´oxima quanto quisermos de T, o que ´e uma contradi¸c˜ao. Vamos agora provar, usando o resultado anterior, a unicidade das ´arvores relativamente m´ınimas por indu¸c˜ao no n´umero de pontos de Steiner. Quando s= 0, a topologia dada especifica todas as liga¸c˜oes e existe uma ´unica ´arvore. Basta agora aver´ıguar que se existe uma ´unica ´arvore relativamente m´ınima para problemas com (s−1) pontos de Steiner, o mesmo acontece para problemas com spontos de Steiner. Figura 4.16: s00 pertence ao segmento [ss0] e ao arco capaz de 120opara v1ev2, o que implica que s=s0=s00 Se TeT0s˜ao duas ´arvores relativamente m´ınimas, ent˜ao tˆem o mesmo comprimento (ω=ω0). E para todo p≥0, q≥0, p+q= 1, uma ´arvore T00 constru´ıda como acima tem o mesmo comprimento ωe portanto tamb´em ´e relativamente m´ınima. Nesta topologia existe pelo menos um par de v´ertices iniciais adjacentes a um mesmo ponto de Steiner, porque v≥s+ 2 e se cada v´ertice inicial fosse adjacente a diferentes pontos de Steiner esta desigualdade n˜ao se verificava. Sem perda de generalidade, sejam v1ev2dois v´ertices adjacentes ao mesmo ponto de Steiner, chamemos sa esse ponto em Tes0a esse ponto em T0. Ent˜ao, v1sesv2s˜ao arestas da ´arvore Tes00 =ps +qs0, e como 0 ≤p≤1, s00 move-se em ss0(se s6=s0). Como T00 ´e um m´ınimo local, ∠v1s00v2= 120o. Ent˜ao, s=s0=s00. Fica assim provado que se existe unicidade para (s−1) pontos de Steiner tamb´em existe para s pontos de Steiner. 4.5 Constru¸c˜ao de ´arvores relativamente m´ınimas Melzak foi o primeiro matem´atico a propor um algoritmo para resolver o Problema de Steiner Euclideano. Na sec¸c˜ao anterior prov´amos que, para cada topologia, existe no m´aximo uma ´arvore relativamente m´ınima. Notemos que a existˆencia de ´arvores m´ınimas resulta facilmente de um argumento envolvendo compacidade. Em todo o caso o algoritmo proposto por Melzak procura essa ´arvore relativamente m´ınima para cada poss´ıvel topologia e depois de obter todas essas ´arvores compara-as e seleciona a de menor peso, a ´ Arvore M´ınima de Steiner. Liang e Navara em [42] exploraram o c´alculo da posi¸c˜ao dos pontos de Steiner em R2. Sugere-se uma leitura complementar sobre o tema em [16, 79]. O processo de constru¸c˜ao que vamos apresentar foi sugerido por Melzak em [46] e 65 trabalhado por Gilbert e Pollak em [29] e por Pollak em [54], e parte do princ´ıpio que conhecemos o conjunto dos vpontos iniciais e a topologia para esse conjunto de pontos (quantos pontos de Steiner existem e quais os v´ertices iniciais adjacentes a um mesmo ponto de Steiner). Como j´a vimos apenas interessa considerar ´arvores cujos pontos adicionais s˜ao pontos de Steiner de grau 3. Por conseguinte, apenas desconhecemos as posi¸c˜oes dos pontos de Steiner no espa¸co euclideano. Por esta raz˜ao n˜ao h´a perda de generalidade em assumir que os v´ertices iniciais tˆem grau 1 e que, por conseguinte, est˜ao ligados a pontos de Steiner, uma vez que fixada a topologia as arestas entre pontos iniciais s˜ao constantes do problema. Toda a ´arvore de Steiner que n˜ao ´e completa pode ser decomposta numa uni˜ao de ´arvores de Steiner completas: substituindo cada v´ertice vique tenha grau k≥2 por knovos v´ertices vi1, vi2, ..., vik. Assim, a ´arvore inicial ´e dividida em v´arias ´arvores completas menores. Estas ´arvores completas menores designam-se por componentes completas da ´arvore inicial. De modo an´alogo, quando a topologia especificada n˜ao ´e completa obtemos as topologias das componentes completas, e com estas ´ultimas constru´ımos as componentes completas separadamente. Por fim, basta junt´a-las para obter a ´arvore de Steiner procurada. Este processo ´e dividido em duas fases: divis˜ao e reconstru¸c˜ao. Com o intuito de simplificar a linguagem utilizada vamos introduzir a defini¸c˜ao de Ponto Equil´atero. Defini¸c˜ao 13. Designamos por Ponto Equil´atero o terceiro ponto que se obt´em quando se constr´oi um triˆangulo equil´atero para dois pontos dados. A Figura 4.17 apresenta um exemplo de um Ponto Equil´atero, e dizemos que E´e um Ponto Equil´atero de AeB. Figura 4.17: Ponto Equil´atero Ede AeB Na fase da divis˜ao, reduz-se continuamente o problema de vpontos iniciais a (v−1) pontos. Assim, dado um conjunto de vv´ertices e a respetiva topologia, consideramos dois v´ertices adjacentes a um mesmo ponto de Steiner e substitu´ımos esses dois pontos por um dos seus Pontos Equil´ateros e atualizamos a topologia. O processo ´e executado at´e obtermos apenas dois v´ertices. Nesta altura inicia-se a segunda fase do processo de constru¸c˜ao da ´arvore relativamente m´ınima, a reconstru¸c˜ao. Come¸camos por construir um segmento de reta com os dois v´ertices. Um desses v´ertices ´e um Ponto Equil´atero. Esse Ponto Equil´atero ´e substitu´ıdo pelos dois pontos que o originaram (restantes v´ertices do triˆangulo equil´atero que o originou) e o Ponto de Steiner P´e o ponto de interse¸c˜ao do segmento de reta que se construiu com a circunferˆencia que circunscreve o triˆangulo equil´atero referido. Assim, o v´ertice n˜ao selecionado e os outros dois v´ertices do triˆangulo equil´atero s˜ao adjacentes a um mesmo ponto de Steiner P. Esta etapa ´e executada continuamente para todos os Pontos 66 Equil´ateros criados na fase da divis˜ao at´e que se obtenha uma ´arvore com os vv´ertices iniciais. Comecemos por analisar a primeira fase do processo de constru¸c˜ao quando s˜ao dados trˆes pontos, A,BeC. Sejam AeBdois pontos dados adjacentes a um mesmo ponto de Steiner P. Consideremos o triˆangulo equil´atero [ABD]. Harold Coxeter em [19] mostrou que o ponto de Steiner procurado, seja Pesse ponto, pertence `a reta DC e `a circunferˆencia que cont´em os pontos A,BeD. Ver Figura 4.18. Figura 4.18: Processo de constru¸c˜ao para trˆes pontos iniciais ´ E ´obvio que quando efetuamos a constru¸c˜ao do triˆangulo equil´atero podemos obter duas posi¸c˜oes distintas para o Ponto Equil´atero D, no entanto, Melzak salvaguardou esta situa¸c˜ao ao impor que o interior do triˆangulo equil´atero que se est´a a construir, neste caso [ABD], n˜ao se deve sobrepor ao interior do triˆangulo formado pelos trˆes pontos considerados, neste caso [ABC]. E como B.D. Holbrook salientou que AP +BP =DP, a ´arvore m´ınima de Steiner para um conjunto de vpontos dados, em que dois desses pontos (AeB) sejam adjacentes a um mesmo ponto de Steiner P, pode ser encontrada substituindo esses dois v´ertices AeBpelo ponto Ddo triˆangulo equil´atero [ABD] e resolvendo o problema de Steiner para (v−1) pontos, situa¸c˜ao analisada novamente mais adiante. Para este caso em que s˜ao dados trˆes pontos, o problema fica resolvido ao fim de uma etapa. Na sec¸c˜ao 2.1 j´a provamos que AP +BP +CP =DC (o comprimento de cada um dos segmentos de Simpson ([DC]) ´e igual `a soma das distˆancias entre o ponto de Torricelli (P) e os trˆes pontos dados A,BeC). Se forem dados quatro pontos, as op¸c˜oes para desenhar um segmento cujo comprimento seja igual ao comprimento de uma determinada ´arvore de Steiner completa s˜ao muitas mais, o mesmo que dizer que existem muitas mais op¸c˜oes a tomar na fase da divis˜ao at´e obter somente dois v´ertices. Consideremos os pontos iniciais B,C,EeGe a topologia apresentados na Figura 4.19, em que PeQs˜ao pontos de Steiner. Uma possibilidade, entre muitas, para chegar a dois ´unicos v´ertices ´e construir os triˆangulos equil´ateros [ABC] e [EFG], tal como se mostra na Figura 4.20. Assim, AeFs˜ao os ´ultimos dois pontos. Efetuemos agora a segunda fase do processo 67 Figura 4.19: Pontos iniciais B,C,EeGe respetiva topologia Figura 4.20: Constru¸c˜ao dos triˆangulos equil´ateros [ABC] e [EFG] de constru¸c˜ao, a reconstru¸c˜ao da ´arvore relativamente m´ınima pretendida. Comecemos por considerar o segmento de reta [AF] e as circunferˆencias que circunscrevem os triˆangulos [ABC] e [EFG]. Os pontos de interse¸c˜ao de [AF ] com essas circunferˆencias s˜ao os pontos de Steiner pretendidos, como se observa na Figura 4.21. Figura 4.21: Posi¸c˜ao dos pontos de Steiner PeQ A ´arvore relativamente m´ınima para a topologia dada ´e a que se observa na Figura 4.22. Uma outra possibilidade ´e construir apenas um destes triˆangulos equil´ateros, seja [EGF ] esse triˆangulo (ver Figura 4.23). Assim, EeGs˜ao substitu´ıdos pelo seu Ponto Equil´atero Fe o nosso problema inicial de quatro pontos ´e reduzido a um problema de trˆes pontos. J´a foi provado que uma ´arvore de 68 Figura 4.22: ´ Arvore relativamente m´ınima para os quatro pontos B,C,EeGe topologia dados Figura 4.23: O problema ficou reduzido a trˆes pontos iniciais Steiner tem, no m´aximo, v−2 pontos de Steiner, logo como o problema passou a ter somente trˆes pontos, teremos, no m´aximo, um ponto de Steiner. Pela topologia dada sabemos que P´e esse ponto. Por conseguinte, B,CeFs˜ao trˆes pontos adjacentes a um mesmo ponto de Steiner P. Por isso, podemos desenhar um outro triˆangulo equil´atero de base [CF ]. Seja [CFN] esse triˆangulo. BeNs˜ao os pontos que se obtˆem ap´os a fase da divis˜ao. Figura 4.24: BeNs˜ao os pontos obtidos ap´os a fase da divis˜ao Ao efetuarmos a fase da reconstru¸c˜ao obtemos a ´arvore relativamente m´ınima pretendida, tal como se pode observar na Figura 4.25. Come¸ca-se por obter o ponto de interse¸c˜ao do segmento de reta [BN] com a circunferˆencia que circunscreve o triˆangulo equil´atero [CFN], ponto este que nos d´a a posi¸c˜ao de um dos pontos de Steiner procurados, P. Logo de seguida 69 obtemos o ponto de interse¸c˜ao da circunferˆencia que circunscreve o triˆangulo equil´atero [EFG] com o segmento de reta [FP ], visto ser o segundo ponto de Steiner procurado, Q. Figura 4.25: ´ Arvore relativamente m´ınima para os quatro pontos B,C,EeGe topologia dados O processo que se exemplificou para trˆes e quatro pontos aplica-se a um n´umero qualquer de pontos dados desde que se conhe¸ca a posi¸c˜ao desses vpontos dados e a topologia associada, e a ´arvore relativamente m´ınima ´e constru´ıda por indu¸c˜ao no n´umero de pontos de Steiner sna qual a constru¸c˜ao de Melzak ´e utilizada v´arias vezes para localizar esses spontos de Steiner. Antes de explorarmos a situa¸c˜ao de uma forma mais gen´erica, analisemos a Figura 4.26 onde se observa a fase da divis˜ao para 5 pontos dados, A,B,C,DeEe a topolgia considerada (AeCs˜ao adjacentes ao mesmo ponto de Steiner P,BeDs˜ao adjacentes ao mesmo ponto de Steiner QeE´e adjacente ao ponto de Steiner R), e a Figura 4.27 onde se observa a fase da reconstru¸c˜ao para os mesmos 5 pontos . Figura 4.26: Fase da divis˜ao: dos 5 pontos dados obtemos somente dois, EeH O caso em que s= 0 ´e trivial. Consideremos ent˜ao o caso em que s≥1. Pretendemos mostrar que pode ser reduzido a uma ou mais ´arvores, cada qual com menos pontos de Steiner. O primeiro passo ´e descobrir um ponto de Steiner sique, nesta topologia, seja adjacente a dois v´ertices vievj. Tal ponto de Steiner, si, existe, uma vez que ao considerar qualquer componente completa com um ou mais pontos de Steiner e com v0pontos iniciais, cada um 70 Figura 4.27: Fase da reconstru¸c˜ao: os dois pontos EeHpermitem descopbrir os 3 pontos de Steiner, gradualmente destes v0pontos iniciais ´e extremidade de uma ´unica aresta, aresta esta incidente tamb´em num ponto de Steiner. Como j´a foi referido (sec¸c˜ao 4.3.3), v0=s0+ 2, ent˜ao, pelo menos um ponto de Steiner deve ser adjacente a dois pontos dados. Consideremos trˆes pontos adjacentes ao ponto de Steiner s0:vi,vjea. Se a´e um dos pontos dados, ent˜ao a constru¸c˜ao 4.28 localiza s0ou mostra que n˜ao existe solu¸c˜ao para esta topologia. Suponhamos que s0j´a foi localizado. Se removermos s0e as arestas vis0,vjs0e as0da ´arvore relativamente m´ınima obtemos trˆes ´arvores relativamente m´ınimas distintas, cada uma delas com um dos v´ertices vi,vjea. Cada uma destas ´arvores tem menos do que spontos de Steiner e pode ser constru´ıda por indu¸c˜ao. Figura 4.28: Constru¸c˜ao de s0e localiza¸c˜oes poss´ıveis de a Se a´e um ponto de Steiner, a sua localiza¸c˜ao n˜ao ´e conhecida. No entanto, o modo de constru¸c˜ao sugerido na Figura 4.28 permite aferir parcialmente essa localiza¸c˜ao. 71 Na sec¸c˜ao 2.1 foi largamente explorada a determina¸c˜ao da posi¸c˜ao do ponto de Torricelli para trˆes pontos dados, esta Figura 4.28 explora algo similar. Uma vez que apenas vie vjs˜ao pontos dados, a Figura 4.28 permite-nos analisar as zonas em que poder´a estar a localiza¸c˜ao de a. Ora vejamos. Se ase localizasse na zona amarela, ent˜ao ter´ıamos uma situa¸c˜ao em que os trˆes pontos dados(vi,vjea) formariam um triˆangulo em que um dos ˆangulos internos teria uma amplitude superior a 120oe, por conseguinte, conforme provado na sec¸c˜ao 2.1, a posi¸c˜ao do ponto de Steiner s0coincidiria com a posi¸c˜ao do v´ertice vi. Racioc´ınio an´alogo caso ase localizasse nas zonas azul ou vermelha. Apenas a zona cinzenta (neste caso estamos a considerar que a0est´a `a direita da aresta vivj) nos permite obter uma posi¸c˜ao n˜ao degenerada para a. Se a0substituir s0,viou vjconclui-se que n˜ao existe uma ´arvore relativamente m´ınima para esta topologia. O ponto a0tem somente duas localiza¸c˜oes, em lados opostos de vivj, localiza¸c˜ao esta que influenciar´a a localiza¸c˜ao de a. Tentam-se essas duas possibilidades. Se uma ´arvore relativamente m´ınima Texiste, ent˜ao pode ser constru´ıda do seguinte modo: em primeiro lugar devemos resolver o problema mais simples em que os v´ertices vi,vj es0s˜ao removidos e a0passa a ser um v´ertice. As adjacˆencias entre os pontos, com exce¸c˜ao de s0, mantˆem-se e surge uma aresta adicional aa0. Esta nova ´arvore relativamente m´ınima tem o mesmo comprimento que a anterior, uma vez que |a0a|=|vis0|+|vjs0|+|as0|. De facto, ao analisarmos a Figura 4.28 verificamos que |aa0|=|as0|+|s0a0|ent˜ao, |s0a0|=|vis0|+|vjs0|. Quando a nova ´arvore ´e encontrada, a aresta aa0pode ser substitu´ıda pelas arestas vis0, vjs0eas0de modo a obter a ´arvore desejada. Nem sempre ´e poss´ıvel aferir de imediato qual a op¸c˜ao incorreta para a posi¸c˜ao de a0, entre as duas dispon´ıveis. Este m´etodo indutivo substitui o problema com spontos de Steiner por um com (s−1). Este ´ultimo ´e substitu´ıdo por um com (s−2), e assim sucessivamente. A ´arvore relativamente m´ınima em cada um destes problemas mais simples tem o mesmo comprimento que a ´arvore relativamente m´ınima desejada. Assim, quando o problema for simplificado de tal modo que a solu¸c˜ao seja evidente, o comprimento ´e imediatamente conhecido. 72 Cap´ıtulo 5 Raz˜ao de Steiner O Problema de Steiner tem assumido um papel cada vez mais importante e continua a ser um dos problemas mais famosos da geometria combinat´oria. No entanto, todos os estudos efetuados at´e `a data mostraram tratar-se de um problema de grande complexidade, quer ao n´ıvel da estrutura quer ao n´ıvel da complexidade computacional. Ao longo das ´ultimas d´ecadas foram desenvolvidos algoritmos para determinar a localiza¸c˜ao e o n´umero de pontos de Steiner da solu¸c˜ao de um dado problema, mas nenhum deles permite apresentar a solu¸c˜ao quando ´e fornecido um grande n´umero de pontos iniciais. No entanto, foram desenvolvidos algoritmos que apresentam boas aproxima¸c˜oes da solu¸c˜ao pretendida. Estes ´ultimos s˜ao aquilo que designamos por heur´ısticas [9, 58]. Ent˜ao h´a duas quest˜oes que se colocam: •Uma vez que determinar a ´ Arvore M´ınima de Steiner ´e de grande complexidade para um grande n´umero de pontos iniciais e que, por outro lado, existem bons algoritmos para determinar a ´ Arvore Geradora Minimal, ser´a realmente compensador determinar a´ Arvore M´ınima de Steiner? •Se ao longo das ´ultimas d´ecadas foram desenvolvidos algoritmos que apresentam aproxima¸c˜oes da solu¸c˜ao pretendida como saber se a aproxima¸c˜ao ´e boa? E qual o que apresenta melhor aproxima¸c˜ao? Do ponto de vista econ´omico, o recurso `a ´ Arvore M´ınima de Steiner parece ser muito compensador comparativamente com o recurso `a ´ Arvore Geradora Minimal, por isso tornase necess´ario conhecer o erro de se construir a ´ Arvore Geradora Minimal em vez da ´ Arvore M´ınima de Steiner. Por outro lado, ´e necess´ario estabelecer uma medida que nos permita efetuar compara¸c˜oes entre as diferentes heur´ısticas e averiguar qual a qualidade de cada uma delas. Esta medida ´e a raz˜ao entre o custo de uma aproxima¸c˜ao da ´ Arvore de Steiner M´ınima e o custo da ´ Arvore Geradora Minimal, raz˜ao esta que se designa por Raz˜ao de Steiner (ρ). aaa aaa 73 Lema 8. Consideremos um quadril´atero convexo [ABCD], com ˆangulos α, β, γ, δ eθtal como representado na Figura 5.7. Ent˜ao, o ˆangulo θ´e agudo se e s´o se cotβcotα < cotγcotδ. Figura 5.7: Quadril´atero convexo [ABCD] Demonstra¸c˜ao. Designemos por h1a altura do triˆangulo [ABC] relativamente a [AC], por h2a altura do triˆangulo [ACD] relativamente a [AC] e por XeYos pontos de interse¸c˜ao. Figura 5.8: Quadril´atero convexo [ABCD] cotγ =AY h1⇔AY =h1cotγ cotβ =CY h1⇔CY =h1cotβ AC =AY +CY =h1cotγ +h1cotβ =h1(cotγ +cotβ) cotδ =XC h2⇔XC =h2cotδ cotα =AX h2⇔AX =h2cotα AC =AX +XC =h2cotα +h2cotδ =h2(cotα +cotδ) Ent˜ao, 80 h2(cotα +cotδ) = h1(cotγ +cotβ)⇔ h2=cotβ +cotγ cotα +cotδ h1.(5.1) O ˆangulo θ´e agudo se e somente se AX < AY : AX < AY ⇔h2cotα < h1cotγ (5.2) Se substituirmos 5.1 em 5.2 obtemos o resultado pretendido: cotβ +cotγ cotα +cotδ ·h1·cotα < h1cotγ ⇔ cotγcotα +cotβcotα < cotγcotα +cotγcotδ ⇔ cotβcotα < cotγcotδ Lema 9. Se existe uma topologia de Steiner completa que liga quatro pontos A,B,CeD, ent˜ao o quadril´atero formado por esses quatro pontos ´e convexo. Demonstra¸c˜ao. Seja (AB)−P−Q−(CD) a ´arvore de Steiner completa que liga A,B,C eD(ver Figura 5.9). Figura 5.9: ´ Arvore de Steiner completa (AB)−P−Q−(CD) Desenhemos a reta AX de tal modo que esta seja paralela `a reta que cont´em a aresta [BP ] e desenhemos a reta Y Z de tal modo que Y Z contenha a aresta [AP]. Ent˜ao, como os trˆes ˆangulos em Pmedem 120o,Best´a no interior do ˆangulo XAY e, portanto, numa metade do plano determinado pela reta Y Z. Como CQ ´e paralelo a Y Z e Q6=P,CeDe consequentemente o triˆangulo [ACD] est˜ao na outra metade. Assim, Bn˜ao est´a no interior do triˆangulo [ACD]. Ent˜ao, o quadril´atero [ABCD] ´e convexo, uma vez que o mesmo argumento se aplica a todos os v´ertices e o lema est´a provado. 81 Figura 5.10: Retas AX eY Z Figura 5.11: Bn˜ao est´a no interior do triˆangulo [ACD] Teorema 10. Sejam dados quatro pontos A,B,CeDde modo a que realmente existam ambas as topologias de Steiner completas. Ent˜ao, a mais curta das duas est´a no mesmo sentido que o ˆangulo agudo entre as diagonais do quadril´atero [ABCD]. As duas ´arvores de Steiner completas (dado que ambas existem) ter˜ao o mesmo comprimento se e s´o se as diagonais forem perpendiculares. Demonstra¸c˜ao. Pelo Lema 9 podemos afirmar que o quadril´atero [ABCD] ´e convexo. Se etiquetarmos os v´ertices de forma consecutiva `a volta do pol´ıgono convexo [ABCD], ent˜ao as duas topologias de Steiner completas ligam AeBaP,PaQ,QaCeD, e AeDaP0, P0aQ0,Q0aBeC, ver Figura 5.12. Analisemos cada uma delas. Podemos obter o comprimento da ´arvore de Steiner (AB)−P−Q−(CD) atrav´es da constru¸c˜ao do triˆangulo equil´atero [ABE], seguida da constru¸c˜ao do triˆangulo equil´atero [CEH]. O comprimento pretendido ´e o comprimento de [DH]. O que pretendemos mostrar ´e que DH =BP +AP +PQ +QC +QD, justifica¸c˜ao que adv´em do resultado j´a provado para trˆes pontos iniciais, na sec¸c˜ao 2.1, Problema de Fermat. Sabemos que DH =DQ +QH. Se efetuarmos a rota¸c˜ao de π 3no sentido contr´ario ao dos ponteiros do rel´ogio do triˆangulo 82 Figura 5.12: Duas topologias de Steiner completas para os quatro pontos dados A,B,Ce D Figura 5.13: DH =BP +AP +PQ +QC +QD [HQC] de centro em C, constatamos que QH =EQ1, onde Q1´e a imagem de Qpela referida rota¸c˜ao. Ent˜ao, DH =DQ +EQ1. Mas EQ1=EQ +QQ1. No entanto, o triˆangulo [CQQ1] ´e equil´atero (∠Q1CQ =π 3por ser a amplitude do ˆangulo da rota¸c˜ao e ∠CQQ1=π 3por ser suplementar do ˆangulo PQC), logo, QQ1=QC. Ent˜ao, EQ1=EQ +QC =EP +PQ +QC. De modo an´alogo, se efetuarmos a rota¸c˜ao do triˆangulo [ABP] de centro em Be amplitude π 3no sentido dos ponteiros do rel´ogio, constatamos que EP =EP1+P1P, onde P1´e a imagem de Ppela referida rota¸c˜ao. EP =AP +BP . Ent˜ao, DH =DQ +AP +BP +PQ +QC. Embora a observa¸c˜ao da Figura 5.14 nos leve a pensar que, por exemplo, CE interseta AB ou que ∠DBH < π, na realidade isto pode n˜ao acontecer. Sabemos que: AE =EB, porque o triˆangulo [ABE] ´e equil´atero; CE =EH, porque o triˆangulo [CEH] ´e equil´atero; 83 Figura 5.14: Comprimento da ´arvore de Steiner (AB)−P−Q−(CD) ∠CEA =∠HEB, porque ambos tˆem uma amplitude igual a π 3−∠CEB ou π 3+∠CEB, conforme CE intersete AB ou n˜ao; Logo os triˆangulos [CEA] e [HEB] s˜ao congruentes (L.A.L), o que implica que AC =BH e que os ˆangulos ECA eEHB tˆem a mesma amplitude: ∆[CEA]∼ =∆[HEB]⇒AC =BH ∧∠ECA =∠EHB (5.3) Designemos por Xo ponto de interse¸c˜ao de AC eBD. Ao analisar o quadril´atero [CXBH] concluimos que: ∠CXB +∠XBH = 2π−(∠XCH +∠BHC) = 2π−π 3+∠ECA +π 3−∠BHE =4π 3usando (5.3) Logo ∠DBH =4π 3−∠CXB. (5.4) A segunda topologia de Steiner considerada, (AD)−P0−Q0−(BC), pode ser representada pelo esquema da Figura 5.16, onde se construiu o triˆangulo equil´atero [CBE0], seguido do triˆangulo tamb´em equil´atero [E0AH0]. Assim, o comprimento do segmento de reta [DH0] d´a-nos o comprimento desta ´arvore. Ora, pelo argumento anterior ∠DBH0=4π 3−∠BXA. Consideremos que ∠DBH > π (e que ∠DBH0> π). Designemos por α(e α0) esse ˆangulo. Quando nos referirmos a esses ˆangulos como ˆangulos internos dos triˆangulos [DBH] e [DBH0] estes ser˜ao designados por αteα0 t. Assim, 84 Figura 5.15: Quadril´atero [CXBH] Figura 5.16: Comprimento da ´arvore de Steiner (AB)−P0−Q0−(CD) α=αtse α≤π α= 2π−αtse α > π e de forma an´aloga para α0eα0 t. Em primeiro lugar, constatamos que ´e imposs´ıvel que αeα0sejam superiores a πem simultˆaneo, uma vez que, por (5.4): 8π 3−∠CXB −∠BXA =5π 3<2π Provemos ent˜ao que α > α0se e s´o se αt> α0 t. Se α≤πent˜ao todos os ˆangulos s˜ao n˜ao superiores a πe, por conseguinte, as defini¸c˜oes s˜ao as mesmas. Se α > π ent˜ao, pela igualdade (5.3), ∠CBX < π 3e, por isso, ∠BXA > 2π 3. αt= 2π−α=2π 3+∠CBX > 2π 3, enquanto α0 t=α0(uma vez que apenas um pode exceder π) α0 t=4π 3−∠BXA < 2π 3. Assim, αt> α0 t. 85 Reciprocamente, suponhamos que αt> α0 t. Se α > π, ent˜ao α > π > αt> α0 t=α0(uma vez que apenas um pode exceder π). Se α0> π, ent˜ao, pelo argumento anterior, α0 t> αt, o que ´e uma contradi¸c˜ao. Assim, α=α0se e s´o se αt=α0 t. Sabemos ainda que: BH0=BH (pela implica¸cao (5.3) ambos s˜ao iguais a AC) [DB] ´e um lado comum aos dois triˆangulos. Se dois lados de um triˆangulo s˜ao congruentes com dois lados de um segundo triˆangulo, ent˜ao o ˆangulo formado pelos dois lados no primeiro triˆangulo excede o ˆangulo formado pelos dois lados no segundo triˆangulo se e s´o se o terceiro lado no primeiro triˆangulo exceder o terceiro lado no segundo triˆangulo. Assim, DH > DH0⇔αt> α0 t⇔α > α0⇔∠CXB < ∠BXA DH =DH0⇔αt=α0 t⇔α=α0⇔∠CXB =∠BXA Teorema 11. Sejam dados quatro pontos A,B,CeDde modo a que realmente existam ambas as topologias de Steiner completas. Ent˜ao a mais curta das duas, na dire¸c˜ao do ˆangulo agudo entre as diagonais, ´e a ´arvore m´ınima de Steiner para os pontos A,B,CeD. Demonstra¸c˜ao. O que pretendemos provar ´e que qualquer ´arvore de Steiner para os quatro pontos dados que tenha um ou nenhum ponto de Steiner ´e maior do que uma das ´arvores de Steiner completas. Pelo Lema 9, [ABCD] ´e um quadril´atero convexo. Sendo assim, devemos distinguir duas situa¸c˜oes: uma em que a ´arvore de Steiner tem um ponto de Steiner e uma segunda situa¸c˜ao em que a ´arvore de Steiner n˜ao tem qualquer ponto de Steiner. Caso 1 Seja T1uma ´arvore de Steiner com um ponto de Steiner P. Este ponto de Steiner P´e adjacente a trˆes dos pontos iniciais. Sejam A,BeCesses pontos. E D´e adjacente a A,B ou C. •Suponhamos ent˜ao que D´e adjacente a A(ou C), como na Figura 5.17. Efetuemos a constru¸c˜ao do triˆangulo equil´atero [ABE], seguida da constru¸c˜ao do triˆangulo equil´atero [CDF]. O comprimento da ´arvore de Steiner T1(AP +BP +CP +CD) ´e EC +CD =EC +CF, o que excede o comprimento de EF , comprimento de uma ´arvore de Steiner completa. •Mas Dpode ser adjacente a B. Comecemos ent˜ao por construir a mediatriz de [BP ] e analisar os dois semiplanos que essa mediatriz determina. Bpertence a um desses semiplanos. Pela convexidade j´a referida, Dpertence ao mesmo semiplano que A,PeCe como os semiplanos s˜ao 86 Figura 5.17: Uma ´arvore de Steiner com um ponto de Steiner em que D´e adjacente a C determinados pela mediatriz de [BP], sabemos que BePpertencem a semiplanos distintos. Assim, Dest´a mais pr´oximo de Pdo que de B. Ent˜ao, T1n˜ao ´e a liga¸c˜ao mais curta entre A,B,C,DeP. Figura 5.18: Uma ´arvore de Steiner com um ponto de Steiner em que D´e adjacente a B Caso 2 Seja T0uma ´arvore de Steiner sem pontos de Steiner, ou seja, uma ´arvore geradora minimal para A,B,CeD. Como o quadril´atero [ABCD] ´e convexo, ent˜ao existem trˆes poss´ıveis ´arvores m´ınimas (ver Figura 5.19). Figura 5.19: ´ Arvores de Steiner sem pontos de Steiner em que [ABCD] seja convexo Provemos ent˜ao que qualquer `arvore das trˆes apresentadas na Figura 5.19 ´e maior do que 87 uma das ´arvores de Steiner completas. 1. Efetue-se a constru¸c˜ao dos triˆangulos equil´ateros [ABE] e [CDF ]. AB +BC +CD =EB +BC +CF > EF (comprimento de uma ´arvore de Steiner completa) Figura 5.20: EB +BC +CF > EF 2. Efetue-se novamente a constru¸c˜ao dos triˆangulos equil´ateros [ABE] e [CDF ]. Ent˜ao, AB +BD +CD =EB +BD +DF ≥EF (comprimento de uma ´arvore de Steiner completa) Figura 5.21: EB +BD +DF ≥EF 3. Efetue-se a constru¸c˜ao dos triˆangulos equil´ateros [CDF] e [BFH]. Pelo argumento do Teorema 11, BD =CH, e AB +BD +BC =AB +BC +CH ≥AH (comprimento de uma ´arvore de Steiner completa). Estamos finalmente em condi¸c˜oes de provar o resultado de Polak de que a raz˜ao m´ınima de Steiner ´e ρ≥√3 2para qualquer subconjunto de quatro pontos de R2. 88 Figura 5.22: AB +BC +CH ≥AH Teorema 12. Seja ω(AMS)o peso da ´ Arvore M´ınima de Steiner para um subconjunto de quatro pontos dados de R2eω(AGM)o peso da ´ Arvore Geradora Minimal para o mesmo conjunto de pontos. Ent˜ao, ω(AMS) ω(AGM)≥√3 2 . Demonstra¸c˜ao. Se a ´ Arvore M´ınima de Steiner n˜ao tiver nenhum ponto de Steiner ent˜ao ω(AMS) = ω(AGM)⇔ω(AMS) ω(AGM)= 1 ≥√3 2. Figura 5.23: A ´ Arvore M´ınima de Steiner n˜ao tem nenhum ponto de Steiner Averiguemos agora o que acontece se a ´ Arvore M´ınima de Steiner tiver um ´unico ponto de Steiner. Se a ´ Arvore M´ınima de Steiner tem um ´unico ponto ent˜ao este ´e adjacente a trˆes dos quatro pontos dados. No in´ıcio desta sec¸c˜ao apresent´amos a prova de Gilbert e Pollak, em [29], de que ω(AMS) ω(AGM)≥√3 2para qualquer subconjunto de trˆes pontos de R2. Designemos por ω3(AMS) o peso da ´ Arvore M´ınima de Steiner para os trˆes pontos iniciais que s˜ao adjacentes ao ´unico ponto de Steiner e por ω3(AGM) o peso da ´ Arvore Geradora Minimal para os mesmos trˆes pontos. Ent˜ao j´a foi provado que ω3(AMS) ω3(AGM)≥√3 2. Portanto, se adicionarmos a liga¸c˜ao que permite juntar o quarto v´ertice verificamos que ω(AMS) ω(AGM)>√3 2. Ent˜ao, sem perda de generalidade, podemos assumir que a ´ Arvore M´ınima de Steiner ´e 89 Figura 5.36: ´ Arvore Geradora Minimal (Caso 4) Figura 5.37: ´ Arvore Geradora Minimal (Caso 4) (a) Se ∠ABE ≤π, ent˜ao o prolongamento de [AB] encontra o prolongamento de [EF] num ponto X. Com as condi¸coes descritas em (1) (a), ∠ABE ≤πe∠BEF ≤π, resulta que B∈[AX] e E∈[FX]. Pela desigualdade ∠ABE +∠BEF ≥5π 3, ∠BXE ≥2π 3. Figura 5.38: ´ Arvore Geradora Minimal quando ∠ABE ≤π Logo, 96 AF ≥√3 2(AX +XF)≥ ≥√3 2(AB +BE +EF ) = =√3 2(CB +BE +EG)≥ ≥√3 2(GC +BE +EG) O ´ultimo passo adv´em da constru¸c˜ao da ´ Arvore Geradora Minimal, BC ≥CG. (b) Se ∠ABE > π, a constru¸c˜ao da ´ Arvore Geradora Minimal permite concluir que ∠BEG ≥π 3. Logo ∠BEF ≥2π 3. Pelo Lema 7, AF ≥√3 2(AB +BE +EF ). Figura 5.39: ´ Arvore Geradora Minimal quando ∠ABE > π 2. Se ∠BEG > 2π 3ent˜ao ∠BEG +∠GEF > π. Desenhemos o triˆangulo equil´atero [CFM] de tal modo que ω(AMS) = BM. Figura 5.40: ´ Arvore Geradora Minimal quando ∠BEG > 2π 3 (a) Se ∠EGC ≥2π 3ent˜ao G´e exterior ao triˆangulo [CFM] e ∠EFM ≥2π 3. 97 Figura 5.41: ´ Arvore Geradora Minimal quando ∠BEG > 2π 3e∠EGC ≥2π 3 Pelo Lema 7, BM ≥√3 2(BE +EF +F M) = =√3 2(BE +EG +F C)≥ ≥√3 2(BE +EG +GC) O ´ultimo passo adv´em da convexidade do quadril´atero, ∠EGC < π ent˜ao ∠EGC+ ∠EGF < 4π 3.∠CGF > 2π 3de tal modo que [FC] ´e o maior lado do triˆangulo [FGC]. (b) Se ∠EGC < 2π 3ent˜ao G´e um ponto interior ao triˆangulo [CFM] (Figura 5.42). Por conseguinte, ∠F GM > ∠FCM =π 3. Logo ∠EGM > 2π 3. Uma vez que ∠BEG > 2π 3ent˜ao, pelo Lema 6, BM ≥√3 2(BE +EG +GM). Falta agora provar que GM ≥GC. Figura 5.42: ´ Arvore Geradora Minimal quando ∠BEG ≤2π 3e∠EGC < 2π 3 Agora EF =GF eCF =FM. Pela constru¸c˜ao da ´ Arvore Geradora Minimal, CE ≤F M, uma vez que os triˆangulos [CEF] e [MGF] s˜ao congruentes e ∠MGF ≥∠GFM. Para al´em 98 disso, ∠EFM =π 3+∠CFE e∠EFM =π 3+∠GFM, ou seja, ∠CFE =∠GFM. ∠CFE +∠GFM −2π 3=∠CFG. Como ∠CFE =∠GFM ent˜ao ∠EFC =1 2∠CFG+π 3, ou seja, ∠CFE ≥∠CFG. Mas ∠EFG =π 3, logo ∠CFG ≤π 6, o que implica que ∠GFM =π 3−∠CFG > π 6>∠CFG. Mas tamb´em GF =EF eCF =FM. Desde que ∠GFM ≥∠CFG,GM ≥CG. O que completa a prova para este caso. Caso 5 A´ Arvore Geradora Minimal ´e a da Figura 5.43. Figura 5.43: ´ Arvore Geradora Minimal (Caso 5) Nestas circunstˆancias podemos ter trˆes situa¸c˜oes distintas: quando ∠CBE ≥2π 3, quando ∠EGC ≥2π 3e quando ∠CBE < 2π 3∧∠EGC < 2π 3. Analisemos cada uma delas em separado. 1. Suponhamos que ∠CBE ≥2π 3. Comecemos por construir os triˆangulos equil´ateros [EGF]e[BF L]. Esta prova ´e idˆentica `a prova do Caso 3. Desde que [EG] seja o maior lado do triˆangulo [BEG] ent˜ao ∠EBG ≥π 3. Por isso, Figura 5.44: ´ Arvore Geradora Minimal quando ∠CBE ≥2π 3 99 ω(AMS) = CL ≥ ≥√3 2(CB +BE +EL) = =√3 2(CB +BE +BG)≥ ≥√3 2(CG +BG +BE) = =√3 2ω(AGM). 2. Se ∠EGC ≥2π 3devemos construir o triˆangulo equil´atero [ABC] seguido do triˆangulo equil´atero [AGL]. Desde que [BC] seja o maior lado do triˆangulo [BCG] ent˜ao ∠BGC ≥ π 3. Figura 5.45: ´ Arvore Geradora Minimal quando ∠EGC ≥2π 3 Por isso, ω(AMS) = EL ≥ ≥√3 2(EG +GC +CL) = =√3 2(EG +GC +BG)≥ ≥√3 2(BE +GC +BG) = =√3 2ω(AGM). 3. Quando na ´ Arvore Geradora Minimal considerada no Caso 5 ∠CBE < 2π 3e∠CGE < 2π 3, Pollak inicia a prova mostrando que existe a outra topologia completa que n˜ao a considerada inicialmente ((BE)−P−Q−(CG)). Comecemos por tra¸car o segmento [XY ] que tem o comprimento da ´ Arvore de Steiner. J´a vimos anteriormente que a interse¸c˜ao das circunferˆencias que circunscrevem os 100 Figura 5.46: ´ Arvore Geradora Minimal quando ∠CBE < 2π 3e∠CGE < 2π 3 triˆangulos equil´ateros com o segmento de reta definido pelos pontos equil´ateros cujo comprimento ´e igual ao da ´ Arvore de Steiner d´a a posi¸c˜ao dos pontos de Steiner. Ent˜ao, se [XY ] intersetar os segmentos de reta [BE]e[CG] e, se as circunferˆencias que circunscrevem os triˆangulos [BEX] e [CGY ] n˜ao se intersetarem, [XY ] tamb´em interseta os arcos BE eCG, e por conseguinte, d´a-nos a posi¸c˜ao dos pontos de Steiner P eQ, de modo que P´e adjacente a Be a E, e Q´e adjacente a Ce a G, ou seja, a topologia (BE)−P−Q−(CG) existe (Figura 5.46). Por um lado, ∠Y GE =∠Y GC+∠CGE < π e∠CBX =∠CBE +∠EBX < π. Por outro lado, [BC] ´e o maior lado do triˆangulo [BCG], ent˜ao ∠BCG < π 2e, por isso, ∠BCY < 5π 6. De modo an´alogo, ∠GEX < 5π 6. Ent˜ao XeYest˜ao no mesmo semiplano determinado por BC, tal como EeG, e no mesmo semiplano determinado por EG, tal como BeC. Logo [XY ] interseta [BE] e [CG]. Marquemos ent˜ao um novo ponto S, no lado oposto ao de Xrelativamente a BE, de tal modo que ∠EBS =π 3, e um outro ponto T, no lado oposto ao de Yrelativamente aCG, de tal modo que ∠CGT =π 3. A circunferˆencia que circunscreve o triˆangulo [BEX] pertence a um dos semiplanos determinados por BS, exatamente aquele a que tamb´em pertencem XeE, e a circunferˆencia que circunscreve o triˆangulo [CGY ] pertence ao semiplano determinado por GT a que tamb´em pertencem CeY. Desde que ∠EBG > π 3e∠BGC > π 3, por constru¸c˜ao da ´ Arvore Geradora Minimal, os arcos BE eGC pertencem a semiplanos diferentes determinados por BG e, por conseguinte, n˜ao se intersetam. Ent˜ao a topologia de Steiner completa (BE)−P−Q−(CG) tamb´em existe. Desde que π 3<∠EBG < 2π 3eπ 3<∠BGC < 2π 3ent˜ao |cot∠EBG| ≤ √3 3e|cot∠BGC| ≤ √3 3. Por isso, |cot∠EBG ·cot∠BGC| ≤ 1 3. Por outro lado, cot∠CBG > √3 3e cot∠EGB > √3 3, ent˜ao cot∠EBG ·cot∠BGC < cot∠CBG ·cot∠EGB. Pelo Lema 8 e pelo Teorema 7, (BE)−P−Q−(CG) ´e a ´ Arvore m´ınima de Steiner e n˜ao (BC)−P−Q−(EG). Estamos portanto no Caso 2, que j´a foi devidamente provado. 101 Figura 5.47: A topologia de Steiner completa (BE)−P−Q−(CG) tamb´em existe 5.2 Alguns casos particulares da Raz˜ao de Steiner Como j´a foi referido no in´ıcio deste cap´ıtulo, sempre que o problema dado tem mais de vinte pontos iniciais ´e impratic´avel determinar a ´ Arvore M´ınima de Steiner, e por conseguinte, a Raz˜ao de Steiner ´ Otima. Assim, ´e pr´atica comum recorrer a heur´ısticas que nos fornecem aproxima¸c˜oes da ´ Arvore M´ınima de Steiner e determinar a Raz˜ao de Steiner efetuando o quociente entre o comprimento dessa ´ Arvore M´ınima de Steiner obtida por m´etodos heur´ısticos e o comprimento da ´ Arvore Geradora Minimal. O valor desta raz˜ao permite averiguar se uma determinada heur´ıstica fornece uma boa ou m´a aproxima¸c˜ao, sendo uma solu¸c˜ao considerada de boa qualidade sempre que a raz˜ao de Steiner ´e menor ou igual a um. Por outro lado, esta raz˜ao permite-nos estabelecer compara¸c˜oes entre as v´arias heur´ısticas. A tabela seguinte apresenta alguns valores para a Raz˜ao de Steiner obtidos a partir de aproxima¸c˜oes de ´ Arvores M´ınimas de Steiner obtidas atrav´es de processos heur´ısticos [56]. Como pudemos constatar para R2, o estudo da Raz˜ao de Steiner em Rntem-se mostrado muito complexo e muitas quest˜oes continuam em aberto [22, 29, 35]. Para ´arvores de Steiner em espa¸cos euclideanos de dimens˜ao superior a dois ainda n˜ao ´e conhecido o ´ınfimo, mas existem algumas conjeturas nesse sentido [69]. Ding-Zhu Du em [73] apresenta uma prova que ρ > 0,615 para Rn. No entanto, Smith e MacGregor Smith apresentaram em [66] uma conjetura para a Raz˜ao de Steiner em R3:ρ= 0,78419. Estes dois autores afirmam que esta raz˜ao ´e alcan¸cada atrav´es de uma estrutura que designaram por sausage. Defini¸c˜ao 14. Uma n-sausage ´e um conjunto infinito numer´avel de pontos em Rnformado pelos centros das esferas de diˆametro unit´ario que se obtˆem da seguinte forma: 102 Ano Autores Raz˜ao de Steiner 1981 Kou, Markowsky e Berman ρ=1 2 1993 Zelikovsky ρ=6 11 ∼ =0,54 1994 Berman e Ramaiyer ρ=9 16 ∼ =0,56 e ρ∼ =0,57 1995 Zelikovsky ρ= 11 + ln2∼ =0,59 1995 Karpinski e Zelikovsky ρ∼ =0,61 1997 Pr¨omel ρ∼ =0,6 1999 Hougardy e Pr¨omel ρ∼ =0,63 2000 Robbins e Zelikovsky ρ=1 1+ln3 2∼ =0,65 Tabela 5.2: Valores da Raz˜ao de Steiner at´e 2000 Comecemos com uma esfera de diˆametro unit´ario no espa¸co Rn. Adicionamos de forma sucessiva esferas de diˆametro unit´ario de tal modo que a k-´esima esfera adicionada seja tangente `as ´ultimas `esferas adicionadas, onde `= min{n, k −1}. Notemos que, fixado n, h´a apenas uma n-sausage a menos de isometria. Um conjunto de dpontos consecutivos de uma n-sausage ´e designado por uma n-sausage de dpontos. Nas Figuras 5.48 e 5.49 podemos observar imagens de uma sausage em R2e de uma sausage em R3. Du e Smith [22] mostraram que `a medida que o n´umero de pontos iniciais aumenta a Raz˜ao de Steiner da estrutura sausage para dimens˜oes superiores a dois diminui, tendendo para um determinado valor. A t´ıtulo de exemplo, em R4, `a medida que se aumenta o n´umero de pontos iniciais, a Raz˜ao de Steiner da sausage tende para 0,74398. Para al´em disso, conjeturaram que, para dimens˜oes relativamente pequenas, esses limites para os quais tende a Raz˜ao de Steiner correspondem ao ´ınfimo para a dimens˜ao considerada. 103 Figura 5.48: Sausage de 11 pontos em R2em [66] Figura 5.49: Sausage de 11 pontos em R3em [66] 104 Cap´ıtulo 6 Aplica¸c˜oes do problema As aplica¸c˜oes do Problema de Steiner s˜ao imensas e diversificadas. Ao longo deste cap´ıtulo pretendemos dar uma ideia dessa diversidade e facultar um leque abrangente de referˆencias bibliogr´aficas. No livro “Shortest Connectivity: An Introduction with Applications in Phylogeny” [12], Cieslik descreve o que poder´a ter sido uma das primeiras aplica¸c˜oes do Problema de Steiner. Numa carta escrita a Schuhmacher em 1836, Gauss colocou o seguinte problema: “Como construir uma rede ferrovi´aria de comprimento m´ınimo que ligue quatro cidades alem˜as: Bremen, Harburg, Hannover e Braunschweig?” Figura 6.1: Problema proposto por Gauss a Schuhmacher Gauss colocou este problema a Schuhmacher em resposta a uma carta onde este ´ultimo expressava um paradoxo no Problema de Fermat: para quatro pontos v1,v2,v3ev4, no plano euclideano, que formam um quadril´atero convexo, a solu¸c˜ao do Problema de Fermat ´e o ponto de interse¸c˜ao das duas diagonais. Se movermos dois dos quatro v´ertices do quadril´atero de modo a que fiquem coincidentes conforme ilustrado na Figura 6.2, o ponto de interse¸c˜ao das duas diagonais vai coincidir com os dois v´ertices referidos. No entanto, a solu¸c˜ao do Problema de Fermat para os trˆes pontos que se obtiveram a partir dos quatro pontos considerados continua a passar pelo ponto de Torricelli T. 105 Cap´ıtulo 7 Conclus˜ao Neste trabalho foram apresentados diversos t´opicos que permitem uma boa apreens˜ao do Problema de Steiner. O estudo incidiu essencialmente no Problema de Steiner Euclideano, mas foram feitas algumas referˆencias sobre o estudo deste problema para outras vers˜oes, nomeadamente, Problema de Steiner Ret´ılineo e Problema de Steiner em Grafos. Apesar da grande satisfa¸c˜ao sentida ao longo da elabora¸c˜ao da presente disserta¸c˜ao, muitas foram as alturas em que a dificuldade teimava em se impor. Os diversos t´opicos diretamente relacionados com a ´ Arvore de Steiner, at´e mesmo a defini¸c˜ao, foram dos mais complicados deste trabalho, visto haver a preocupa¸c˜ao em apresentar um conceito acess´ıvel, mas bastante completo e abrangente. As aplica¸c˜oes do Problema de Steiner foram uma outra ´area dif´ıcil, uma vez que os artigos sobre esta tem´atica s˜ao muito espec´ıficos e exigem um vasto dom´ınio de ´areas como a f´ısica, a biologia, a inform´atica, entre outras. ` A medida que avan¸cava na disserta¸c˜ao as dificuldades foram diminuindo e dando lugar a uma maior confian¸ca ao realizar as tarefas. As barreiras do idioma dos artigos cient´ıficos e da linguagem LATex foram ultrapassadas. Na realidade agora ´e que me sinto apta a escrever uma disserta¸c˜ao. A falta de tempo n˜ao permitiu que o cap´ıtulo das aplica¸c˜oes do Problema de Steiner fosse mais explorado. Nele ´e apenas apresentada uma revis˜ao bibliogr´afica de algumas das aplica¸c˜oes, permitindo o acesso a um leque diversificado de artigos sobre esta tem´atica, que passei a conhecer. Do mesmo modo, muito h´a ainda a dizer, por exemplo, sobre o Problema de Steiner em Grafos e o Problema de Steiner Ret´ılineo, apenas referido no in´ıcio do documento. Tamb´em, as heur´ısticas existentes para o Problema de Steiner s˜ao imensas e em constante atualiza¸c˜ao. No entanto, a resolu¸c˜ao te´orica do problema parece-me que tem andado muito a par das necessidades nas aplica¸c˜oes. Ao efetuar a revis˜ao bibliogr´afica para este trabalho constatei que pouco ou nada existe sobre o tema em portuguˆes. Encontrei alguns artigos em l´ıngua portuguesa, de autores brasileiros, na ´area das heur´ısticas e das aplica¸c˜oes. Embora estes fatores tenham sido um constrangimento na elabora¸c˜ao deste trabalho, contribu´ıram, de certa forma, para o enfatizar. 112 Bibliografia [1] M. Aigner e G. Ziegler, Proofs from The Book, Springer Heidelberg, 2003. [2] C. Alford, M. Brazil e D. H. Lee, Hanbook of Operations Research in Natural Resources, (2006), 561-578. [3] Bell, Witten e Fellows, Ice roads - Steiner trees, Computer Science unplugged, (1998), 151-162. [4] M. W. Bern e R. L. Graham, The shortest-network problem, Scientific American, 1 (1989), 84-89. [5] S. Bhaskaran e F. J. salzborn, Otimal design of Gas pipeline Networks, The Journal of the Operational Research Society, 30 (1979), 1047-1060. [6] B. Bollob´as, D. Gamarnik, O. Riordan e B. Sudakov, On the value of a random minimum weight Steiner tree, Combinatorica, 24 (2004), 187-207. [7] M. Brazil, D. Lee, J. H. Rubinstein, D. a. Thomas, J. F. Weng e N. C. Wormald, Optimisation in the design of underground mine access. [8] D. Cardoso, J. Szymanski e M. Rostami, Matem´atica Discreta, Escolar Editora, 2009. [9] P. Carmi e L. Chaitman-Yerushalmi, Unexplored Steiner Ratio in Geometric Networks, Department of Computer Science, Ben-Gurion university of the Negev, Israel. [10] D. Cieslik, The Steiner Ratio - A Report, University of Greifswald. [11] D. Cieslik, The Steiner Ratio of Metric Spaces - A Report. [12] D. Cieslik, Shortest Connectivity: An Introduction with Applications in Phylogeny, University of Greifswald. [13] D. Chen, D. Du, X. Hu, G. Lin, L. Wang e G. Xue, Approximations for the Steiner Trees with Minimal Number of Steiner Points, Journal of Global Optimization, 18 (2000), 17-33. [14] X. Cheng, Y. Ding-Zhu Du e H. Ngo, Steiner Trees in Industry, Handbook of Combinatorial Optimization, 5(2004), 193-216. [15] M. Chlebik e J. Chleb´ıkov´a , The Steiner tree problema on graphs: Inapproximability results, Theretical Computer Science, 406 (2008), 207-214. 113 [16] E. Cockayne, On the Steiner Problem, Thesis, McGill University, (1963). [17] T. Cormen, C. Leiserson e R. Rivest, Introduction to Algorithms, MIT Press, 1990. [18] R. Courant e H. Robbins, What is Mathematics, Oxford University Press, 1996. [19] H. Coxeter, Introduction to Geometry, John Wiley and Sons, Incorporated, 1963. [20] D. Du, On Steiner Ratio Conjecture, Annals of Operations Research, 33 (1991), 437449. [21] D. Du e F. Hwang, A proof of the Gilbert-Pollak Conjecture on the steiner ratio, Algorithmica, 7(1992), 121-135. [22] D. Du e W. Smith, Disproofs of Generalized Gilbert-Pollak Conjecture on the Steiner Ratio in Three or More Dimensions, Journal of Combinatorial Theory, 74 (1996), 115130. [23] D. Z. Du, J.M. Smith e J.H. Rubinstein, Advances in Steiner Trees, Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 2000. [24] S. Even, Graph Algorithms, Computer Science Press, 1979. [25] V. Forte, N. Maculan, J. Brito, F. Montenegro e M. Rocha, Uma busca local iterativa aplicada ao Problema de Steiner Euclidiano em Rn, Simp´osio de pesquisa operacional e log´ıstica da Marinha Brasileira, 64 (2009). [26] M. Gander, K. Santugini e A. Steiner, Shortest Road Network Connecting Cities, (2008), 1-14. [27] M. Garey, R. Graham e D. Johnson, The complexity of computing Steiner minimal trees, SIAM Journal on Applied Mathematics, 32 (1977), 835-859. [28] M. Garey e D. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32 (1977), 826-834. [29] E. N. Gilbert e H. O. Pollak, Steiner minimal trees, SIAM Journal and Applied Mathematics, 16 (1968), 1-29. [30] M. Goodrich e R. Tamassia, Projeto de Algoritmos - Fundamentos, An´alise e Exemplos da Internet, Editora Bookman, 2004. [31] R. L. Graham e P. Hell, On the history of the minimum spanning tree problem, Annals of the History of Computing, 7(1985), no. 1, 43-57. [32] R. Graham e F. Hwang, A remark on steiner minimal trees, Bulletin of the Institute of Mathematics Academia Sinica, 4(1976), 177-182. [33] M. Hanan, On Steiner’s Problem with Rectilinear Distance, SIAM Journal on Applied Mathematics, 14 (1966), 255-265. [34] M. Herring, The Euclidean Steiner Minimal Problem, Denison University, (2004). [35] F. Hwang, D. Richards e P. Winter, The Steiner Tree Problem, Annals of Discrete Mathematics 53, Elsevier Science Publishers, 1992. 114 [36] K. Jain, M. Mahdian e M. Salavatipour , Packing Steiner Trees. [37] N. Kapov e M. Kos , The Applications of Steiner Trees to Delay Constrained Multicast Routing: a Tabu Search Approach, University of Zagreb, ConTEL 2003, 2(2003), 443448. [38] A. Kapsalis, V. J. Rayward-Smith e G. D. Smith, Solving the Graphical Steiner Tree Problem Using Genetic Algorithms, The Journal of the Operational Research Society, 44 (1993), 397-406. [39] M. Kaufmann, S. Gao e K. Thulasiraman, On Steiner Minimal Tree in Grid Graphs and its Application to VLSI Routing, Algorithms and Computations, 1994. [40] T. Koch e A. Martin, Solving Steiner Tree Problems in Graphs to Optimality, KonradZuse-Zentrum fur Informationstechnik Berlin, (1997). [41] J. W. Laarhoven, Exact and heuristic algorithms for the Euclidean Steiner tree problem, Tese, University of Iowa, (2010). [42] J. Liang e M. Navara, Implementation of calculating steiner point for 2D objects, CMP laboratory, Czech Technical University. [43] D.T. Lotarev e A.P. Uzdemir, Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph, Automation and Remote Control, 66 (2005), 1603-1613. [44] C. L. Lu, C. Y. Tang e R. C. Lee, The full Steiner Tree problem, Theorical Computer Science, 306 (2003), 55-67. [45] J. Matousek e J. Nesetril, Invitation to Discrete Mathematics, Oxford University Press, 2008. [46] Z. Melzak, On the problem of Steiner, Canad. Math. Bull., 4(1961), 143-148. [47] R. Mondaini, D. Mondaini e N. Maculan, The Study of Steiner Points Associated with the Vertices of Regular Tetrahedra Joined Together at Common Faces, Investigaci´on Operativa, (1998), 103-110. [48] R. P. Mondaini e P. M. Pardalos, Mathematical Modelling of Biosystems, Applied Optimization, 102 (2008), 199-219. [49] F. Montenegro, Heur´ısticas para o Problema de Steiner Euclidiano em Rn, Tese, UFRJ, (2001). [50] F. Montenegro, J. A. Torre˜ao e N. Maculan, Microcanonical Optimization Algorithm for the Euclidian Steiner Problem in R(n) with application to Phylogenetic Inference, Phusical Review E-Statistical Physics, Plasmas, Fluids and Related Interdisciplinary Topics, 68 (2003). [51] A. Neto, Problema de Steiner Euclidiano aplicado a mol´eculas de interesse biol´ogico, Tese, UFAM, 2007. [52] N. V. Oliveira, O Problema de Steiner e a Estrutura das Biomacromol´eculas, Tese, COPPE-UFRJ, (2005). 115 [53] J. plesnik, A Bound for the Steiner Tree problem in Graphs, Mathematics Slovaca, 31 (1981), 155-163. [54] H. Pollak, Some Remarks on the Steiner Problem, Journal of Combinatorial Theory, 24 (1978), 278-295. [55] J. Presnik, A bound for the Steiner tree problem in graphs, Mathematica Slovaca, 31 (1981), 155-163. [56] H. Pr¨omel, A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3, Journal of Algorithms, 36 (2000), 89-101. [57] J. Riordan, The enumeration of labeled trees by degrees, Bulletin of the American Mathematical Society, 72 (1966), 110-112. [58] M. L. Rocha, Aplica¸c˜ao de Algoritmos Paralelos e H´ıbridos para o Problema de ´ Arvore de Steiner no Rn, Tese, COPPE-UFRJ, (2008). [59] C.C. S´a e J. Rocha, Treze Viagens pelo Mundo da Matem´atica, Universidade do Porto Editorial, 2010. [60] D. Sankoff e P. Rousseau, Locating the vertices of a Steiner tree in a arbitrary metric space, Mathematical Programming, 9(1975), 240-246. [61] L. Simonetti, N.Maculan e A. Lucena, Gera¸c˜ao de colunas para o problema de empacotamento de ´arvores de Steiner, Simp´osio da Sociedade Brasileira de Pesquisa Operacional, XXXV (2003), 1602-1613. [62] T. Simpson, Doctrine and Application of Fluxions, ... ,1776. [63] W. Smith, How To Find Steiner Minimal Trees in Euclidean d-Space, Algorithmica, 7 (1992), 137-177. [64] J. Smith, Steiner Minimal Tree in E3: Theory, Algorithms and Applications, Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 2(1998), 397-470. [65] J. Smith, Y. Jang e M. Kim, Steiner Minimal Trees, Twist Angles, and the Protein Folding Problem, Proteins: Structure, Function and Bioinformatics, 66 (2007), 889902. [66] J. M. Smith e W. D. Smith, On the Steiner Ratio in 3-Space, Journal of Combinatorial Theory, 69 (1995), 301-332. [67] J. Smith e B. Toppur, Euclidean Steiner Minimal Trees, Minimal Energy Configurations, and the Embbedding Problem of Weighted Graphs in E3, Discrete Applied Mathematics, 71 (1996), 187-215. [68] C. Staton e J. Smith, Steiner Trees and 3-D Macromolecular Conformation, Informs Journal on Computing, 16 (2004), 470-485. [69] J. M. Steele, Cost of Sequential Connection for points in space, Operations Research Letters, 8(1989), 137 - 142. 116 [70] E. A. Thompson, The Method of Minimum Evolution, Annals of Human Genetics, 36 (1973), 333-340. [71] D. Trietsch, Augmenting euclidean networks, Discussion Paper No632, J. L. Kellogg Graduate School of Management, Northwestern university, Illinois. [72] K. Vik, P. Halvorsen e C. Griwodz, Evaluating Steiner-tree heuristics and diameter variations for application layer multicast, Computer Networks, 52 (2008), 2872-2893. [73] P. Wan, D. Du e R. Graham , The Steiner ratio for the dual normed plane, Discrete Mathematics, 171 (1997), 261-275. [74] J. Wang, Computing and Combinatorics, 7 th Annual International Conference, COCOON 2001. [75] P. Winter e M. Zachariasen, Large Euclidean Steiner Minimum Trees in an Hour, International Symposium on Mathematical Programming, (1996), 1-28. [76] L. Wu e J. He, Explosion-proof textile with hierarchical Steiner tree structure, Thermal Science, 16 (2012), 343-344. [77] S. Yan e B. Lin, Application - Specific, Network-on-Chip Architecture Synthesis based on Set Partitions and Steiner Trees, Department of ECE, University of California, (2008), 277-282. [78] Z. X. Yang, X. Y. Jia, J. Y. Hao e Y. P. Gao, Geometry - Experiment Algorithm for Steiner Minimal Tree Problem, Journal of Applied Mathematics, 2013 (2013). [79] H. Zhou, Efficient Steiner Tree Construction Based on Spanning Graphs, Electrical and Computer Engineering, Northwestern University. [80] http://www.atractor.pt/mat/fr-in.htm [consultado a 22/11/2012] [81] http://www-history.mcs.st-andrews.ac.uk/Biographies/Steiner.html [consultado a 27/12/2012] [82] ganley.org/steiner [consultado a 07/08/2013] [83] http://mathworld.wolfram.com/SteinerPoints.html [consultado a 22/11/2012] [84] http://en.wikipedia.org/wiki/very-large-scale_integration [consultado a 07/08/2013] 117 ´ Indice δ-divis˜ao, 53 ´ Arvore M´ınima de Steiner, 57 ´ Arvore de Steiner, 54 ´arvore, 38 ´arvore de Steiner Completa, 61 ´arvore geradora, 40 ´arvore geradora minimal, 40 ´arvore relativamente m´ınima, 57 algoritmo, 49 Algoritmo de Bor¨uvka, 44 Algoritmo de Kruskal, 45 Algoritmo de Prim, 48 aresta de corte, 37 arestas, 34 atalho, 36 c´odigo de Pr¨ufer, 42 caminho, 36 ciclo, 36 circuito, 36 circuito euleriano, 36 componente conexa, 36 divis˜ao de um v´ertice, 53 extremidades da aresta, 34 grafo, 34 grafo com peso, 38 grafo completo, 35 grafo conexo, 36 grafos euclideanos, 52 grafos isomorfos, 35 grau de um v´ertice, 34 heur´ıstica, 49 matriz de adjacˆencia, 34 passeio, 36 Ponto de Steiner, 53 Ponto de Torricelli, 17 ponto equil´atero, 66 Problema de Steiner em Grafos, 52 Problema de Steiner Euclideano, 52 Problema de Steiner Retil´ıneo, 52 problemas computacionais, 49 raz˜ao de Steiner, 73 raz˜ao de steiner ´otima, 74 Sausage, 102 Segmentos de Simpson, 23 sequˆencia de Pr¨ufer, 42 sequˆencia de graus, 35 subgrafo, 35 subgrafo gerador, 35 subgrafo induzido, 35 Teorema de Cayley, 41 topologia, 55 topologia completa, 60 topologia de Steiner, 55 v´ertice de corte, 37 v´ertices, 34 v´ertices adjacentes, 34 118