Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-06-22T11:43:28Z No. of bitstreams: 1 texto completo.pdf: 3061093 bytes, checksum: 5af4cd5ec886c8001e3e331f2bd2e133 (MD5) / Made available in DSpace on 2017-06-22T11:43:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 3061093 bytes, checksum: 5af4cd5ec886c8001e3e331f2bd2e133 (MD5) Previous issue date: 2016-10-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Recentemente, Ceratocystis fimbriata Ellis & Halsted foi relatado em Tectona grandis L. f (teca) e Carapa guianensis Aubl. (andiroba) no Brasil. Em teca, o fungo provoca descoloração do lenho e morte das plantas afetadas, o que compromete a produção de madeira nobre para serraria. Em andiroba, infecta e mata sementes e mudas, o que pode afetar negativamente sua regeneração natural e consequentemente sua biodiversidade. A identificação de C. fimbriata nessas hospedeiras foi baseada apenas em características morfológicas e em sequências gênicas da região ITS. Além disso, não foram analisadas suas relações filogenéticas com outros isolados e espécies de Ceratocystis e nem a variabilidade genética e fisiológica de suas populações. Tais estudos são fundamentais para embasar as estratégias de controle da doença. Deste modo, o presente estudo teve como objetivos: 1) Avaliar as relações entre os isolados do fungo de ambas as espécies hospedeiras com isolados de outros hospedeiros do Clado da América Latina por meio dos genes “mating type” e da região ITS rDNA. 2) Avaliar a interesterilidade por meio de cruzamentos entre isolados obtidos de diferentes espécies hospedeiras. 3). Determinar a variabilidade genética nas populações de C. fimbriata, por meio de marcadores microssatélites e sua especialização fisiológica por meio de inoculações cruzadas. Dentre 24 isolados do fungo, obtidos de teca de quatro localidades do Mato Grosso e 73 isolados de C. fimbriata de andiroba do Acre, Roraima e Amazonas, foram identificados novos haplótipos de ITS e mating type, distribuídos entre outros isolados dentro do Clado da América Latina (CAL), que residem em um único grupo juntamente com isolados de batata doce, a partir do qual a espécie foi originalmente descrita. Os isolados oriundos de teca e andiroba foram inter férteis com outras linhagens de C. fimbriata ̧ mostrando que pertencem a uma única espécie biológica de C. fimbriata. As análises de microssatélites da população do fungo em teca mostraram uma baixa variabilidade genética. Nas inoculações, apesar das mudas de teca apresentarem lesões relativamente pequenas, dois isolados de teca diferiram da testemunha. Os isolados de eucalipto não foram patogênicos em teca. As populações de C. fimbriata de andiroba dos três estados (AC, RR e AM) apresentaram 14 genótipos e variabilidade genética intermediária em relação a outras populações nativas do fungo. Inoculações cruzadas do fungo em andiroba, teca, eucalipto e mangueira, sugerem que os isolados de C. fimbriata destas espécies são hospedeiro-específicos e que existe variabilidade em agressividade entre os isolados do fungo de andiroba. / Recently, Ceratocystis fimbriata Ellis & Halsted was reported in Tectona grandis L. f (teak) and Carapa guianensis Aubl. (andiroba) in Brazil. In teak, the fungus causes death and wood discoloration, which affects the production of high valuable timber. In andiroba, the fungus infects and kills seeds and seedlings, which may affect negatively its natural regeneration and, probably, its biodiversity. The identification of C. fimbriata on these hosts was based only on morphological characteristics and analysis of ITS rDNA sequences. Furthermore, the genetic and physiological variability of C. fimbriata populations as well as their phylogenetic relationships with other isolates and species of Ceratocystis were not analyzed . Such studies are essential to support disease management strategies. Therefore, this study aimed to: 1) Assess the relationship among isolates of the fungus from both host species with isolates from other hosts of the Latin American Clade (LAC) by using mating type genes and ITS rDNA region. 2) Assess the interesterility through crossings between isolates from different host species. 3) Determine the genetic variability in populations of C. fimbriata through microsatellite markers and their physiological especialization by f cross-inoculation experiments. Out of 24 isolates of the fungus obtained from teak from of locations in the state of Mato Grosso, and of 73 isolates of C. fimbriata from andiroba in the states of Acre, Roraima and Amazonas, new ITS haplotypes and mating types identified were distributed among other isolates within the LAC and reside in a single group that includes isolates from sweet potato, from which the species was originally described. Teak and andiroba isolates were inter fertile with other strains of C. fimbriata, showing that this is a single biological species of C. fimbriata. Microsatellite analysis of the fungal population on teak showed low genetic variability. In cross-inoculations, although teak plants presented relatively small lesions, two isolates differed from the control. The eucalyptus isolates were not pathogenic on teak. The populations of C. fimbriata from andiroba of the three states (AC, AM, and RR) showed 14 genotypes and intermediary levels of genetic variability compared to other native populations of the fungus in Brazil. Cross-inoculations of andiroba, teak, eucalyptus and mango isolates suggest that the isolates of C. fimbriata from these species are host specific and that there is variability in aggressiveness among isolates of the fungus from andiroba.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-12-18T10:13:42Z No. of bitstreams: 1 texto completo.pdf: 888748 bytes, checksum: 0ed978f40dbb58619e83efdce22c7b01 (MD5) / Made available in DSpace on 2017-12-18T10:13:42Z (GMT). No. of bitstreams: 1 texto completo.pdf: 888748 bytes, checksum: 0ed978f40dbb58619e83efdce22c7b01 (MD5) Previous issue date: 2017-06-23 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Estudos que relacionam variação das propriedades tecnológicas do lenho da madeira ao longo da idade são importantes para determinar a idade de colheita da floresta, a fim de verificar se a madeira apresenta propriedades satisfatórias para determinado uso. O presente trabalho avaliou alterações nas propriedades da madeira ao longo da idade. No Capítulo I estudou-se influência da idade em teor de extrativos, propriedades físicas e relação cerne/alburno da madeira de Tectona grandis. Foi utilizada madeira aos 10, 12, 14 e 16 anos, em quatro repetições. De cada repetição, foram seccionados quatro toretes a 0,5 m (base); 2,3 m; 4,6 m e 6,9 m de altura. Destes, foram determinadas a relação C/A e confeccionadas amostras para umidade de equilíbrio higroscópico, densidade básica, retratibilidade e permeabilidade. O restante do material foi moído para avaliação do teor de extrativos. Os resultados foram comparados com os descritos na literatura. Neste capítulo concluiu-se que existe influência dos teores de extrativos na determinação da UEH, densidade e retratibilidade. A coloração entre cerne e alburno não influenciou a permeabilidade da madeira durante o envelhecimento do lenho. No Capítulo II foi avaliada a variabilidade radial das propriedades anatômicas e físicas da madeira de teca em diferentes idades. Foi utilizada madeira aos 10, 14 e 17 anos, em quatro repetições. De cada repetição, foram seccionados toretes da base (0,5 m acima do solo), divididos em dois discos transversais (superior e inferior) e, de cada disco, foi retirada um bagueta central amostrando as posições radiais de 0, 33, 66 e 99 % do raio. Da bagueta do disco superior, foram avaliadas a inclinação microfibrilar, comprimento, espessura da parede e diâmetro de lume das fibras e, frequência dos poros. Da bagueta do disco inferior, foram determinadas as retratibilidades radial, longitudinal, tangencial, volumétrica, fator anisotrópico e densidade básica. Utilizou-se o coeficiente de Pearson para avaliar o grau de correlação entre as propriedades da madeira e observou-se que variações anatômicas determinaram alterações nas propriedades físicas da madeira. Conclui-se que as correlações encontradas puderam descrever a maturação do lenho e observou-se que na idade de 17 anos, assim como nas regiões próximas à casca, há madeira mais resistente e com menores variações dimensionais. / Studies that relate the variation of the technological properties of the wood throughout the age are important to determine the time to remove the wood with satisfactory physical characteristics for certain use. The present work, was developed based on the alterations of the properties of the wood along the age. Chapter I evaluated the influence of age on extractive contents, physical properties and heartwood / sapwood (H / S) relation of Tectona grandis (teak) wood. Wood at 10, 12, 14 and 16 years old was used in four repetitions. From each replicate, were sectioned four torts at 0,5 m (base); 2.3 m; 4.6 m and 6.9 m height. From the torts, the H / S relation was determined and the samples were prepared to calculate the humidity of the hygroscopic equilibrium (HHE), basic density, retractability and permeability. The rest of the material was transformed into sawdust to evaluate the extractive content. The results were compared with the literature for the specie. So, in this chapter it is concluded that there is influence of the extractive contents in the determination of the HHE, density and retractability, and the coloration between heartwood and sapwood was not able to determine the permeability of the wood during its aging. Chapter II evaluated the radial variability of the anatomical and physical properties of teak wood at different ages. Wood at 10, 14 and 17 years old was used in four repetitions. From each repetition, torts were sectioned from the base (0,5 m above the ground), divided into two transverse discs and, from the central bag of each disc, the radial positions of 0, 33, 66 and 99% were sampled of only ray. From the upper bag, the microfibril inclination (MFA), length (CP) and wall thickness (FPE) of the fibers, lume diameter (DL) and pore frequency (PF) were evaluated. From the lower bag, were determined the radial (RR), longitudinal (RL), tangential (RT), volumetric (RV) retractibilities, and anisotropic factor (FA) and basic density (DB). Pearson's coefficient was used to evaluate the degree of correlation between anatomical and physical properties. It was observed that anatomical variations determined changes in the physical properties of the wood. It is concluded that the correlations found in this study could describe the maturation of the wood and it was observed that the age of 17 years as well as regions close to the bark have more resistant wood and with smaller dimensional variations.

