Uma caraterização combinatória das árvores filogenéticas

Ana Rita Mendanha Sim˜ ao Uma caraterizac¸ ˜ ao combinat´ oria das ´ arvores filogen´ eticas Departamento de Matem´ atica Faculdade de Ciˆ encias da Universidade do Porto 2014 Ana Rita Mendanha Sim˜ ao Uma caraterizac¸ ˜ ao combinat´ oria das ´ arvores filogen´ eticas Tese submetida ` a Faculdade de Ciˆ encias da Universidade do Porto para obtenc¸ ˜ ao do grau de Mestre em Matem´ atica Orientadores: Prof.aDoutora Maria Leonor Nogueira Coelho Moreira Prof. Doutor Samuel Ant´ onio de Sousa Dias Lopes Departamento de Matem´ atica Faculdade de Ciˆ encias da Universidade do Porto 2014 Agradecimentos Concluindo este meu trabalho, ´ e justo prestar homenagem e os meus sinceros agradecimentos a todos os que pela sua ac¸ ˜ ao, direta ou indiretamente, o tornaram vi´ avel. Em primeiro lugar, aos meus orientadores, Professora Doutora Maria Leonor Moreira e Professor Doutor Samuel Dias Lopes, pelos seus ensinamentos, pela pertinˆ encia nas sugest˜ oes e cr´ ıticas e pela enorme disponibilidade demonstrada. De facto, a sensibilidade evidenciada ao longo deste percurso, n˜ ao s´ o engrandeceu o meu trabalho como me ajudou a percecionar uma vertente humana capaz de me apontar um trilho de crescimento afetivo. Na verdade, da simbiose entre o trabalho propriamente dito e da componente emocional colocada ao dispor desse mesmo trabalho, resulta sempre uma enorme gratificac¸ ˜ ao pessoal e profissional. ` A minha fam´ ılia que sempre me apoiou em todos os meus projetos, proporcionando sempre condic¸ ˜ oes ideais para que os pudesse realizar. Inexced´ ıvel nesse apoio, colocou sempre como prioridade a concretizac¸ ˜ ao deste meu projeto; convicta de que o tempo que lhe dediquei serviria para enfatizar uma componente que me enriqueceria, sensibilizada, pude observar que esse apoio ultrapassou os parˆ ametros da razoabilidade tendo, assim, contribu´ ıdo para um solidificar de lac¸os que, gradativamente, foram estreitados mercˆ e da confianc¸a e do incentivo de que fui alvo. ` As minhas colegas de mestrado, Carla Azevedo e Elisa Silveira, que me apoiaram ao longo destes dois anos e que foram uma preciosa ajuda par a concretizac¸ ˜ ao deste mestrado. De facto, em espirito de colaborac¸ ˜ ao e de ajuda interpessoal, pude enriquecer o meu trabalho colocando a t´ onica na an´ alise cr´ ıtica que, de forma positiva, me ajudou a desbravar caminhos que, eventualmente, pudessem apresentar-se mais obscuros. ` A Vˆ ania Pinheiro pela paciˆ encia com que leu este trabalho e pela disponibilidade sempre demonstrada. Atendendo ao facto de que os seus m´ ultiplos afazeres poderiam coartar esse mesmo apoio, esta minha caminhada veio demonstrar exatamente o contr´ ario. Ao Pedro Eiras, por todo o apoio e carinho demonstrado ao longo deste ´ ultimo ano. Na verdade, excedeu as minhas melhores expetativas no sentido em que me proporcionou um enorme sentimento de autoconfianc¸a e est´ ımulo para a execuc¸ ˜ ao do trabalho. E, finalmente, a todos os meus amigos, pelo apoio sempre demonstrado, pela sua preocupac¸ ˜ ao e pela disponibilidade. Grata pela dedicac¸ ˜ ao, companheirismo e amizade, fica a t´ onica na edificac¸ ˜ ao de uma relac¸ ˜ ao interpessoal que jamais esquecerei. Sensibilizada, deixo o meu profundo agradecimento. iii iv Resumo Areconstruc¸ ˜ ao filogen´ etica ´ e uma ´ area de estudo multidisciplinar onde se juntam a matem´ atica, a biologia e as ciˆ encias da computac¸ ˜ ao para permitir construir a ´ arvore evolutiva de um conjunto de objetos biol´ ogicos a partir de relac¸ ˜ oes conhecidas entre eles. Do ponto de vista matem´ atico, a estes objetos biol´ ogicos v˜ ao corresponder os elementos de um conjunto Xque estar˜ ao em correspondˆ encia com os v´ ertices de grau um, ditos folhas, de um certo grafo, dito X-´ arvore filogen´ etica. Nesta dissertac¸ ˜ ao s˜ ao tratados resultados recentes obtidos por Dress, Huber e Steel, publicados em [4] e [5] que permitem lidar com restric¸ ˜ oes impostas pelos dados existentes para fazer a reconstruc¸ ˜ ao filogen´ etica. Definem-se e caraterizam-se certos conjuntos de pares de folhas de uma X-´ arvore filogen´ etica, ditos lassos, que permitem reconstruir a ´ arvore. Associa-se uma estrutura combinat´ oria, um matroide, a uma X-´ arvore. Esse matroide est´ a definido no conjunto de pares de folhas da ´ arvore e mostra-se que as suas bases s˜ ao os lassos minimais que permitem reconstruir a ´ arvore. Palavras-chave: ´ Arvore filogen´ etica, grafo, matroide, lasso, edge-weight lasso, lasso topol´ ogico. v vi Abstract Phylogenetic reconstruction is a multidisciplinary area in which mathematics, biology and computer science come together aiming to construct the evolution tree of a set of biological objects, given certain known relations between them. From a mathematical perspective, these biological objects correspond to elements of a set X, which in turn correspond to the degree one vertices, known as leaves, of a certain graph, called a phylogenetic X-tree. This thesis covers recent results by Dress, Huber, and Steel, published in [4] and [5], which allow for the phylogenetic reconstruction under restrictions imposed by existing data. We determine and characterize certain sets of pairs of leaves of a phylogenetic X-tree, called lassos, which determine aspects of the tree. A combinatorial structure called a matroid is associated to a phylogenetic X-tree. This matroid is defined on the set of all pairs of leaves of the tree and it is shown that its bases are exactly the minimal lassos which allow for the reconstruction of the tree. Keywords: Phylogenetic tree, graph, matroid, lasso, edge-weight lasso, topological lasso. vii viii Conte´udo Resumo v Abstract vii ´ Indice de Figuras xii 1 Introduc¸ ˜ ao 1 2´ Arvores filogen´ eticas 3 2.1 Conceitos e resultados b´ asicos......................... 3 2.1.1 Grafos................................... 4 2.1.2 ´ Arvores .................................. 7 2.1.3 X-´ arvores e ´ Arvores filogen´ eticas ................... 12 2.2 Enlac¸ar uma ´ arvore filogen´ etica......................... 19 3 Matroides 27 3.1 Definic¸ ˜ aoePropriedades ............................ 27 3.2 Circuitos e rank num matroide . . . . . . . . . . . . . . . . . . . . . . . . . 31 4 Matroide associado aos lassos de uma ´ arvore filogen´ etica 35 4.1 Definic¸ ˜ aodomatroide .............................. 35 4.2 ´ Arvoresestrela.................................. 46 4.3 Forma recursiva para a construc¸ ˜ ao das bases do matroide . . . . . . . . . 52 4.4 Caraterizac¸ ˜ ao da X-´ arvore pelo seu matroide . . . . . . . . . . . . . . . . . 60 5 Conclus˜ ao 63 ix permitir a existˆ encia de v´ arias arestas a ligar dois v´ ertices, como em K¨ onigsberg, ou se for introduzida orientac¸ ˜ ao nas arestas como interessar´ a em rede de transportes. A definic¸ ˜ ao que daremos aqui de grafo ´ e de algum modo a mais simples porque tamb´ em ´ e a conveniente para o problema que iremos tratar. 2.1.1 Grafos Definic¸ ˜ ao 1. Dado um conjunto A, definimos o conjunto A 2como o subconjunto das partes de Acom exatamente dois elementos, i.e., o conjunto dos pares de objetos de A. Definic¸ ˜ ao 2. Um grafo G´ e definido pelo par ordenado de conjuntos (V, E), onde V= V(G) = {v1, v2, ..., vn}´ e um conjunto n˜ ao vazio e finito, cujos elementos se designam por v´ ertices eE=E(G) = {e1, ..., em}´ e um conjunto de pares n˜ ao ordenados de v´ ertices, isto ´ e, E⊆V 2, aos quais chamamos arestas. Exemplo 1. O diagrama abaixo representa o grafo Gdefinido por: V(G) = {a, b, c, d, e, f, g, h, i} E(G) = {{a, b},{a, d},{b, c},{b, e},{b, f},{c, d},{c, f},{d, g},{e, h}, {f, g},{f, h},{f, i},{g, i},{h, i}} Figura 2.1: Grafo G= (V, E) Dois v´ ertices uevde um grafo G= (V, E)dizem-se adjacentes se {u, v} ∈ E, ou seja, se {u, v}´ e uma aresta do grafo, vamos denotar por uv essa aresta. Esses v´ ertices dizem-se extremos da aresta uv. A aresta uv, diz-se incidente em ue em ve estes v´ ertices tamb´ em se dizem incidentes na aresta. Definic¸ ˜ ao 3. Ograu de um v´ ertice vem G´ e o n´ umero de arestas e∈E(G)incidentes nele. Vamos denotar o grau do v´ ertive vpor deg(v). Por exemplo, na Figura 2.1,deg(a) = 2edeg(f)=5. Definic¸ ˜ ao 4. Se G= (V, E)´ e um grafo: •qualquer grafo H= (W, F)tal que W⊆VeF⊆Ediz-se um subgrafo do grafo G= (V, E). •um subgrafo H= (W, F)do grafo G= (V, E)diz-se um subgrafo gerador se W= V. 4 •se W⊆V´ e um conjunto de v´ ertices de G, o subgrafo induzido por Wem G´ e o grafo G[W]=(W, EW), onde EW´ e o conjunto de arestas de Gcom ambas as extremidades em W. •se F⊆E´ e um conjunto de arestas de G, o subgrafo induzido por Fem G´ e o grafo G[F] = (VF, F), onde VF´ e o conjunto de v´ ertices de Gincidentes nas arestas de F. Figura 2.2: Grafos: H,G[W]eG[F]. Os trˆ es grafos representados na Figura 2.2 s˜ ao subgrafos de G= (V, E), representado na Figura 2.1. O grafo H= (W, F)´ e um subgrafo de Gcom, W={b, c, d, f, g} ⊆ Vo seu conjunto de v´ ertices e F={bc, cd, bf, fg} ⊆ Eo conjunto de arestas. O grafo G[W]=(W, EW)´ e o subgrafo induzido por Gno mesmo conjunto W= {b, c, d, f, g} ⊆ V;EW´ e o conjunto de artesas de Gcom ambas as extremidades em W, EW={bc, bf, cf, cd, fg, dg}. O grafo G[F]=(VF, F)´ e o subgrafo induzido por Gno conjunto de arestas F= {ab, bc, bf, cd, fg, dg}; o seu conjunto de v´ ertices ´ eVF={a, b, c, d, f, g}´ e o conjunto de v´ ertices de Gincidentes nas arestas do conjunto F. Definic¸ ˜ ao 5. Um caminho de um grafo G´ e uma sequˆ encia de v´ ertices todos distintos, em que dois quaisquer v´ ertices consecutivos s˜ ao adjacentes. Se o v´ ertice inicial do caminho for ueov´ ertice final for vdiz-se que ´ e o caminho de uavou entre uev. Um grafo Pk= (V, E), onde V={v0, v1,· · · , vk}eE={v0v1,· · · , vk−1vk}diz-se um caminho de comprimento k, um caminho em G´ e um subgrafo de G. Na Figura 2.1, abfh,adcfh,adgfh eadgifh s˜ ao caminhos entre aeh. Estes quatro caminhos s˜ ao distintos; adcfh eadgfh tˆ em o mesmo comprimento, ou seja, o mesmo n´ umero de arestas; abfh ´ e um caminho de comprimento m´ ınimo, pois cont´ em o menor n´ umero de arestas necess´ arias para ligar aahem G. Definic¸ ˜ ao 6. Um ciclo de um grafo ´ e uma sequˆ encia de v´ ertices, em que o primeiro e o´ ultimo elemento s˜ ao iguais e todos os outros s˜ ao distintos entre si e distintos deste; al´ em disso, dois quaisquer v´ ertices consecutivos desta sequˆ encia s˜ ao adjacentes e ela tem pelo menos trˆ es v´ ertices distintos. 5 Observe-se que num ciclo, o n´ umero de v´ ertices e o de arestas coincidem, e esse n´ umero diz-se o comprimento do ciclo; al´ em disso, no ciclo, qualquer v´ ertice tem grau dois e o seu comprimento ´ e≥3. Por exemplo, na Figura 2.3 est˜ ao representados a vermelho os ciclos abcda de comprimento quatro e o ciclo figf de comprimento trˆ es. Figura 2.3: Ciclos do grafo da Figura 2.1. Definic¸ ˜ ao 7. Um grafo G= (V, E)diz-se bipartido, se o seu conjunto de v´ ertices pode ser subdividido em dois subconjuntos, V1eV2;V=V1∪V2eV1∩V2=∅, tais que n˜ ao existem arestas entre os elementos do mesmo subconjunto de v´ ertices. Observe-se que decorre da definic¸ ˜ ao que toda a aresta do grafo bipartido Gune um v´ ertice de V1a um v´ ertice de V2. Em particular, um grafo vazio,G= (V, ∅),´ e bipartido. Figura 2.4: Grafos Bipartidos. Teorema 2.1. Um grafo ´ e bipartido se e s´ o se n˜ ao possui ciclos de comprimento ´ ımpar. A prova do Teorema 2.1 pode ser vista na p´ agina 16 de [10]. Observe-se que, em consequˆ encia do Teorema 2.1, os ciclos de comprimento par e os grafos sem ciclos, ditos ac´ ıclicos, s˜ ao grafos bipartidos. Definic¸ ˜ ao 8. Um grafo G= (V, E)diz-se conexo se dados dois quaisquer dos seus v´ ertices existe um caminho entre eles em G. 6 Um grafo G= (V, E)que n˜ ao ´ e conexo diz-se desconexo e pode sempre ser decomposto como uni˜ ao disjunta de subgrafos conexos maximais, ditas as componentes conexas de G. Mais precisamente, G=G[V1]˙ ∪G[V2]˙ ∪ · · · ˙ ∪G[Vk], onde V=V1˙ ∪V2˙ ∪ · · · ˙ ∪Vk,G[Vi] ´ e um grafo conexo maximal, para todo i= 1,2,· · · , k ( i.e., qualquer subgrafo de G contendo estritamente algum destes G[Vi]´ e desconexo). Figura 2.5: Grafo conexo G1; grafo desconexo G2com duas comonentes conexas. 2.1.2 ´ Arvores De entre os grafos conexos, as ´ arvores s˜ ao, de um certo ponto de vista, os mais simples mas s˜ ao tamb´ em aqueles que surgem num grande n´ umero de aplicac¸ ˜ oes em ´ areas muito diversas. Em particular, elas modelam diversos problemas ligados ` a gen´ etica, entre eles os que est˜ ao ligados ao trabalho sobre o qual nos debruc¸amos nesta dissertac¸ ˜ ao. Definic¸ ˜ ao 9. Uma ´ arvore ´ e um grafo conexo que n˜ ao cont´ em ciclos. Observe-se que se um grafo ´ eac´ ıclico todas as suas componentes conexas s˜ ao ´ arvores e utiliza-se a designac¸ ˜ ao de floresta para estes grafos. Figura 2.6: ´ Arvore. Numa ´ arvore, chama-se folha a qualquer v´ ertice de grau um; na ´ arvore da Figura 2.6 o conjunto de folhas ´ e{a, c, d, i}. Os v´ ertices com grau diferente de um s˜ ao designados por v´ ertices interiores; na ´ arvore da Figura 2.6 o conjunto dos v´ ertices interiores ´ e {b, e, h, f, g}. Lema 1. Existe exatamente um caminho entre cada par de v´ ertices de uma ´ arvore T. 7 Demonstrac¸ ˜ ao. Seja Tuma ´ arvore e sejam xeydois v´ ertices de T. Como T´ e conexo, existe em Tum caminho entre xey; seja xx1x2...xkyesse caminho. Resta provar que este caminho ´ e´ unico. Admitamos que existe outro caminho xy1y2...ylye consideremos a justaposic¸ ˜ ao do primeiro com o inverso do segundo, isto ´ e, a sequˆ encia de v´ ertices xx1x2...xkyylyl−1...y1x. ´ E claro que quaisquer dois v´ ertices consecutivos desta nova sequˆ encia s˜ ao adjacentes. Se os v´ ertices diferentes de xdesta sequˆ encia forem todos distintos, ela forma um ciclo do grafo, o que contradiz o facto de Tser uma ´ arvore. Em geral, eles n˜ ao s˜ ao necessariamente todos distintos, mas ´ e f´ acil ver que vai sempre existir uma subsequˆ encia destes que forma um ciclo. Em consequˆ encia do Lema 1, dados dois v´ ertices aebde uma ´ arvore, fica bem definido o caminho entre eles, que ser´ a denotado por Pab; ele ´ e o ´ unico caminho na ´ arvore que liga estes dois v´ ertices. Vamos denotar por Eab o conjunto das arestas de Pab. Por exemplo, na Figura 2.6, Pai =abehi eET(a|i) = {ab, be, eh, hi}. Observac¸ ˜ oes: •Seja G= (V, E)um grafo e euma aresta do grafo G, denota-se por G\{e}o grafo obtido a partir de Gquando se retira a aresta e, i.e., o subgrafo de Gdefinido por V(G\{e}) = V(G)eE(G\{e}) = E(G)\ {e} ⊆ EG. •Quando a uma ´ arvore T, retirarmos uma aresta e∈E(T)obtemos um grafo, T\e, que ´ e na mesma ac´ ıclico, claro, mas desconexo j´ a que ao retirar a aresta e=uv os v´ ertices uevn˜ ao podem permanecer ligados por um caminho em T\eporque esse caminho juntamente com a aresta eformaria um ciclo de T. Al´ em disso, podese provar que T\etem exatamente duas componentes conexas. Cada uma destas componente ´ e, ent˜ ao, um grafo conexo e ac´ ıclico, ou seja , uma ´ arvore. 8 Figura 2.7: ´ Arvores T\{ek}:T\{fh},T\{dg}eT\{eh}. Na Figura 2.7 est˜ ao representadas trˆ es florestas obtidas da ´ arvore da Figura 2.6, quando retirada uma das suas arestas. As duas componentes conexas obtidas em cada um dos casos est˜ ao representadas uma a azul e outra a preto. •Se C´ e um ciclo e e=xy ∈E(C),C\ {e}´ e um caminho entre xeye, portanto, um grafo conexo. Figura 2.8: Ilustrac¸ ˜ ao de dois ciclos quando retirada uma aresta. Teorema 2.2. O n´ umero de arestas de uma ´ arvore T, dito cardinalidade da ´ arvore e notado por |T|, s´ o depende do n´ umero nde v´ ertices de T:|T|=n−1. Demonstrac¸ ˜ ao. Nos casos n= 1 en= 2 o resultado verifica-se. Para provarmos o resultado por induc¸ ˜ ao consideremos Tuma ´ arvore qualquer com nv´ ertices, n≥3, e retiremos-lhe uma aresta. Como observ´ amos acima, se retirarmos uma aresta ea uma ´ arvore T,T\e´ e uma floresta constituida por duas ´ arvores, T0eT00; sejam n0en00, respetivamente, o n´ umero de v´ ertices dessas ´ arvores e seja no n´ umero de v´ ertices de T.´ E claro que n=n0+n00. Por hip´ otese de induc¸ ˜ ao, o n´ umero de arestas de T0´ en0−1e o n´ umero de arestas de T00 ´ en00 −1. Assim o n´ umero de arestas da ´ arvore T´ e: 9 (n00 −1) + (n00 −1) + 1 = n−1 como quer´ ıamos demonstrar. Se ao inv´ es de retirarmos uma aresta ` a´ arvore Tlhe acrescentarmos uma aresta e=xy ligando dois dos seus v´ ertices n˜ ao adjacentes, forma-se um ciclo deste novo grafo, T∪{e}. Esse ciclo ´ e obtido pela adic¸ ˜ ao dessa aresta ao caminho de Tentre xey; e ele ´ e o ´ unico ciclo do grafo , T∪ {e}porque, se n˜ ao fosse ´ unico, como qualquer ciclo teria de conter e, ao retirar a aresta xy existiriam dois caminhos distintos entre xeyem T, o que n˜ ao pode acontecer, pois T´ e uma ´ arvore. Figura 2.9: T∪ {gi}eT∪ {cd}. Na Figura 2.9 est˜ ao representados os dois grafos obtidos da ´ arvore da Figura 2.6, quando adicionada as arestas gi ecd, respetivamente. A aresta adicionada est´ a representada a vermelho. Definic¸ ˜ ao 10. Uma ´ arvore geradora de um grafo G´ e qualquer ´ arvore que ´ e um subgrafo gerador de G. Na Figura 2.10, os subgrafos indicados em linhas vermelhas s˜ ao duas ´ arvores geradoras do grafo Gda Figura 2.1. Figura 2.10: ´ Arvores geradoras do grafo Gda Figura 2.1. Observac¸ ˜ oes: •Decorre do Teorema 2.2 que a cardinalidade de uma ´ arvore geradora de um grafo Gcom nv´ ertices ´ e igual a n−1e, consequentemente, que todas as ´ arvores geradoras do grafo Gtˆ em a mesma cardinalidade. 10 •Qualquer grafo conexo Gtem, no m´ ınimo, uma ´ arvore geradora. Demonstrac¸ ˜ ao. Seja ent˜ ao Gum grafo conexo. Se Gfor um grafo ac´ ıclico ent˜ ao G ´ e uma ´ arvore; neste caso h´ a uma s´ o´ arvore geradora do grafo Gque ´ e o pr´ oprio grafo. Caso contr´ ario, Gtem pelo menos um ciclo: consideremos uma aresta ede Gtal que epertenc¸a a um ciclo do grafo Ge retiremos essa aresta a G. Obtemos assim o grafo G\{e}que ´ e um subgrafo de G, gerador porque tem o mesmo conjunto de v´ ertices e conexo porque a aresta retirada pertencia a um ciclo. Se G\{e}n˜ ao tiver ciclos ´ e uma ´ arvore geradora de G. Caso contr´ ario, retiramos outra aresta que pertenc¸a a um ciclo do grafo G\{e}e assim sucessivamente. Como os subgrafos obtidos a cada passo s˜ ao sempre geradores e conexos e tˆ em cada um deles menos ciclos que o anterior, ao fim de um n´ umero finito de passos o subgrafo obtido ser´ a tamb´ em ac´ ıclico e, portanto, uma ´ arvore geradora do grafo G. Figura 2.11: Ilustrac¸ ˜ ao da prova. Lema 2. Seja G= (V, E)um grafo conexo com nv´ ertices, e F⊆Eum conjunto ac´ ıclico de arestas de G, ie., um conjunto F⊆Etal que o grafo G[F]=(VF, F)induzido por F em G´ e ac´ ıclico. Ent˜ ao, F´ e o conjunto das arestas de uma ´ arvore geradora se e s´ o se F´ e um conjunto maximal para a inclus˜ ao com esta propriedade, i.e., se para todo Xtal que F⊂X⊆E, G[X]n˜ ao ´ e ac´ ıclico. Demonstrac¸ ˜ ao. Se F´ e o conjunto das arestas de uma ´ arvore geradora, T=G[F], ent˜ ao VF=Ve|F|=|V| − 1. 11 Assim, para todo Xtal que F⊂X⊆E, como T´ e subgrafo de G[X],G[X]´ e conexo eVX=Vportanto se G[X]fosse ac´ ıclico seria uma ´ arvore geradora com pelo menos |V|arestas, contradizendo o Teorema 2.2. Reciprocamente, se o conjunto F´ e ac´ ıclico maximal, ent˜ ao o grafo G[F]tem de ser conexo e VF=V, i.e., uma ´ arvore geradora de G; caso contr´ ario, como G´ e conexo, seria poss´ ıvel acrescentar pelo menos uma aresta e∈Eao conjunto Fsem formar ciclos no grafo induzido pelo novo conjunto F∪ {e}. 2.1.3 X-´ arvores e ´ Arvores filogen´ eticas Devido ` a sua estrutura, as ´ arvores s˜ ao uma forma de representar a evoluc¸ ˜ ao das esp´ ecies e a forma como se relacionam entre si. Em particular, as ´ arvores, denominadas por ´ arvores filogen´ eticas, s˜ ao um bom modelo para a representac¸ ˜ ao das relac¸ ˜ oes evolutivas entre v´ arias esp´ ecies ou, por exemplo, entre diferentes indiv´ ıduos da mesma esp´ ecie. Nestas ´ arvores, os v´ ertices de grau 1s˜ ao etiquetados por elementos de um conjunto X, conjunto que ´ e inicialmente fixado e usualmente representa o conjunto das esp´ ecies ou ind´ ıviduos cuja evoluc¸ ˜ ao se pretende modelar. Os v´ ertices que ficam sem etiqueta, v´ ertices “interm´ edios”, ter˜ ao obrigat´ oriamente grau maior do que dois, com excec¸ ˜ ao feita, por vezes, a um v´ ertice destacado, dito a ra´ ız, que geralmente representa um ancestral comum aos elementos de X. Nestes casos, o caminho que liga a ra´ ız a um v´ ertice de etiqueta x0,x0∈X, ordena os antepassados de x0at´ e esse ancestral; o primeiro v´ ertice comum aos caminhos dos v´ ertices de etiquetas x, y ∈Xrepresenta o mais ”recente antepassado comum a ambos. Nesta ´ arvore ´ e tamb´ em usual atribuir um peso ` as arestas que pode, por exemplo, representar o tempo de evoluc¸ ˜ ao entre as esp´ ecies que a aresta liga. Os resultados de que falaremos nesta secc¸ ˜ ao s˜ ao v´ alidos num contexto um pouco mais geral das chamadas X-´ arvores, que definimos abaixo, de acordo com a opc¸ ˜ ao feita no livro [3] onde este tema ´ e tratado com detalhe. No resto do trabalho trataremos um caso particular destas ´ arvores, definidas abaixo como X-´ arvores filogen´ eticas Definic¸ ˜ ao 11. Seja Xum conjunto; uma X-´ arvore ´ e um par ordenado Γ = (T, φ), em que T= (V, E)´ e uma ´ arvore e φ:X→V´ e uma func¸ ˜ ao com a propriedade de todos os v´ ertices de Tde grau ≤2pertencerem ` a sua imagem. Definic¸ ˜ ao 12. Uma X-´ arvore filogen´ etica ´ e uma X-´ arvore Γ = (T, φ), em que φ´ e uma bijec¸ ˜ ao de Xno conjunto das folhas de T. Decorre da definic¸ ˜ ao que uma X-´ arvore filogen´ etica n˜ ao pode ter v´ ertices de grau 2. Se al´ em disso, todos os v´ ertices interiores de Ttiverem grau trˆ es, ent˜ ao Γ´ e uma X-´ arvore filogn´ etica bin´ aria. Na Figura 2.12 est˜ ao representadas uma X-´ arvore e uma X´ arvore filogen´ etica com os conjuntos de etiquetas: X={1,2,3,4,5,6,7,8,9,10,11};X={1,2,3,4,5,6,7,8,9}, respectivamente. 12 Figura 2.12: X-´ arvore; X-´ arvore filogen´ etica. No caso das X-´ arvores filogen´ eticas, ´ e usual, e tamb´ em o faremos ao longo deste trabalho , identificar o conjunto Xdas etiquetas com o conjunto das folhas de T. Definic¸ ˜ ao 13. Duas X-´ arvores filogen´ eticas, T1= (V1, E1)eT2= (V2, E2), s˜ ao isomorfas se existe uma func¸ ˜ ao φ:V1−→ V2, tal que: 1. φ´ e bijetiva; 2. φ|X=Id; 3. ab ∈E(T1)⇔φ(a)φ(b)∈E(T2). Se T1´ e isomorfa a T2, ou equivalentemente, se as duas X-´ arvores s˜ ao topologicamente equivalentes, escrevemos T1 X ∼ =T2. Exemplo 2. Na Figura 2.13 est˜ ao representadas trˆ es X-´ arvore filgen´ eticas, T1,T2eT3. AX-´ arvore T1´ e isomorfa ` aX-´ arvore T2,T1 X ∼ =T2, mas n˜ ao ´ e isomorfa ` aX-´ arvore T3, T1 X T3. Figura 2.13: Trˆ es X-´ arvore filogen´ eticas: T1,T2eT3. As duas X-´ arvores, T1eT2, s˜ ao isomorfas pois a func¸ ˜ ao φ:V(T1)−→ V(T2) representada na Figura 2.13 respeita os trˆ es pontos da Definic¸ ˜ ao 13, portanto ´ e um isomorfismo. 13 Figura 2.19: X-´ arvore com pesos. Dw2(b, c) = 100 = Dw3(b, c) Dw2(b, d) = 202 = Dw3(b, d) Dw2(a, f) = 204 = Dw3(a, f) Dw2(a, e) = 200 = Dw3(a, e) logo, (T, w2)L ≡(T, w3), com w26=w3 Exemplo 8. Vamos considedar agora duas X-´ arvores distintas, TeT0representadas na Figura 2.20, que n˜ ao s˜ ao topologicamente equivalentes, e cada uma com a sua func¸ ˜ ao peso associada, wew0, respetivamente. Consideramos tamb´ em o lasso L={ab, cd}. Figura 2.20: Duas X-´ arvores distintas. Como no exemplo anterior, o peso do caminho entre os pares de folhas que pertencem ao lasso Ls˜ ao iguais nas duas ´ arvores: Dw(a, b) = 2 = Dw0(a, b) Dw(c, d) = 6 = Dw0(c, d). logo, (T, w)L ≡(T0, w0). O peso do caminho entre os pares de folhas que n˜ ao pertencem ao lasso Ls˜ ao distintos nas duas ´ arvores e portanto para qualquer conjunto de pares L0que contenha pelo menos um dos pares abaixo as duas ´ arvores n˜ ao ser˜ ao L0-isom´ etricas. 20 Dw(a, c)=86= 4 = Dw0(a, c) Dw(a, d)=86= 4 = Dw0(a, d) Dw(b, c)=86= 4 = Dw0(b, c) Dw(b, d)=86= 4 = Dw0(b, d) Definic¸ ˜ ao 17. Seja Tuma X-´ arvore e Lum lasso associado a essa mesma ´ arvore. Vamos denotar por Γ(L)o grafo que tem como conjunto de v´ ertices os elementos do conjunto X, e arestas os pares de folhas que pertencem ao lasso L. Por exemplo, o grafo Γ(L)associado ao lasso L={ab, bc, bd, af, ae}da Figura 2.19 ´ e: Figura 2.21: Grafo Γ(L)associado a L={ab, bc, bd, af, ae}. Definic¸ ˜ ao 18. Dada uma X-´ arvore Te um subconjunto Lde X 2, definem-se trˆ es tipo de lassos: •L´ eedge-weight lasso de Tse determina o peso de todas as arestas da ´ arvore, isto ´ e, se wew0forem duas func¸ ˜ oes peso em Tque “coincidem em L”. Isto ´ e, tais que (T, w)L ≡(T, w0)ent˜ ao coincidem em todas as arestas de T, ou seja, w=w0. •L´ elasso topol´ ogico de Tse determina a topologia da ´ arvore, isto ´ e, se wew0 forem duas func¸ ˜ oes peso em TeT0, respetivamente, que “coincidem em L”, isto ´ e, tais que (T, w)L ≡(T0, w0), ent˜ ao TeT0s˜ ao topologicamente equivalentes. •Lstrong lasso de Tse ´ e simultaneamente edge-weight e topol´ ogico; este subconjunto, L, permite determinar os pesos de todas as arestas da ´ arvore e a sua topologia. Seja Tuma X-´ arvore com conjunto de folhas X={a, b, c, d, e, f}, e seja L= {ab, ac, bc, de, df, ef}um lasso associado a esta X-´ arvore. ´ E f´ acil verificar que Ln˜ ao ´ e um edge-weight lasso. Como j´ a foi visto na Definic¸ ˜ ao 18, L´ e um edge-weight lasso se wew0forem duas func¸ ˜ oes peso em Ttal que (T, w)L ≡(T, w0), ent˜ ao coincidem em todas as arestas de T, ou seja, w=w0. ´ E conhecido o comprimento dos caminhos que ligam quaisquer duas folhas do conjunto: {ab},{ac},{bc},{de},{df},{ef}. No entanto, n˜ ao ´ e poss´ ıvel determinar a distˆ ancia entre uma folha do conjunto {abc}e do conjunto {def}. Consideremos ekuma aresta do caminho que ligue duas folhas dos conjuntos {abc}e{def}e que n˜ ao pertenc¸a aos caminhos que ligam os pares de folhas do conjunto L. Essa aresta pode tomar 21 qualquer valor, o que n˜ ao garante que w=w0, logo L={ab, ac, bc, de, df, ef}n˜ ao ´ e um edge-weight lasso para a X-´ arvore T. Por fim, vamos considerar a X-´ arvore representada na Figura 2.22 com conjunto de folhas X={a, b, c, d, e, f}, e seja L={ab, ac, bc, de, df, ef, ae, bd, cf}um lasso associado aT. 22 Figura 2.22: X-´ arvore T. Vamos verificar que L´ e um edge-weight lasso para a X-´ arvore T, uma vez que ´ e poss´ ıvel determinar, para qualquer func¸ ˜ ao peso wde T, os valores D(x, y) := Dw(x, y), para todas as cordas xy ∈X 2. As distˆ ancias entre quaisquer xy ∈Ls˜ ao conhecidas. Vamos verificar se, para todas as cordas que n˜ ao pertenc¸am ao lasso L,´ e poss´ ıvel determinar o valor de D(x, y). Por exemplo: D(a, d) = D(a, c) + D(b, d)−D(b, c) depois de conhecida a distˆ ancia entre as folhas aed, podemos determinar: D(b, e) = D(a, e) + D(b, d)−D(a, d). Analogamente, determinamos a distˆ ancia entre os pares de folhas restantes: D(c, e) = D(d, e) + D(c, f)−D(d, f) D(a, f) = D(c, f) + D(a, e)−D(c, e) D(b, f) = D(b, e) + D(a, f)−D(a, e) D(c, d) = D(c, e) + D(a, d)−D(a, e). Para uma certa func¸ ˜ ao peso w,´ e poss´ ıvel determinar a distˆ ancia entre todos os pares de folhas, ent˜ ao L={ab, ac, bc, de, df, ef, ae, bd, cf}´ e um edge-weight lasso. No entanto, Ln˜ ao ´ e um lasso topol´ ogico, pois existem, pelo menos, duas X-´ arvores que n˜ ao s˜ ao topologicamente equivalentes com o mesmo peso entre todos os pares de folhas da X-´ arvore T. Na Figura 2.23 est˜ ao representadas duas X-´ arvores, T1eT2, com a mesma distˆ ancia entre todos os pares de folhas de L, mas n˜ ao s˜ ao topologicamente equivalentes. 23 Figura 2.23: Duas ´ arvores que n˜ ao s˜ ao topologicamente equivalentes: T1eT2. Admitamos que existe uma func¸ ˜ ao φ:V(T1)−→ V(T2), que ´ e um isomorfismo nas duas X-´ arvoes. Para as duas X-´ arvores, T1eT2, considere-se: •xeydois v´ ertices interiores de T1, •ax a aresta com extremidades aex;cy a aresta com extremidade cey, •φ(x)eφ(y)as imagens de xeyem T2, respetivamente, representado na Figura 2.24. Assim sendo, a aresta ax tem que ter por imagem uma aresta que tem extremidade em a, e outra extremidade em φ(x)(imagem de xem T2). Do mesmo modo, a aresta cy tem que ter por imagem uma aresta que tem extremidade em c, e outra extremidade em φ(y)(imagem de yem T2). Com esta construc¸ ˜ ao, na X-´ arvore T2, temos que φ(x) = φ(y), o que contradiz o item 1da Definic¸ ˜ ao 13, logo T1 X T2. Figura 2.24: T1eT2. Teorema 2.4. Se n≥4eL´ e lasso topol´ ogico de T, ent˜ ao Γ(L)deve ser conexo. Demonstrac¸ ˜ ao. Suponha que existe uma bipartic¸ ˜ ao de Xem dois subconjuntos disjuntos n˜ ao vazios, AeB, tal que Ln˜ ao cont´ em nenhuma corda formada por ab onde a∈A eb∈B. Considera-se wqualquer func¸ ˜ ao de peso em T. Consideremos T|AeT|Bas duas ´ arvores obtidas atrav´ es da restric¸ ˜ ao de TaAeB, respetivamente, e consideremos w|Aew|B, as restric¸ ˜ oes de wa estas sub´ arvores, as suas func¸ ˜ oes de peso. 24 Podemos ent˜ ao construir uma X-´ arvore T0com func¸ ˜ ao de peso w0tal que T0n˜ ao ´ e topologicamente equivalente a Tapesar de se verificar T|A∼ =T0|AeT|B∼ =T0|B, bem como wA=w0 AewB=w0 Be , por conseguinte, (T, w)e(T0, w0)serem L-isom´ etricas. Isso pode ser feito pela “fus˜ ao” de T|AeT|Bpor arestas convenientemente escolhidas. A Figura 2.25 representa a X-´ arvore com conjunto X={a, b, c, d, e, f}, conjunto L={ab, bc, ac, de, ef, fd}e o grafo Γ(L). Como o grafo ´ e desconexo, ent˜ ao o lasso L n˜ ao ´ e topol´ ogico. Figura 2.25: X-´ arvore com conjunto X={a, b, c, d, e, f}e o seu grafo Γ(L)assciado ao conjunto L={ab, bc, ac, de, ef, fd}. Teorema 2.5. Se L´ e weigth-lasso de T, ent˜ ao Γ(L)´ e fortemente n˜ ao bipartido, i.e., todas as componentes conexas do grafo Γ(L)s˜ ao n˜ ao bipartidas. Demonstrac¸ ˜ ao. Suponha que Γ(L)cont´ em uma componente conexa que ´ e bipartida: seja Y⊆Xo conjunto de v´ ertices dessa componente e sejam Y+eY−, os dois conjuntos de uma bipartic¸ ˜ ao de Ytais que n˜ ao existem arestas do grafo a ligar v´ ertices Y+entre si, nem de Y−entre si. Dada qualquer func¸ ˜ ao de peso de T, podemos adicionar uma constante suficientemente pequena, τ, aos pesos de todas as arestas que cont´ em uma folha em Y+e subtrair a mesma quantidade a todos os pesos das arestas que cont´ em uma folha em Y−, sem alterar a distˆ ancia entre quaisquer duas folhas x, x0∈Xcom xx0∈L. Sendo assim, o lasso n˜ ao ´ eedge-weigth lasso. Na Figura 2.26 est´ a representada uma X-´ arvore com conjunto X={a, b, c, d, e}. Consideremos L={ab, ac, bc, de}e o seu grafo Γ(L)que como verific´ amos na figura ´ e um grafo desconexo. Figura 2.26: X-´ arvore com conjunto X={a, b, c, d, e}e o grafo Γ(L)associado ao conjunto L={ab, ac, bc, de}. 25 Consideremos a componente conexa bipartida do grafo, {de}. Temos ent˜ ao os conjuntos de bipartic¸ ˜ ao Y+={d}eY−={e}e somamos τa todas as arestas incidentes nas folhas que pertencem ao conjunto Y+e subtraimos τa todas as arestas que incidem nas folhas que pertencem ao conjunto Y−, ilustrado na Figura 2.27. Figura 2.27: X-´ arvore com conjunto X={a, b, c, d, e}com diferentes pesos nas arestas. Como verificamos na Figura 2.27, a distˆ ancia entre todos os pares de folhas que pertencem ao lasso Lmantˆ em-se nas duas ´ arvores, variando o valor τobtemos v´ arias X−´ arvores distintas e a distˆ ancia entre os pares de folhas do lasso Ln˜ ao se altera. Concluimos ent˜ ao que o lasso Ln˜ ao ´ eedge-weigth lasso. Corol´ ario 1. Em particular, Γ(L)´ e conexo e n˜ ao bipartido se L´ estrong-lasso para T. Demonstrac¸ ˜ ao. Pelo Teorema 2.4 sabe-se que se Γ(L)´ e um grafo conexo, ent˜ ao L ´ e um lasso topol´ ogico. Por outro laso, pelo Teorema 2.5 sabe-se que que se Γ(L)´ e fortemente n˜ ao bipartido, ent˜ ao L´ e um edge-weight lasso. Assim, se Γ(L)´ e um grafo conexo e fortemente n˜ ao bipartido, ent˜ ao o lasso L´ e um edge-weight lasso e lasso topol´ ogico, ou seja, um strong lasso. 26 Cap´ıtulo 3 Matroides Neste cap´ ıtulo introduzimos uma estrutura combinat´ oria que ser´ a associada no cap´ ıtulo seguinte ` as X-´ arvores filogen´ eticas, um matroide. O matroide pode ser introduzido de diversas formas que podem estar mais diretamente relacionadas com alguns dos objetos matem´ aticos a que esta estrutura pode ser associada: por exemplo, o conjunto de independentes, o das bases ou o dos circuitos. O conceito de base de um espac¸o vetorial e o de ´ arvore geradora de um grafo, s˜ ao dois dos mais conhecidos exemplos diretamente ligados a esta estrutura combinat´ oria. Ela ´ e definida num conjunto finito e n˜ ao vazio, dito o seu conjunto de suporte, que no caso em estudo no pr´ oximo cap´ ıtulo ser´ aX 2, visto como o conjunto dos pares de folhas de uma X-´ arvore. Neste caso, ser´ a usada uma func¸ ˜ ao, denominada por func¸ ˜ ao rank, para introduzir o matroide associado a uma qualquer X-´ arvore. As provas de alguns dos resultados aqui apresentados bem como outras propriedades e resultados gerais em Teoria de Matroides podem ser consultados, por exemplo, em [1], [2] e [6]. 3.1 Definic¸ ˜ ao e Propriedades Definic¸ ˜ ao 19. Seja Mum conjunto finito e Ium conjunto de partes de M, que satisfazem as seguintes condic¸ ˜ oes: (i) ∅∈I; (ii) Se X∈IeY⊆Xent˜ ao Y∈I; (iii) Se I1eI2∈Ie|I1|<|I2|ent˜ ao existe um elemento b∈I2\I1tal que I1∪ {b} ∈ I. Dizemos ent˜ ao que M= (M, I)´ e um matroide. Se M= (M, I)´ e um matroide, dizemos que M´ e um matroide sobre Mou que M ´ e o conjunto de suporte de M. Os elementos de I, tamb´ em denotado por I(M), dizem-se os independentes de M. Os subconjuntos de Mque n˜ ao est˜ ao em Is˜ ao ditos os dependentes de M. Observe-se o que resulta da Definic¸ ˜ ao 19: 27 •o conjunto de independentes ´ e n˜ ao vazio porque ∅∈I. •Como I6=∅eM´ e finito existe sempre pelo menos um conjunto independente maximal para a inclus˜ ao: Vamos supor x0um elemento do conjunto MeI0um subconjunto independente. Se existir um elemento x1∈M\{I0}tal que I1=I0∪ {x1}´ e um subconjunto independente, isto implica que existe um subconjunto indepentente que cont´ em estritamente o anterior; caso contr´ ario, I0´ e um conjunto independente maximal. Em geral, se Ii−1´ e um conjunto independente, ou podemos acrescentar um elemento xi∈M\Ii−1tal que Ii=Ii−1∪ {xi}´ e um conjunto independente ou Ii=Ii−1∪ {xi} ´ e dependente, para todo xi∈M\Ii−1, e nesse caso Ii−1´ e independente maximal. Como M´ e um conjunto finito e existe pelo menos um I0isto implica que existe um ktal que Ik´ e um subconjunto independente maximal. •Os subconjuntos independentes maximais s˜ ao ditos bases do matroide. Lema 4. Quaisquer dois conjuntos independentes maximais tˆ em o mesmo n´ umero de elementos. Demonstrac¸ ˜ ao. Sejam I1eI2dois conjuntos independentes maximais de um matroide Me admitamos por reduc¸ ˜ ao ao absurdo que |I1| 6=|I2|; sem perda de generalidade podemos admitir que |I1|<|I2|. Pela Definic¸ ˜ ao de matroide, existe um elemento b∈I2\I1 tal que I1∪ {b}´ e independente. Sabemos que I1∪ {b}%I1porque b∈I2\I1, o que contraria o facto de I1ser maximal. Logo, nem |I1|<|I2|nem |I2|<|I1|. Assim sendo |I1|=|I2|. Decorre do lema anterior que, quaisquer duas bases de um matroide M, tˆ em o mesmo n´ umero de elementos. Teorema 3.1. Seja Buma colec¸ ˜ ao de subconjuntos de M. Se B´ e a colec¸ ˜ ao de bases de um matroide em M, ent˜ ao, satisfaz as seguintes condic¸ ˜ oes: (i) B6=∅; (ii) Se AeBs˜ ao membros distintos de Bea∈A\B, ent˜ ao existe um elemento b∈B\Atal que A\ {a}∪{b} ∈ B. Demonstrac¸ ˜ ao. Como j´ a foi visto anteriormente, a colec¸ ˜ ao das bases de um matroide ´ e n˜ ao vazia. Sejam AeB∈Bduas bases quaisquer. As bases de um matroide s˜ ao os subconjuntos independentes maximais, ent˜ ao, pelo Lema 4 sabemos que |A|=|B|. Consideremos x∈A\B. Como A\{x} ⊆ AeA∈I, ent˜ ao pela Definic¸ ˜ ao 19, A\{x} ∈ I. Dado que |A\{x}| =|A| − 1 = |B| − 1<|B|, pela Definic¸ ˜ ao 19 sabemos que existe y∈B\(A\{x})tal que (A\{x})∪ {y} ∈ I. Falta agora provar que este conjunto, al´ em de independente, ´ e maximal. 28 Como |(A\{x})∪ {y}| =|A|=|B|e{x} 6={y}, ent˜ ao (A\{x})∪ {y}´ e maximal, se n˜ ao fosse teriamos independentes maximais com cardinais distintos, o que contraria o Lema 4. O rec´ ıproco do Teorema ´ e verdade, ou seja, se uma colec¸ ˜ ao Bde subconjuntos de um conjunto Msatisfaz as duas propriedades, ent˜ ao o par M= (M, I)´ e um matroide, onde I={I∈P(M) : I⊆Bpara algum B∈B}eP(M)´ e o conjunto das partes de M. A prova do rec´ ıproco do Teorema pode ser vista na p´ agina 8 de [2]. De seguida, s˜ ao apresentados alguns exemplos de matroides. Exemplo 9 (Matroide Livre).Seja Mum conjunto com nelementos tal que M∈I. Neste caso, todos os subconjuntos de Es˜ ao independentes, ou seja, I=P(M). O par M= (M, P(M)) define um matroide dito matroide livre. Exemplo 10. Sejam nekdois inteiros n˜ ao negativos tais que k≤n. Seja Eo conjunto com nelementos e Ba colec¸ ˜ ao de subconjuntos de Mcom kelementos. A fam´ ılia Bverifica os axiomas das bases de um matroide e assim o par M= (M, B) define um matroide chamado matroide uniforme, denotado por Un,k. A qualquer grafo podemos associar um matroide. Definic¸ ˜ ao 20 (Matroide Gr´ afico).Consideremos um grafo conexo Ge seja E(G)o conjunto de arestas de G. A este grafo podemos associar o matroide, MG= (EG,IG), com conjunto de suporte igual ao conjunto das arestas do grafo G,EG, e conjunto de independentes os conjuntos ac´ ıclicos de arestas de G, i.e., os conjuntos de arestas dos seus subgrafos acı’ıclicos, IG={I⊆EG:G[I]´ e ac´ ıclico }. Seja BGo conjunto formado pelos conjuntos de arestas ac´ ıclicos maximais; provamos em [6] que os elementos deste conjunto s˜ ao as ´ arvores geradoras do grafo G. Como referimos anteriormente, as bases dos matroides tem propriedades b´ asicas que podem ser tomadas como axiomas para um matroide. Deste modo, caracterizamos o matroide atrav´ es do seu conjunto de bases. Teorema 3.2. Se G´ e um grafo conexo, ent˜ ao MG= (EG,BG)´ e um matroide. Demonstrac¸ ˜ ao. Consideremos AeBduas ´ arvores geradoras distintas do grafo G,Ae B∈BGe seja a∈A\Beb∈B\A. Queremos provar que A∪ {b}\{a} ∈ BG, ou seja, que ´ e uma ´ arvore geradora de G. Consideremos uma aresta b∈B\A,A∪ {b}cont´ em um ´ unico ciclo, Cb, ver secc¸ ˜ ao 2.1.2. Como B´ e uma ´ arvore, ent˜ ao Cb*B. Sabemos ent˜ ao, que existe uma aresta a∈A\Btal que A∪ {b}\{a}´ e ac´ ıclico, ou seja, uma ´ arvore. Como |A∪{b}\{a}| =|A|=|B|ent˜ ao A∪{b}\{a}´ e uma ´ arvore geradora, pois todas as ´ arvores geradoras tem a mesma cardinalidade. Assim, MG´ e um matroide. 29 onde < λxy :xy ∈L>designa o subespac¸o de c RE(o dual de RE) gerado pelas func¸ ˜ oes λxy, com xy ∈L. Teorema 4.1. Seja X 2o conjunto dos pares de folhas de uma X-´ arvore e fa func¸ ˜ ao definida acima. Esta func¸ ˜ ao verifica as propriedades da func¸ ˜ ao rank de um matroide. A demonstrac¸ ˜ ao deste Teorema decorre da observac¸ ˜ ao, feita no cap´ ıtulo 3, onde demonstr´ amos que a func¸ ˜ ao fverifica as propriedades da func¸ ˜ ao rank. Decorre do Teorema 4.1 que a func¸ ˜ ao fdetermina univocamente um matroide com conjunto de suporte X 2e func¸ ˜ ao rank igual a f. Designaremos esse matroide por M(T). Dado e∈E, seja wea func¸ ˜ ao definida no conjunto das arestas da ´ arvore Tdo seguinte modo: we:E−→ R f7→ δe,f =1se e=f 0se e6=f . Por exemplo, we1´ e uma func¸ ˜ ao que vale 1na aresta e1e0nas restantes; we2´ e uma func¸ ˜ ao que vale 1na aresa e2e0nas restantes; e assim sucessivamente. Observe-se que o conjunto das func¸ ˜ oes {we:e∈E}´ e uma base de RE. Tendo em conta esta base, podemos associar a cada func¸ ˜ ao λxy :RE−→ Rum vetor de R|E|, nomeadamente a matriz de λxy relativamente ` a base {we:e∈E}de REe` a base can´ onica de R: λxy 7→ (λxy(we1)λxy(we2)...λxy(wek)),com k=|E|eE={e1, e2, ..., ek}. Observe-se tamb´ em que este vetor determina λxy. A cada lasso Lpodemos associar a matriz ML, cujas linhas s˜ ao os vetores associados a λxy, para cada xy ∈L. Observe-se que o rank de L´ e igual ` a carater´ ıstica da matriz ML. Na Figura 4.1, est˜ ao representados trˆ es tipos espec´ ıficos de X-´ arvores que ir˜ ao desempenhar um papel importante neste trabalho. Definic¸ ˜ ao 24. (i) As ´ arvores estrela, s˜ ao X-´ arvores que tˆ em apenas um v´ ertice interior e, por conseguinte, s˜ ao equivalentes ` a´ arvore T∗(X) := (V∗(X), E∗(X)), com conjunto de folhas X, v´ ertices V∗(X) := X∪ {∗} e conjunto de arestas E∗(X) := {∗x:x∈X}, onde “∗”denota o ´ unico v´ ertice interior de T∗(X). (ii) As ´ arvores quarteto, s˜ ao X-´ arvores bin´ arias que tˆ em quatro folhas. Tab|cd representa oquarteto com conjunto de folhas {a, b, c, d}, cuja aresta central ´ e denotada por eab|cd, e separa as folhas a, b das folhas c, d. (iii) As ´ arvores lagarta, s˜ ao X-´ arvores bin´ arias que contˆ em um caminho e todas as suas folhas est˜ ao ` a mesma distˆ ancia desse caminho. 36 Figura 4.1: X-´ arvore estrela. Apresentamos de seguida, alguns exemplos que ilustram a determinac¸ ˜ ao do rank de um lasso L, associado a uma X-´ arvore. Exemplo 16. Consideremos a X-´ arvore representada na Figura 4.2. Figura 4.2: X-´ arvore estrela. Seja Lum lasso associado a esta X-´ arvore. Queremos determinar rank(L) = dim(<L>) = dim(< λxy :xy ∈L>). Neste caso, |E|= 4 e vamos considerar L={ab, cd, cb, ad}. Para determinar o rank de L, vamos considerar a matriz ML. Por exemplo, a λab est´ a associado um vetor de R4, em que cada entrada desse vetor corresponde ` a distˆ ancia da folha a` a folha brelativamente a cada uma das func¸ ˜ oes wei. As quatro func¸ ˜ oes, λxy com xy ∈L, correspondem aos seguintes vetores de R4: λab 7→ (λab(we1)λab(we2)λab(we3)λab(we4)) = (1 1 0 0) λcd 7→ (λcd(we1)λcd(we2)λcd(we3)λcd(we4))=(0011) λcb 7→ (λcb(we1)λcb(we2)λcb(we3)λcb(we4)) = (0 1 1 0) λad 7→ (λad(we1)λad(we2)λad(we3)λad(we4)) = (1 0 0 1) Assim, a matriz ´ e: 37 ML=    λab λcd λcb λad    =    1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1     Como o determinante da matriz ML´ e zero ent˜ ao as quatro func¸ ˜ oes s˜ ao linearmente dependentes, o que quer dizer que dim(<L>)≤3. Como det  0 0 1 0 1 1 1 0 0 =−16= 0, ent˜ ao a carater´ ıstica da matriz ML´ e igual a trˆ es, o que quer dizer que trˆ es linhas da matriz MLs˜ ao linearmente independentes, ou seja, trˆ es dos quatro vetores s˜ ao linearmente independentes, ent˜ ao a dimens˜ ao do espac¸o vetorial gerado por estas func¸ ˜ oes ´ e igual a trˆ es. rank(L) = dim(<L>) = 3 Consideremos agora: L={ab, bd, cb, ac}. λab 7→ (λab(we1)λab(we2)λab(we3)λab(we4)) = (1 1 0 0) λbd 7→ (λbd(we1)λbd(we2)λab(we3)λbd(we4)) = (0 1 0 1) λcb 7→ (λdc(we1)λdc(we2)λab(we3)λdc(we4)) = (0 1 1 0) λac 7→ (λab(we1)λac(we2)λac(we3)λac(we4)) = (1 0 1 0) e a seguinte matriz: ML=    λab λbd λcb λac    =    1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0     Como det(ML)=26= 0, ent˜ ao as quatro func¸ ˜ oes s˜ ao linearmente independentes, o que quer dizer que a dimens˜ ao do espac¸o gerado por elas ´ e igual a 4. rank(L) = dim(<L>) = 4 Assim sendo, L´ e um lasso com rank(L)=4e|L|=4=|E|= dim c RE. Portanto, L´ e uma base do matroide M(T). Observe-se que Ltamb´ em ´ e um edge-weight lasso. Dada uma func¸ ˜ ao peso w∈RE, que atribui um valor w(ei)∈Ra cada aresta ei∈E, seja Dw(x, y)a distˆ ancia entre o v´ ertice xeyrelativamente a w. Supondo que as distˆ ancias (relativamente a w) entre os pares de folhas em Ls˜ ao conhecidas, temos        Dw(a, b) = x0 Dw(b, d) = x1 Dw(c, b) = x2 Dw(a, c) = x3 , x0, x1, x2, x3∈R⇔       w(e1) + w(e2) = x0 w(e2) + w(e4) = x1 w(e2) + w(e3) = x2 w(e1) + w(e3) = x3 . 38 Observe-se que a matriz formada pelos coeficientes do sistema ´ e igual a ML. O determinante da matriz ´ e diferente de zero, ent˜ ao o sistema ´ e poss´ ıvel e determinado, logo L´ e um edge-weight lasso, j´ a que determina w. Na Figura 4.3 est´ a representado o grafo Γ(L)associado ao lasso L. Figura 4.3: Grafo Γ(L)associado ao lasso L={ab, bd, cb, ac}. 39 Exemplo 17. Consideremos a X-´ arvore representada na Figura 4.4. Nos mesmos padr˜ oes que o exemplo anterior, queremos determinar, para um certo lasso L, o seu rank. Figura 4.4: X-´ arvore quarteto. Nesta ´ arvore |E|= 5. Seja L={ab, cd}um lasso associado a esta X-´ arvore. Como λab eλcd s˜ ao duas func¸ ˜ oes que n˜ ao se podem escrever ` a custa uma da outra, ent˜ ao s˜ ao linearmente independentes, logo rank(L) = dim(<L>)=2. Consideremos agora L={ab, cd, ad, bc}. λab 7→ (λab(we1)λab(we2)λab(we3)λab(we4)λab(we5)) = (1 1 0 0 0) λcd 7→ (λcd(we1)λcd(we2)λcd(we3)λcd(we4)λcd(we5)) = (0 0 0 1 1) λad 7→ (λad(we1)λad(we2)λad(we3)λad(we4)λad(we5))=(10101) λbc 7→ (λbc(we1)λbc(we2)λbc(we3)λbc(we4)λbc(we5)) = (0 1 1 1 0) Uma forma de calcular a dimens˜ ao do subespac¸o gerado pelas quatro func¸ ˜ oes ´ e verificar se existem x, y, z ew∈Rtal que: xλab +yλcd +zλad +wλbc = 0. A soluc¸ ˜ ao x=y=z=w= 0 ´ e chamada a soluc¸ ˜ ao trivial da equac¸ ˜ ao. Se essa soluc¸ ˜ ao for ´ unica, ent˜ ao as func¸ ˜ oes s˜ ao linearmente independentes. Caso a soluc¸ ˜ ao trivial n˜ ao seja a ´ unica, ent˜ ao as func¸ ˜ oes s˜ ao linearmente dependentes. A dimens˜ ao do subespac¸o gerado pelas quatro func¸ ˜ oes ´ e menor ou igual a quatro. Para verificar se as quatro func¸ ˜ oes s˜ ao linearmente dependentes ou independentes, resolvemos o sistema:            xλab(we1) + yλcd(we1) + zλad(we1) + wλbc(we1) = 0 xλab(we2) + yλcd(we2) + zλad(we2) + wλbc(we2) = 0 xλab(we3) + yλcd(we3) + zλad(we3) + wλbc(we3) = 0 xλab(we4) + yλcd(we4) + zλad(we4) + wλbc(we4) = 0 xλab(we5) + yλcd(we5) + zλad(we5) + wλbc(we5) = 0 ⇔            x+z= 0 x+w= 0 z+w= 0 y+w= 0 y+z= 0 ⇔           z=−x w=−x − y=−w z=−y ⇔           z= 0 w= 0 −x−x= 0 ⇒x= 0 y= 0 z= 0 40 rank(L) = dim(<L>) = 4 Este sistema s´ o tem uma soluc¸ ˜ ao, a soluc¸ ˜ ao trivial, o que quer dizer que as quatro func¸ ˜ oes s˜ ao linearmente independentes e a dimens˜ ao do subespac¸o gerado por elas ´ e igual ` a sua cardinalidade. Uma base do matroide associado a esta X-´ arvore ´ e um lasso L, com cardinalidade igual a |E|= 5 erank(L) = 5. Vamos verificar se o lasso L={ab, cd, ad, bc, bd}tem as propriedades referidas acima. Com o intuito de calcular a dimens˜ ao do subespac¸o gerado pelas cinco func¸ ˜ oes, vamos considerar a matriz formada pelos vetores λxy, com xy ∈L: ML=      λab λcd λad λbc λbd      =      11000 00011 10101 01110 01101       Como det(ML) = −46= 0, ent˜ ao as cinco func¸ ˜ oes s˜ ao linearmente independentes, logo a dimens˜ ao do subespac¸o gerado pelas mesmas ´ e igual ` a sua cardinalidade. rank(L) = dim(<L>) = 5 Portanto L´ e uma base do matroide M(T). Observe-se que L´ e um edge-weight lasso. Dada uma func¸ ˜ ao peso w∈RE, que atribui um valor w(ei)∈Ra cada aresta ei∈E, seja Dw(x, y)a distˆ ancia entre o v´ ertice xeyrelativamente a w. Supondo que as distˆ ancias (relativamente a w) entre os pares de folhas em Ls˜ ao conhecidas, temos            Dw(a, b) = x0 Dw(c, d) = x1 Dw(a, d) = x2 Dw(b, c) = x3 Dw(b, d) = x4 ⇔           w(e1) + w(e2) = x0 w(e4) + w(e5) = x1 w(e1) + w(e3) + w(e5) = x2 w(e2) + w(e3) + w(e4) = x3 w(e2) + w(e3) + w(e5) = x4 Observe-se que a matriz formada pelos coeficientes do sistema ´ e igual a ML. O determinante da matriz ´ e diferente de zero, ent˜ ao o sistema ´ e poss´ ıvel e determinado, logo L´ e um edge-weight lasso, j´ a que determina w. Na Figura 4.5 est´ a representado o grafo Γ(L)associado ao lasso L. Exemplo 18. Consideremos a X-´ arvore representada na Figura 4.6. Seguindo o modelo dos exemplos anteriores, queremos determinar, para um certo lasso L, o seu rank. Nesta X-´ arvore |E|= 7. Seja L={ab, be, de, cd}um lasso associado a esta X- ´ arvore. λab 7→ (λab(we1)λab(we2)λab(we3)λab(we4)λab(we5)λab(we6)λab(we7))=(1100000) λbe 7→ (λbe(we1)λbe(we2)λbe(we3)λbe(we4)λbe(we5)λbe(we6)λbe(we7))=(0111000) 41 Figura 4.5: Grafo Γ(L)associado ao lasso L={ab, cd, ad, bc, bd}. Figura 4.6: X-´ arvore lagarta. λde 7→ (λde(we1)λde(we2)λde(we3)λde(we4)λde(we5)λde(we6)λde(we7))=(0001101) λcd 7→ (λcd(we1)λcd(we2)λcd(we3)λcd(we4)λcd(we5)λcd(we6)λcd(we7))=(0000011) Uma forma de calcular a dimens˜ ao do subespac¸o gerado pelas quatro func¸ ˜ oes ´ e verificar se existem x, y, z ew∈Rtal que: xλab +yλbe +zλde +wλcd = 0. Resolvendo o sistema:                    xλab(we1) + yλbe(we1) + zλde(we1) + wλcd(we1) = 0 xλab(we2) + yλbe(we2) + zλde(we2) + wλcd(we2) = 0 xλab(we3) + yλbe(we3) + zλde(we3) + wλcd(we3) = 0 xλab(we4) + yλbe(we4) + zλde(we4) + wλcd(we4) = 0 xλab(we5) + yλbe(we5) + zλde(we5) + wλcd(we5) = 0 xλab(we6) + yλbe(we6) + zλde(we6) + wλcd(we6) = 0 xλab(we7) + yλbe(we7) + zλde(we7) + wλcd(we7) = 0 ⇔                    x= 0 x+y= 0 y= 0 y+z= 0 z= 0 w= 0 z+w= 0 ⇔       x= 0 y= 0 z= 0 w= 0 . Como a ´ unica soluc¸ ˜ ao do sistema ´ e a soluc¸ ˜ ao trivial, ent˜ ao as quatro func¸ ˜ oes s˜ ao linearmente independentes, o que quer dizer que a dimens˜ ao do subespac¸o gerado por elas ´ e igual ` a sua cardinalidade. 42 rank(L) = dim(L>)=4 Utilizando o mesmo processo, determinamos que: L={ab, be, de, cd, ce}:rank(L) = dim(<L>)=5 L={ab, be, de, cd, ce, ae}:rank(L) = dim(<L>) = 6 Com o intuito de determinar uma base do matroide associado ` aX-´ arvore, consideramos o lasso L={ab, bc, cd, ad, be, ce, bd}, com |L|=|E|= 7. Para calcular o rank do lasso, a dimens˜ ao do subespac¸o gerado pelas sete func¸ ˜ oes, vamos considerar a matriz formada pelos vetores λxy, com xy ∈L: ML=           λab λbc λcd λad λbe λce λbd           ⇔           1100000 0110110 0000011 1010101 0111000 0001110 0110101           Como o det(ML) = −86= 0, ent˜ ao as sete func¸ ˜ oes s˜ ao linearmente independentes, o que quer dizer que a dimens˜ ao do subespac¸o gerado pelas mesmas ´ e igual ` a sua cardinalidade. rank(L) = dim(<L>) = 7 Observe-se que L´ e um edge-weight lasso. Dada uma func¸ ˜ ao peso w∈RE, que atribui um valor w(ei)∈Ra cada aresta ei∈E, seja Dw(x, y)a distˆ ancia entre o v´ ertice xeyrelativamente a w. Supondo que as distˆ ancias (relativamente a w) entre os pares de folhas em Ls˜ ao conhecidas, temos                    Dw(a, b) = x0 Dw(b, e) = x1 Dw(d, e) = x2 Dw(c, d) = x3 Dw(c, e) = x4 Dw(a, e) = x5 Dw(b, d) = x6 ⇔                    w(e1) + w(e2) = x0 w(e2) + w(e3) + w(e5) + w(e6) = x1 w(e6) + w(e7) = x2 w(e1) + w(e3) + w(e5) + w(e7) = x3 w(e2) + w(e3) + w(e4) = x4 w(e4) + w(e5) + w(e6) = x5 w(e2) + w(e3) + w(e5) + w(e7) = x6 Observe-se que a matriz formada pelos coeficientes do sistema ´ e igual a ML. O determinante da matriz ´ e diferente de zero, ent˜ ao o sistema ´ e poss´ ıvel e determinado, logo L´ e um edge-weight lasso, j´ a que determina w. Na Figura 4.7 est´ a representada o grafo Γ(L)associado ao lasso L. Exemplo 19. Consideremos a X-´ arvore representada na Figura 4.8. Seguindo o modelo dos exemplos anteriores, queremos determinar, para um certo lasso L, o seu rank. Com o intuito de determinar uma base do matroide associado ` aX-´ arvore, consideramos o lasso L={ab, bc, cd, ad, ac, ae, bf, cf, de},|L|=|E(T)|. 43 Figura 4.7: Grafo Γ(L)associado ao lasso L={ab, bc, cd, ad, be, ce, bd}. Figura 4.8: X-´ arvore lagarta. Para calcular o rank do lasso, a dimens˜ ao do subespac¸o gerado pelas sete func¸ ˜ oes, vamos considerar a matriz formada pelos vetores λxy,∀xy ∈L: ML=               λab λbc λcd λad λac λae λbf λcf λde               ⇔               110000000 011010110 000000011 101010101 101010110 101100000 011011000 000001110 000110100               Como o det(ML) = 16 6= 0, ent˜ ao as nove func¸ ˜ oes s˜ ao linearmente independentes, o que quer dizer que a dimens˜ ao do subespac¸o gerado pelas mesmas ´ e igual ` a sua cardinalidade. rank(L) = dim(<L>) = 9 Na Figura 4.9 est´ a representada o grafo Γ(L)associado ao lasso L. Teorema 4.2. Seja T= (V, E)uma X-´ arvore e L⊆X 2. As seguintes condic¸ ˜ oes s˜ ao equivalentes: (a) L´ e um edge-weight lasso; (b) Dado w0∈RE, se λT xy(w0) = 0 para toda a corda xy ∈L, ent˜ ao w0= 0; (c) dimhLi=|E|. 44 Figura 4.9: Grafo Γ(L)associado ao lasso L={ab, bc, cd, ad, ac, ae, bf, cf, de}. Em particular, se L´ e um edge-weight lasso, ent˜ ao ∪L=Xe|L| ≥ |E|. Se L´ e um edge-weight lasso minimal ent˜ ao |L|=|E|. Demonstrac¸ ˜ ao. Prova de (a) =⇒(b): Suponhamos que L´ e um edge-weight lasso e que w0∈RE´ e tal que λT xy(w0) = 0 para toda a corda xy ∈L. Seja ω:E→R>0uma func¸ao de peso nas arestas de T(por exemplo, w=Pe∈Ewe). Ent˜ ao existe 6= 0 tal que w+w0toma valores em R>0. Al´ em disso, λT xy(w+w0) = λT xy(w) + λT xy(w0) = λT xy(w), logo (T, w)L ≡(T, w +w0). Como L´ e um edge-weight lasso, resulta que w=w+w0e assim w0= 0 pois 6= 0. Suponhamos ainda, por reduc¸ao ao absurdo, que existe z∈X\ ∪L, e seja f∈Ea ´ unica aresta incidente com z. Ent˜ ao para todo o xy ∈L,λT xy(wf)=0, j´ a que f /∈ET(xy). Pelo que acab´ amos de mostrar, ter´ a de ser wf= 0, o que ´ e absurdo. Logo ∪L=X. Prova de (b) =⇒(a): Suponhamos que (b) se verifica. Sejam w, w0:E→R≥0duas func¸oes de peso pr´ oprias (isto ´ e, wew0tomam valores positivos nas arestas interiores de T) e tais que (T, w)L ≡(T, w0). Ent˜ ao λT xy(w) = λT xy(w0)para todo o xy ∈L, e assim w−w0anula todas as func¸ ˜ oes λT xy. Conclui-se portanto de (b) que w−w0= 0, o que mostra que L´ e um edge-weight lasso. Seja hLio subespac¸o de c REgerado por {λT xy :xy ∈L}. Como dim c RE=|E|, temos dimhLi≤|E|. Considere-se a aplicac¸ ˜ ao linear Φ : RE−→ d hLi, w 7→ Φw, com Φw(f) = f(w), para f∈ hLi. Temos w∈ker Φ ⇔Φw(f)=0∀f∈ hLi ⇔Φw(λT xy) = 0 ∀xy ∈L ⇔λT xy(w) = 0 ∀xy ∈L. Logo, (b) verifica-se se e s´ o se Φ´ e injetiva. Assim, assumindo (b) temos |E|= dim RE= dim imΦ≤dim d hLi= dimhLi ≤ |E|, o que implica que dimhLi=|E|. Resta verificar que (c) implica (b). Suponhamos ent˜ ao que dimhLi=|E|, e portanto que hLi=c RE. Se 06=w∈RE, ent˜ ao existe ˆw∈c REtal que ˆw(w)6= 0. Como hLi=c RE, 45 Acolec¸ ˜ ao das bases j´ a foi descrita acima e coincide com a colec¸ ˜ ao dos geradores de M(T)com cinco elementos. Este matroide tem 132 bases. 4.3 Forma recursiva para a construc¸ ˜ ao das bases do matroide Seja T= (V, E)uma X-´ arvore. Dada uma aresta interior {u, v}=f∈E, a contrac¸ ˜ ao de Tem f´ e a X-´ arvore denotada por T/f tal que: •V(T/f) = (V\ {u, v})∪ {θf}, onde θf´ e um novo v´ ertice que substitui uev; •E(T/f) = E\ {f}, em que identificamos uma aresta {a, b} ∈ E\ {f}com a aresta: –{a, b} ∈ E(T/f)se {a, b}∩{u, v}=∅; –{a, θf} ∈ E(T/f)se b∈ {u, v}; –{b, θf} ∈ E(T/f)se a∈ {u, v}. ´ E f´ acil de verificar que T/f ´ e ainda uma X-´ arvore e que se g∈E´ e uma aresta interior de Tdiferente de f, ent˜ ao g´ e tamb´ em uma aresta interior de T/f. Deste modo ´ e poss´ ıvel formar as contrac¸ ˜ oes (T/f)/g e(T/g)/f, e verificar que (T/f)/g = (T/g)/f. Assim, dado F⊆Eum conjunto de arestas interiores de T,T/F designar´ a a X-´ arvore que se obt´ em fazendo a contrac¸ ˜ ao sucessiva (por qualquer ordem) das arestas de F. Pela definic¸ ˜ ao de contrac¸ ˜ ao que foi dada, E(T/F)identifica-se naturalmente com E\F⊆E. Por fim, observamos que dada uma X-´ arvore T= (V, E), existe um conjunto Fde arestas interiores de Ttal que T/F ´ e uma X-´ arvore estrela. Estas observac¸ ˜ oes, conjugadas com a descric¸ ˜ ao do matroide M(T∗)dada na Propisic¸ ˜ ao 1 para uma X-´ arvore estrela T∗, motivam o estudo da relac¸ao entre os matroides M(T)eM(T/f), que faremos de seguida. Com o intiuto de ilustrar a contrac¸ ˜ ao sucessiva das arestas interiores de uma X- ´ arvore, vamos considerar a X-´ arvore T= (V, E)representada na Figura 4.19. Figura 4.19: X-´ arvore T. O conjunto das arestas interiores de T= (V, E)´ e{f1, f2, f3, f4}e o conjunto dos v´ ertices interiores ´ e{t, u, v, w, z}. Comecemos por contrair a aresta f1=tu ` aX-´ arvore T. A X-´ arvore obtida, representada na Figura 4.20, ´ e a X-´ arvore denotada por T1=T\{f1}, tal que: •V(T1) = V(T\{f1}) = (V\{u, v})∪ {θf1}, 52 •E(T1) = E(T\{f1}) = (E\f1), onde θf1´ e o novo v´ ertice que substitui uet. Figura 4.20: X-´ arvore T1=T/{f1}. Do mesmo modo, contraimos as arestas interiores f2,f3ef4, at´ e obter a X-´ arvore estrela. Esta construc¸ ˜ ao est´ a representada na Figura 4.21. Figura 4.21: X-´ arvores: T2=T1/{f2};T3=T2/{f3};T3=T3/{f4} Se F´ e um conjunto de arestas interiores de T, j´ a observ´ amos que E(T/F) = E\F⊆ E. Logo, a inclus˜ ao RE\F,→REque se obt´ em estendendo w:E\F→RaE, definindo w(f) = 0 para todo o f∈F, d´ a origem a uma sobrejec¸ ˜ ao c RE[ RE\F, dada pela restric¸ ˜ ao λ:RE→R7→ λ|E\F:E\F→R. Em particular, usaremos a identificac¸ ˜ ao seguinte: RE\F={w∈RE:w(f) = 0 para todo o f∈F}. Lema 5. Sejam T= (V, E)uma X-´ arvore, F⊆Eum conjunto de arestas interiores de TeT/F aX-´ arvore obtida de Tpor contrac¸ ˜ ao das arestas em F. Ent˜ ao: (i) Para todo o xy ∈X 2,λT xy|E\F=λT/F xy . (ii) Para todo o subconjunto L⊆X 2, tem-se rankT(L) = rankT/F (L) + dim{λ∈ hLiT:λ(we) = 0,∀e∈E\F} ≤rankT/F (L) + |F|. (iii) Se L´ e um edge-weight lasso para Tent˜ ao L´ e um edge-weight lasso para T/F. 53 Demonstrac¸ ˜ ao. Dados x, y ∈X, o caminho em T/F entre xeyobt´ em-se do caminho em Tentre xey, eliminando neste ´ ultimo as arestas de f∈Fque nele ocorrem (e fazendo a respetiva substituic¸ ˜ ao das extremidades de fpelo v´ ertice θf). Logo, λT xy(w) = λT/F xy (w) para todo o w∈RE\F={w∈RE:w(f) = 0,∀f∈F}, o que prova (i). Para mostrar (ii), tome-se L⊆X 2e considere-se o subconjunto Φ : c RE→[ RE\F induzida pela inclus˜ ao RE\F. Ent˜ ao, rankT(L) = dim(<L>T) = dim(< λT xy :xy ∈L>) = dim(<Φ(λT xy) : xy ∈L>) + dim(KerΦ∩<LT>). Ora, Φ(λT xy) = λT xy|E\F=λT xy e dado λ∈c RE, λ∈KerΦ⇔λE\F= 0 ⇔λ(w)=0∀w∈RE\F ⇔λ(we)=0∀e∈E\F j´ a que {ee:e∈E\F}´ e uma base de RE\F. Logo, dim(<Φ(λT xy) : xy ∈L>) = dim(< λT\F xy :xy ∈L>) =rankT\F(L) e dim(KerΦ∩<L>T) = dim{λ∈<L>T:λ(we) = 0∀e∈E\F} ≤dim(KerΦ) = dim( c RE)−dim(ImΦ) =|E| − dim( [ RE\F) =|E| − (|E|−|F|) = |F| A prova de (iii) ´ e consequˆ encia imediata de (ii), j´ a que L´ eedge-weight lasso pata T ⇔rank(L)T=|E|. Proposic¸ ˜ ao 2. Dados uma X-´ arvore T=V, E, uma aresta interior f∈E,xy ∈X 2 eBuma base do matroide M(T/f), denotemos por ρxy ∈RBa´ unica func¸ ˜ ao que satisfaz λT/f xy =Pb∈Bρxy(b)λT/f b. Ent˜ ao B∪ {xy}´ e uma base de M(T)se e s´ o se Pb∈Bρxy(b)δf|b6=δf|xy. Logo, o conjunto das bases de M(T)´ e dado por B(T) = {B∪ {xy}:xy ∈X 2, B ∈B(T/f)eX b∈B ρxy(b)δf|b6=δf|xy}. 54 Demonstrac¸ ˜ ao. Pelo lema anterior, sabemos que dada uma base B0de M(T),B0´ e gerador de M(T/f), logo existe xy ∈B0tal que B=B0\ {xy}´ e base de M(T/f), o que mostra que as bases de M(T)s˜ ao da forma B∪ {xy}, com Bbase de M(T/f)e xy ∈X 2. Resta determinar para que escolhas de B∈B(T/f)exy ∈X 2´ e que B∪{xy} ´ e base de M(T). Sejam ent˜ ao xy ∈X 2eBuma base de M(T/f). Em particular, rankT/f (B) = |B|= |E| − 1. Pela parte (ii) do lema anterior temos que B∪ {xy}´ e base de M(T)⇔rankT(B∪ {xy}) = |E| ⇔dim ΛB,xy = 1 ⇔dim ΛB,xy 6= 0 ⇔ΛB,xy 6={0}, onde ΛB,xy ={λ∈ hB∪ {xy}iT:λ(we) = 0,∀e6=f}. Seja λ∈ hB∪ {xy}iT. Ent˜ ao existem c∈Reρ∈RBtais que λ=cλT xy +Pb∈Bρ(b)λT b, eλ∈ΛB,xy se e s´ o se 0 = λ|E\{f}=cλT/f xy +X b∈B ρ(b)λT/f b.(4.1) Seja ent˜ ao ρxy ∈RBdada por λT/f xy =Pb∈Bρxy(b)λT/f b. Como as func¸ ˜ oes λT/f b, com b∈B, s˜ ao linearmente independentes, resulta de (4.1) que ρ(b) = −cρxy(b), para todo o b∈B. Assim, ΛB,xy =hλT xy −Pb∈Bρxy(b)λT bie ΛB,xy 6={0} ⇔ λT xy −X b∈B ρxy(b)λT b!(wf)6= 0 ⇔X b∈B ρxy(b)δf|b6=δf|xy, o que estabelece o resultado pretendido. Para ilustrar a Proposic¸ ˜ ao 2, vamos considerar a X-´ arvore representada na Figura 4.1 (ii), uma X-´ arvore Tcom conjunto de folhas X:= {a, c, b, d}. Neste caso, existe uma relac¸ ˜ ao linear entre as func¸ ˜ oes λT xy com xy ∈X 2: λT ac +λT bd =λT ad +λT bc :RE−→ R w7→ 2w(eab|cd) + Pe∈E;e6=eab|cd w(e) . Esta ´ e a ´ unica relac¸ ˜ ao linear em {λT xy :xy ∈X 2}. Assim, as bases do matroide M(T), associado a esta X-´ arvore, s˜ ao os quatro conjuntos constituidos por subconjuntos de Lde X 2, com cinco elementos, que n˜ ao contˆ em exactamente uma das quatro cordas ac, ad, bc, bd, ou equivalentemente, com |L∩ {ac, ad, bc, bd}| ≤ 3. H´ a quatro folhas, logo 4 2= 6 cordas, e destas seis cordas queremos construir conjuntos de cinco elementos, 6 5= 6 hip´ oteses. Nestas seis hip´ oteses temos que retirar os conjuntos em que as quatro cordas ac, bd, ad, bc pertencem em simultˆ aneo (existem dois conjuntos deste tipo). Na Figura 4.22, est˜ ao representados os quatro grafos Γ(L), associados aos lassos Lde X 2, que s˜ ao bases do matroide M(T). 55 Figura 4.22: Grafos Γ(L), associados ` as bases do matroide M(T). Pelo Teorema 2.5, sabemos que, se L´ e um edge-weight lasso, ent˜ ao o grafo Γ(L) deve ser fortemente n˜ ao bipartido com um ciclo de comprimento ´ ımpar. Claramente, se fcoincide com a ´ unica aresta interior de T, isto ´ e, a aresta denotada por eab|cd da Figura 4.1 (ii),T\f´ e equivalente ` a´ arvore estrela T∗representada na Figura 2.6 (i). O grafo Γ(L), correspondente ` as bases da X-´ arvore T∗,´ eom´ ınimo grafo fortemente n˜ ao bipartido com conjunto de v´ ertices X, que tem que ter um ciclo de comprimento ´ ımpar. O grafo tem quatro cordas, logo o ´ unico ciclo de comprimento ´ ımpar ´ e um ciclo de comprimento trˆ es, neste caso, existem quatro possibilidades, ilustradas na Figura 4.23. 56 Figura 4.23: Grafos Γ(L), associados ` as bases do matroide M(T). O v´ ertice que fica de fora tem trˆ es possibilidades de se ligar ao triˆ angulo criado, ou seja, temos doze bases para o matroide associado ` aX-´ arvore estrela T∗. Os grafos Γ(L)associados aos subconjuntos L, que s˜ ao bases do matroide associado ` aX- ´ arvore estrela T∗, est˜ ao representados na Figura 4.12. Observando as simetrias da ´ arvore T, podemos formar duas ´ orbitas relativas ao grupo de simetria de T, que s˜ ao as bases: B1:= {ab, bc, ca, da}eB2:= {ab, bc, ca, dc}, representadas na Figura abaixo. Figura 4.24: Γ(B1);Γ(B2). Com o intuito de encontrar as bases do matroide associado ` aX-´ arvore T, temos que encontrar os conjuntos B=Bi∪ {xy}tais que B´ e uma base de T∗. No caso de B1, as ´ unicas cordas que ficaram de fora s˜ ao db edc. Vamos verificar se ´ e poss´ ıvel acrescentar ` a base B1alguma das cordas. Temos que f:= eab|cd e que: λT\f db =λT\f da −λT\f ac +λT\f cb eλT\f dc =λT\f da −λT\f ab +λT\f bc enquanto, λT db(wf) = λT da(wf)−λT ac(wf) + λT cb(wf)⇔δf|bd =δf|da −δf|ac +δf|cb ⇔ ⇔1−1 + 1 = 1 ⇔1 = 1 57 e λT dc(wf) = λT da(wf)−λT ab(wf) + λT bc(wf)⇔δf|dc =δf|da −δf|ab +δf|bc ⇔ ⇔0 = 1 −0+1⇔06= 2 o que implica, que para todas as bases B1, podemos adicionar cordas dc, mas n˜ ao db. No caso de B2, as ´ unicas cordas que ficaram de fora s˜ ao da edb. Vamos verificar se ´ e poss´ ıvel acrescentar ` a base B2alguma destas cordas: λT\f da =λT\f dc −λT\f cb +λT\f ba eλT\f db =λT\f dc −λT\f ca +λT\f ab enquanto, 1 = λT da(wf)6=λT dc(wf)−λT cb(wf) + λT ba(wf) = −1 e 1 = λT db(wf)6=λT dc(wf)−λT ca(wf) + λT ab(wf) = −1 o que implica que, para as bases do tipo B2, podemos adicionar qualquer uma das cordas. Exemplo 22. Com o intuito de descobrir uma base do matroide associado ` aX-´ arvore representada na Figura 4.25, vamos usar a construc¸ ˜ ao recursiva, enunciada na Proposic¸ ˜ ao 2. Figura 4.25: X-´ arvore com cinco folhas. 1) Uma base do matroide associado ` aX-´ arvore T/{f, g}, ou seja, a ´ arvore estrela representada na Figura 4.26. Figura 4.26: T/{f, g},´ arvore estrela com cinco folhas: T∗ Como j´ a vimos anterioremente, as bases do matroide M(T/{f, g}) = L(T∗), s˜ ao conjuntos Lpara os quais o seu grafo associado, Γ(L)tem uma das seguintes representac¸ ˜ oes: 58 Figura 4.27: Grafos Γ(L), associados a um lasso Lque s˜ ao bases do matroide associado ` aX-´ arvore da Figura 4.26. Por exemplo, o lasso L:= {ab, bc, bd, cd, de}, que ´ e uma configurac¸ ˜ ao D,´ e uma base do matroide M(T∗). 2) Uma base do matroide associado ` aX-´ arvore T/{g}, ou seja, ` a´ arvore representada na Figura 4.28. Figura 4.28: T/{g}. Seja xy uma corda e fa aresta interior da X-´ arvore. Pela Proposic¸ ˜ ao 2 sabemos que, se B´ e uma base de T/{f, g}exy uma corda, ent˜ ao B∪ {xy}´ e uma base do matroide associado a T/{g}se e s´ o se: X b∈B ρxy(b)δf|b6=δf|xy. Neste caso, as cordas xy, podem ser: ac, ad, ae, be ou ce. Para verificar se B∪ {xy}´ e uma base de T/{g}, basta verificar se a desigualdade se verifica. Seja B={ab, bc, bd, cd, de}uma base de T∗. λT/{f,g} ac =λT/{f,g} ab −λT/{f,g} bd +λT/{f,g} cd ent˜ ao λT/{g} ac =λT/{g} ab −λT/{g} bd +λT/{g} cd ⇔ ⇔δf|ac =δf|ab −δf|bd +δf|cd ⇔ ⇔1 = 0 −1+0⇔ ⇔16= 1 Logo B∪ {ac}=B1={ab, bc, bd, cd, de, ac}´ e uma base de T/{g}. 3) Uma base do matroide associado ` aX-´ arvore T, a ´ arvore representada na Figura 4.25. 59 Pela Proposic¸ ˜ ao 2 sabemos que, se B1´ e uma base de T/{g}exy uma corda, ent˜ ao B1∪ {xy}´ e uma base do matroide associado a Tse e s´ o se: X b∈B ρxy(b)δf|b6=δf|xy. Neste caso, as cordas xy, podem ser: ad, ae, be ou ce onde B1={ab, bc, bd, cd, de, ac}. λT/{g} ad =λT/{g} ae −λT/{g} bc +λT/{g} bd +λT/{g} cd −λT/{g} de ent˜ ao λT ad =λT ae −λT bc +λT bd +λT cd −λT de ⇔ ⇔δf|ad =δf|ae −δf|bc +δf|bd +δf|cd −δf|de ⇔ ⇔1 = 0 −1+1+0−1⇔ ⇔16=−1 Logo, B1∪ {ad}=B2={ab, bc, bd, cd, de, ac, ad}´ e uma base de M(T). A´ arvore Ttem os seis seguintes grupos de simetria: {Id, (ab),(cd),(ab)(cd),(ac)(bd), (ad)(bc)}. Se aplicarmos as simetrias ` a base B2, obtemos cinco bases distintas: B3={ab, ac, ad, cd, de, bc, bd} B4={ab, bd, bc, cd, ce, ad, ac} B5={ab, ad, ac, cd, ce, bd, bc} B6={cd, da, bd, ab, be, ac, cb} B7={dc, bc, ca, ba, ae, db, ad} que s˜ ao bases do matroide associado ` aX-´ arvore T. 4.4 Caraterizac¸ ˜ ao da X-´ arvore pelo seu matroide Vejamos que o matroide M(T)de uma X-´ arvore Tdetermina essa X-´ arvore, a menos de isomorfismos de X-´ arvores. Definic¸ ˜ ao 25. Dada uma X-´ arvore TeY⊆Xcom |Y| ≥ 3, a restric¸ ˜ ao de TaY´ e aY-´ arvore denotada por T|Yque se obt´ em da sub-´ arvore de Tminimal que cont´ em os caminhos entre os v´ ertices de Y, por supress˜ ao dos v´ ertices de grau 2 (isto ´ e, substituindo cada v´ ertice vde grau 2 e as duas arestas incidentes com vpor uma ´ unica aresta com extremidades nos dois v´ ertices adjacentes a v). O conjunto de v´ ertices e arestas de T|Ydenotam-se por VYeE|Y. Dado wuma func¸ ˜ ao peso nas arestas de T,w|Y´ e a func¸ ˜ ao peso induzida em T|Yque atribui a casa aresta {u, v}de E|Ya distˆ ancia em Tentre os v´ ertices uev, relativamente aw. Note-se que, para y, y0∈Yew∈RE,λT yy0(w) = λT\Y yy0(w|Y) 60 Lema 6. Dada uma X-´ arvore TeY⊆Xum conjunto com quatro elementos, digamos Y={a, b, c, d},T|Y∼ =Tab|cb ⇔existe alguma base Bde M(T)que cont´ em Labcd = {ab, bc, cd, ad}e nenhuma base de M(T)cont´ em {ac, ad, bc, bd}. Demonstrac¸ ˜ ao. Se T|Y∼ =Tab|cd, ent˜ ao as func¸ ˜ oes λT|Y xy com xy ∈Labcd s˜ ao linearmente independentes, logo o mesmo se sucede com a func¸ ˜ ao λT xy,xy ∈Labcd. Assim, existe alguma base de M(T)que cont´ em Labcd. Al´ em disso, em Tab|cd, λT|Y ac +λT|Y bd =λT|Y ad +λT|Y bc , logo em T, λT ac +λT bd =λT ad +λT bc, e portanto nenhuma base de M(T)cont´ em {ac, ad, bc, bd}. Reciprocamente, das quatro possibilidades para T|Y:T|ab|cd,T|ad|bc,T|ac|bd eT∗, a ´ arvore estrela com folhas {a, b, c, d}. a relac¸ ˜ ao λT0 ab +λT0 cd =λT0 ad +λT0 bc ´ e satisfeita em T0=Tac|bd e em T0=T∗, logo, se Labcd est´ a contido em alguma base de M(T), resulta que T|YTab|bd eT|YT∗. Al´ em disso, se T|Y∼ =Tad|bc ent˜ ao {λT|Y ac , λT|Y ad , λT|Y bc , λT|Y bd }´ e linearmente independente, o que implica que λT ac, λT ad, λT bc, λT bd tamb´ em s˜ ao linearmente independentes, portanto existe alguma base de M(T)que cont´ em {ac, ad, bc, bd}, o que ´ e absurdo. Logo, T|YTad|bc. Logo T|Y∼ =Tab|cd. Definic¸ ˜ ao 26. Dado uma X-´ arvore T, definimos Q(T) = {ab|cd :{a, b, c, d} ∈ X 4eT|{a,b,c,d}∼ = Tab|cd}. Teorema 4.3. ([3, Corol´ ario 6.3.8]) Dadas duas X-´ arvores T1eT2,T1∼ =T2⇔Q(T1) = Q(T2). Corol´ ario 2. Para quaisquer X-´ arvores T1eT2,M(T1) = M(T2)⇔T1∼ =T2. Demonstrac¸ ˜ ao. (⇐:) Se T1∼ =T2ent˜ ao ´ e facil ver que M(T1) = M(T2), j´ a que um isomorfismo de X-´ arvores se restringe ` a identidade em X. (⇒:) Como M(T1) = M(T2)ent˜ ao as bases dos dosi matroides s˜ ao iguais. Pelo Lema 6, sabemos que se M(T1) = M(T2)ent˜ ao Q(T1) = Q(T1)e pelo Teorema 4.3 podemos concluir que T1∼ =T2. 61