SILVA, Ana Shirley Ferreira da. Um estudo computacional sobre o problema de decomposição de grafos em árvore. 2005. 111 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2005. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T18:14:01Z No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:35:55Z (GMT) No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5) / Made available in DSpace on 2016-07-13T12:35:55Z (GMT). No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5) Previous issue date: 2005 / The notion of Tree Decomposition was introduced by Robertson and Seymour in their seris of articles about graph minors and can be intuitively seen as an organization of the vertices and edges of the graph in a tree structure, being the treewidth equal to the size of the largest subset of vertices minus one. The minimum treewidth over all tree decompositions of a graph gives us the treewidth of the graph. Many hard problems can be polinomially solved for a graph G if a tree decomposition with bounded treewidth of G is given. For instance, hamiltonian cycle, maximum independent set isomorphism, vertex coloring, etc. The complexity of the algorithm that solves such problems are generally exponential on the width of the given tree decomposition. So, we can expect that finding a tree decomposition of minimum width is hard. In fact, Arnborg, Corneil and Proskurowski [2] showed that the problem os NP-hard. The problem of finding the treewidth of a graph is the subject of this thesis. The decision variation of the problem is, given a graph G and for a fixed integer k, deciding if the treewidth of G is at most k. We discuss a proof that the decision problem can be polynomially solved. In the last decade were proposed many heuristics for computing upper bounds [3, 10], lower bounds [6, 8, 11], enumeration methods [5] and approximative algorithms [1, 7, 4]. However, none of these results can be considered as good ones, since there is no benchmarks for with the treewidth is known, as well as the difference between the lower and upper bounds for the existing benchmarks is very large. Additionally, the enumeration method was showed to be inefficient even for the decision problem with k fixed in small values (e.g., k = 4) [12]. So, we propose another enumeration method for the problem that can be used along with branch and bound techniques. Actually, we work with the triangulation problem that is equivalent to the tree decomposition problem. We propose a new representation of a solution, wich uses the concept of total orders. Once a solution ca be represented like that, an algorithm that enumerates all the total extensions of a given partial order can be used to enumerate all solutions for the tree decomposition problem, as long as we offer the partial order containing only the reflexive pairs vv, where v is a vertex of the input graph. The proposed enumeration method is a modification of the Corrêa and Szwarcfiter algorithm [9]. This modification allows only the total extensions to be enumerated. The algorithm presents two principal advantages over the Bodlander and Kloks method: it can be used in conjunction with the Branch and Bound method; and it can enumerate a subspace of solutions, what can be useful if we know some existing relations in an optimal solution, or even to investigate such subspaces in order to characterize them. We have implemented and tested the proposed algorithm, applying the branch and bound method and restricting the subspace of solutions. The partial orders used to define the explored subspaces were obtained based on the labeling heuristics for finding upper bounds. Unfortunately, we did not obtain good results because, even when we restricted the subspace of solutions to be searched, the number of nodes generated in the branch and bound tree was too large, exceeding the machine’s memory capacity. In the text, we also present the proof of the NP-hardness of the problem, an algorithm to compute an optimal decompostion of a chordal graph, and also the many existing heuristics to compute lower and upper bounds. In addition, we implemented and tested the labeling heuristics for upper bounds and a GRASP heuristic, being the first application of a GRASP meta-heuristic to the problem. / A noção de Decomposição em árvore foi introduzida por Robertson e Seymour em sua série de artigos sobre menores de grafos e pode ser definida, intuitivamente, como uma organização dos vértices e arestas do grafo em uma estrutura de árvore, sendo a largura da decomposição igual ao tamanho do maior subconjunto de vértices relacionado a um nó desta estrutura menos um. A largura mínima de uma decomposição em árvore de um grafo G é chamada de largura em árvore de G. Vários problemas difíceis podem ser resolvidos em tempo polinomial, dada uma decomposição em árvore de largura limitada, como, por exemplo, Ciclo Hamiltoniano, Conjunto Independente Máximo, Isomorfismo, Coloração de Vértices, etc. A complexidade dos algoritmos que resolvem tais problemas são geralmente exponenciais na largura da decomposição fornecida. Logo, é esperado que encontrar uma decomposição de largura mínima seja um problema difícil. De fato, Arnborg, Corneil e Proskurowski [2] mostraram que o problema é NP - difícil. O problema de encontrar a largura em árvore de um grafo qualquer é o objeto de estudo da presente dissertação de mestrado. Uma restrição desse problema é o de decidir, para um inteiro k fixo, se a largura em árvore de G é no máximo k. Apresentamos a prova de que o problema para k fixo pode ser resolvido polinomialmente. Na última década foram propostas várias heurísticas que fornecem limites superiores para o problema [3, 10], heurísticas para o cálculo de limites inferiores [6, 8, 11], além de métodos enumerativos [5] e algoritmos aproximativos [1, 7, 4]. Porém, nenhum resultado obtido pode ser considerado bom, uma vez que não existe um benchmark para o qual se conhece a largura em árvore e os limites inferiores e superiores têm se mostrado muito distantes. Além disso, o algoritmo enumerativo existente mostrou-se ineficiente mesmo para o problema de decisão com k fixo em valores pequenos (por exemplo, k = 4) [12]. É neste quadro que propomos um método enumerativo para o problema. Na verdade, abordamos o problema de triangularização, que é equivalente ao problema de decomposição em árvore. Isso nos permitiu a proposta de uma nova representação para uma solução do problema que utiliza o conceito de ordens totais. Uma vez que as soluções podem assim ser representadas, um algoritmo que enumere as extensões totais de uma dada ordem parcial pode ser utilizado para enumerar todas as soluções do problema, bastando que fornecemos uma ordem que contenha apenas os pares reflexivos vv, onde v é um vértice do grafo de entrada. O método enumerativo proposto é uma modificação do algoritmo de Corrêa e Szwarcfiter [9]. Esta modificação faz com que apenas as extensões totais da ordem fornecida seja enumerada. O algoritmo apresenta duas principais vantagens com relação ao método enumerativo proposto por Bodlaender e Kloks: pode ser utilizado juntamente com o método “branch and bound”; e pode enumerar um sub-espaço de soluções, o que pode ser útil caso se conheça algumas relações existentes na solução ótima, ou mesmo para investigar determinados sub-espaços de soluções. Implementamos e testamos o algoritmo proposto, aplicando o método “branch and bound” e restringindo o espaço de soluções. As ordens parciais utilizadas para definir os sub-espaços explorados foram obtidas baseando-se nas heurísticas de limite superior que utilizam rotulação. Infelizmente, não obtivemos bons resultados, pois, mesmo restringindo o espaço de busca, a quantidade de nós gerados da árvore de “branch and bound” foi muito grande, excedendo a quantidade de memória disponível da máquina utilizada para os testes. No texto da dissertação apresentamos também um estudo da complexidade do problema, um algoritmo para calcular uma decomposição em árvore ótima de um grafo cordal, além das várias heurísticas para o cálculo de limites superiores e inferiores existentes. Além disso, implementamos e testamos as heurísticas de limite superior que utilizam rotulação e uma heurística GRASP, tendo sido o primeiro estudo de uma aplicação da meta-heurística GRASP para o problema de decomposição em árvore.

DIAS, Fábio Carlos Sousa. Problema de Árvore Geradora Mínima com Restrição de Grau Mínima e Centrais e Terminais Fixos. 2014. 132 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:49:19Z No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa (jairo@ufc.br) on 2016-07-14T23:17:13Z (GMT) No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) / Made available in DSpace on 2016-07-14T23:17:13Z (GMT). No. of bitstreams: 1 2014_tese_fcsdias.pdf: 835073 bytes, checksum: 7c80afdea29a07604c4e791a92383590 (MD5) Previous issue date: 2014 / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Benders’s Decomposition. We propose a new general heuristic that combines ingredients from the Benders’s decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Árvore Geradora Mínima com Restrição de Grau Mínimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma árvore geradora mínima de um grafo onde cada vértice ou é folha da árvore ou satisfaz uma restrição de grau mínimo. Os vértices folhas são chamados terminais e os demais são os centrais. Definimos e estudamos uma variação desse problema, que denotamos MDF-MST, onde os terminais e centrais são definidos a priori. Mostramos que o problema é NP-Difícil e está na Classe FPT, parametrizado pelo número de centrais. Identificamos também casos onde o problema torna-se polinomial. Propomos várias formulações de programação inteira para o problema e comparamos teórica e computacionalmente a qualidade do limite inferior gerado por suas relaxações lineares. Propomos e testamos uma relaxação lagrangeana para o problema, que usamos também para definir heurísticas lagrangenas. Definimos heurísticas gulosas, uma busca VND e uma heurística VNS. Apresentamos uma decomposição de Benders. Propomos uma nova heurística geral que combina ingredientes da decomposição de Benders com método de subgradientes, a qual denominamos Heurística de Subgradientes. Aplicamos tal heurística ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiência computacional dos algoritmos propostos, especialmente a relaxação lagrangeana, é competitiva com a do CPLEX, e superior em vários casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este último onde a restrição sobre os centrais é de grau máximo). Quando comparamos os resultados computacionais com a literatura.

VIANA, Luiz Alberto do Carmo. Árvore geradora com dependências mínima. 2016. 69 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T12:32:49Z No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T17:45:27Z (GMT) No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Made available in DSpace on 2016-09-27T17:45:27Z (GMT). No. of bitstreams: 1 2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) Previous issue date: 2016 / We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of “some”, “exactly one”or “all”dependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported. / Introduzimos o problema de Árvore Geradora com Dependências Mínima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vértices são as arestas de G e cujos arcos definem dependências entre tais arestas. O problema consiste em encontrar, dentre as árvores geradoras do grafo G(V,E) que satisfaçam as restrições de dependência impostas pelo digrafo de entrada D(E,A), uma que tenha custo mínimo, segundo a ponderação w das arestas de G. As restrições de dependência exigem que uma aresta e de G só pode fazer parte de uma solução se for uma fonte em D ou se fizer parte da solução alguma outra aresta é tal que o arco (e′, e) esteja em D. Provamos que decidir se há solução viável para AGDM(G,D,w) é um problema NP-completo, mesmo quando G é um cacto cordal e D é a união de arborescências de altura no máximo 2. Sua NP-completude também é mostrada ainda que G seja bipartido, as restrições de dependência ocorram apenas entre arestas adjacentes de G e formem arborescências de altura no máximo 2. Resultados idênticos são obtidos para as variantes do problema onde, nas restrições de dependência, substitui-se o requisito “alguma” por “exatamente uma” ou “toda”. Para resolver o problema, apresentamos algumas formulações de programação inteira e desigualdades válidas. Propomos uma estratégia para reduzir a dimensão do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instâncias geradas aleatoriamente. Resultados computacionais são reportados.

SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 71 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:42:38Z No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:43:21Z (GMT) No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-05-20T19:43:21Z (GMT). No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.

Submitted by Elizabete Silva (elizabete.silva@ufes.br) on 2015-07-31T18:26:48Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Potencialidades dos extrativos do cerne da madeira de teca como.pdf: 3369575 bytes, checksum: 6dafcc265dc67983b60f55856bd4ac14 (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-08-13T19:41:58Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Potencialidades dos extrativos do cerne da madeira de teca como.pdf: 3369575 bytes, checksum: 6dafcc265dc67983b60f55856bd4ac14 (MD5) / Made available in DSpace on 2015-08-13T19:41:58Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Potencialidades dos extrativos do cerne da madeira de teca como.pdf: 3369575 bytes, checksum: 6dafcc265dc67983b60f55856bd4ac14 (MD5) Previous issue date: 2014-11 / Este estudo teve como objetivo avaliar o potencial preservativo dos extrativos do cerne da madeira de teca (Tectona grandis) e a capacidade dos mesmos na mudança de coloração de madeiras claras. Para tanto, os resíduos gerados no processamento mecânico do cerne da madeira de teca com 20 anos de idade foram coletados e utilizados para realização de extrações. Para avaliar a influência dos extrativos de teca na cor e resistência natural da madeira foi utilizado o alburno da madeira de teca com 10 anos, além da madeira de Pinus sp., em função de ser uma madeira de coloração clara e baixa resistência natural. Foram realizadas extrações em água quente e etanol absoluto. Para determinação da concentração das soluções de tratamento foi realizado um ensaio de toxidez ao fungo Postia placenta. Após definida a concentração, as soluções extraídas foram preparadas para a impregnação. Além disto, foi utilizada uma terceira solução, composta pela combinação das soluções extraídas em água quente e etanol absoluto. Para cada solução testada foi realizado o tratamento pelo método de célula-cheia (Bethell). Para testar a eficiência das soluções preparadas com extrativos de teca, foram realizados leituras colorimétricas e ensaios biológicos com fungos e térmitas xilófagos. A combinação dos extrativos testados promoveu um escurecimento e reduziu a desuniformidade da cor, fazendo com que as madeiras tratadas se aproximassem mais da cor da madeira de cerne do que das amostras sem tratamento das respectivas espécies. A solução de extrativos obtida em etanol absoluto e a combinação dos extrativos obtidos em água quente e etanol absoluto promoveram os melhores resultados na resistência da madeira tratada contra fungos e térmitas xilófagos, alterando significativamente a classe de resistência das respectivas espécies tratadas. / This study aimed to evaluate the preservative potential of the heartwood extractives from teak (Tectona grandis) and the capacity of the same in the color change of light woods. For both, the waste generated in mechanical processing of the teak heartwood with 20 years old were collected and used for performing extractions. To evaluate the influence of teak heartwood extractives in the color and natural resistance of timber, were used the sapwood of teak wood with 10 years and the wood of Pinus sp., due to being a light colored wood and with low natural resistance to wood-destroying organisms. Extractions were performed in hot water and absolute ethanol. To determine the concentration of treatment solutions, a toxicity test to fungus Postia placenta was performed. After set the concentration, the extracted solutions were prepared for impregnation. Furthermore, it was used a third solution, composed by mixing of extracted solutions in hot water and absolute ethanol. The treatment by the method of cell-full (Bethell) was performed for each treatment solution. To test the efficiency of the solutions prepared with teak heartwood extractives, colorimetric analyses and biological assays with fungi and termites were carried out. The combination of the tested extractives promoted a darkening and reduced the disparity of color, making the treated wood closer to the heartwood color than the untreated samples of the respective species. The extractive solution obtained in absolute ethanol and the combination of the extractives obtained in hot water and absolute ethanol provided the best results in the resistance of treated wood against fungi and termites, significantly changing the biological resistance class of the respective treated species.

Made available in DSpace on 2014-06-11T19:33:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-09-25Bitstream added on 2014-06-13T20:05:54Z : No. of bitstreams: 1 lobao_devp_dr_jabo.pdf: 1139868 bytes, checksum: daf9edb278eaab2a86d9576a18660b2e (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Ceplac / A Floresta Atlântica na Região Cacaueira da Bahia tem os mais significativos remanescentes florestais em áreas agricultáveis. Deve-se isso, ao plantio tradicional do cacaueiro sob o dossel da floresta que, aprimorado ao longo de 250 anos, resultou no sistema agrossilvicultural cacau-cabruca. Este trabalho objetivou descrever a estrutura fitossociológica da vegetação arbórea em três áreas de cacau-cabruca e dois fragmentos florestais remanescentes, com ênfase na conservação de espécies. O estudo foi desenvolvido em cinco áreas, três com cacau-cabruca nos municípios de Ibirapitanga, Piraí do Norte e Ubatã, e duas, em fragmentos florestais inseridos no agroecossistema cacaueiro, nos municípios de Itapé e Jussari. O método de amostragem usado foi o de quadrantes, e o critério de inclusão foi diâmetro à altura do peito (DAP) 15 cm. Na análise da estrutura, foram avaliados os descritores usuais de fitossociologia. No cacau-cabruca, inventariaram-se 101 espécies em 36 famílias; 10 espécies apresentaram ocorrência comum. As áreas apresentaram baixa similaridade entre si. Os índices de diversidade (H’) foram 3,3 para Ibirapitanga, 3,2 para Piraí do Norte e 4,0 para Ubatã. Todas as áreas estudadas apresentaram alta dominância total (DoA) e densidade total acima do que a CEPLAC recomenda. Nos fragmentos florestais, foram inventariados 328 indivíduos, distribuídos entre 76 táxons, em 29 famílias botânicas. Dessas, 19 espécies apresentaram ocorrência comum às duas comunidades. A similaridade entre os fragmentos foi J’ = 33%. Quanto à diversidade, em Itapé, o H’ foi 3,16 e em Jussari, 3,77. O cacau-cabruca conservou remanescentes da Floresta Atlântica, tanto fragmentos florestais como indivíduos arbóreos, bem como, exemplares significativos de espécies arbóreas de diferentes estádios da sucessão, espécies raras e nobres de valor comercial... / The Atlantic Forest biome in the Bahia Cocoa Region has the most significant forest remanescents in agricultural areas. For that reason, the traditional cocoa planting under the forest canopy, which has been improved along 250 years, resulted in the agrossilvicultural cacau-cabruca system. This work describes the phytosociological structure of the arboreal vegetation in three cacaucabruca areas and two forest fragment-remanescents, with emphasis in species conservation. The study was developed in five areas, three with cocoa-cabruca in Ibirapitanga, Piraí do Norte and Ubatã municipalities, and two in forest fragments inserted in the cocoa agroecosystems of Itapé and Jussari. The sampling method used was quadrant and the inclusion criterion was chest height diameter (CHD) 15 cm. In the structure analysis the usual phytosociological descriptors were evaluated. In the cacau-cabruca 101 species in 36 families were inventoried, and nine of them showed common occurrence. The areas presented low similarity. The diversity indexes (H') were 3,3 for Ibirapitanga, 3,2 for Piraí do Norte and 4,0 for Ubatã. All areas studied showed high total dominance (DoA) and total density above the one recommended by the CEPLAC. In the forest fragments 328 individuals were inventoried, distributed among 76 taxons, in 29 botanical families. From these, 19 species presented common occurrence to both communities. The similarity between the fragments was J' = 33%. As for diversity, in Itapé H' was 3,16 and in Jussari 3,77. Cacau-cabruca conserved remanescents of the Atlantic Forest, either as fragments or shade arboreal individuals, as well as significant arboreal species at different succesional stages, rare and noble species of commercial value such as Caesalpinia echinata (pau-brasil), among others, in abundance, density and dominance.

Made available in DSpace on 2016-06-02T19:29:53Z (GMT). No. of bitstreams: 1 TeseAP.pdf: 966317 bytes, checksum: af2bf5e89cca6e2763b5a0709d74d8e4 (MD5) Previous issue date: 2002-10-11 / Universidade Federal de Sao Carlos / This work explores the use of models in landscape analysis. Classification tree models were employed in the identification of potential sites of species occurrence in the Ecological Station of Jataí and Experimental Station of Luiz Antônio, and the mathematical graph was employed in the analyses of a fragmented landscape located in the Northeast region of São Paulo State. The classification tree models used data on primate species occurrence and on environmental variables represented as digital maps in a Geographic Information System. The prediction rules generated by the classification models were projected back on the landscape, locating other places that have the same combination of environmental conditions as those found where the species were firstly observed. By representing the landscape as a mathematical graph, it was possible to simulate the removal of functional connections between habitat patches and the loss of habitat due to land use changes. Habitat patches were classified according to their contribution to species recruitment and landscape connectivity. Although it is considered that additional biological information should be incorporated to the analyses the results of this work may constitute useful guides to prospective field surveys. / O presente trabalho explora a utilização de modelos para a análise da paisagem. Modelos de classificação por árvore são empregados no contexto da identificação de áreas de ocorrência potencial de espécies na Estação Ecológica de Jataí e na Estação Experimental de Luíz Antônio e o grafo matemático é utilizado como um modelo para representação e análise da paisagem da região Nordeste do Estado de São Paulo. Para o desenvolvimento dos modelos de classificação por árvore foram utilizados dados sobre a localização de espécies de primatas e sobre algumas variáveis ambientais amostradas de um banco de dados em um sistema de informações geográficas. O mapeamento dos resultados dos modelos de classificação por árvore permitiu localizar na paisagem, outros locais com a mesma combinação de condições em que as espécies foram observadas. A utilização do grafo matemático como um modelo para a representação da paisagem possibilitou a simulação da remoção de ligações funcionais entre manchas de hábitat e a perda e ganho de hábitat, identificando as ligações e manchas que oferecem maior contribuição para o recrutamento de indivíduos e para a conectividade da paisagem. Embora seja necessária a incorporação de mais informações biológicas para o desenvolvimento de modelos mais satisfatórios, os resultados deste trabalho poderão subsidiar trabalhos de campo direcionando a amostragem da paisagem.

Made available in DSpace on 2015-05-08T14:59:31Z (GMT). No. of bitstreams: 1 parte1.pdf: 1887121 bytes, checksum: 87cf54641c539882362cc0f679d7c951 (MD5) Previous issue date: 2011-04-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Machine tools play a key role in modern industrial production; therefore the technological development of machine tool industry has grown over the past decades. High Speed Machining (HSM) is widely used for machining complex and free form surfaces with high geometrical and dimensional accuracy. The spindle is one of the main items of a machine tool. Thus, it becomes necessary to know the influence levels of the main internal sources of heat in a machine tool. These sources basically derive from: transmission of electric engines; friction in drives and gear boxes; machining process (cutting, chip, workpiece); friction in bearings and guides. The dimensional and geometric accuracy of machined parts depends mainly on the performance of the spindle. To admit the idea of a holistic model, and then propose a possible optimization for a high-accuracy machining it is necessary to study and investigate the mechanical and thermal behaviour of the spindle. For that reason, this paper presents an analysis, based on the finite element method, of the mechanical and thermal displacements, as well as a determination of the critical speed of the spindle of the machine tool at high cutting speed. / As máquinas-ferramenta desempenham um papel fundamental nas produções industriais modernas, com isso o avanço tecnológico das indústrias das máquinas-ferramenta vem crescendo ao longo das últimas décadas. A usinagem com Alta Velocidade de corte HSM é largamente utilizada para usinagem de superfícies complexas e de forma livre com alta exatidão geométrica e dimensional. O eixo-árvore é um dos principais elementos de uma máquina-ferramenta. Então, se torna necessário conhecer o grau de influências das principais fontes internas de calor numa máquina-ferramenta. Estas provêm basicamente: Das transmissões dos motores elétricos; Dos atritos nos acionamentos e caixas de engrenagens; Do processo de usinagem (ação de corte, cavacos, peça); Dos atritos nos mancais e guias. A exatidão dimensional e geométrica das peças usinadas dependem principalmente da performance do eixo-árvore. Para que seja admitida a idéia de um modelo holístico, e então, propor uma possível otimização para uma usinagem de alta exatidão é necessário o estudo e a investigação do comportamento mecânico e térmico do eixo-árvore. Por isso, neste trabalho é apresentada a análise, baseada no método dos elementos finitos dos deslocamentos mecânicos e térmicos, bem como, a determinação da velocidade crítica do eixo-árvore da máquina-ferramenta em alta velocidade de corte (HSM).