QUINTINO, Arthur Lima. Vértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticos. 2016. 59 f. Dissertação (Mestrado em Matemática)- Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:21:47Z No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:22:11Z (GMT) No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Made available in DSpace on 2016-08-01T13:22:11Z (GMT). No. of bitstreams: 1 2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) Previous issue date: 2016 / In 1989, Gyárfás conjectured that, for every natural r, r monochromatic paths are suficient to vertex-partition any r-edge-coloured complete graph. Later, Erdos, Gyárfás and Pyber proposed a stronger version of this conjecture, in which r monochromatic cycles are wanted instead of r monochromatic paths. In this dissertation, we present many problems and results related to such conjectures, including problems where the graph to be coloured is not a complete graph, but a complete multipartite graph. We also highlight how the Szemeredi's regularity lemma may be applied in this context. Furthermore, we prove two original results. In the first one, we extend some arguments introduced by Gyárfás and Lehel in order to obtain an alternative, simpler, proof for a result due to Pokrovskiy. Whereas in the second, we show that 4 monochromatic cycles are suficient to vertex-partition any 2-edge-coloured balanced complete bipartite graph, thereby reducing the number of 12 monochromatic cycles that had been previously obtained by Schaudt and Stein. Lastly, we discuss some strategies that may be followed in future works in order to reduce the quantity of monochromatic cycles needed in this case from 4 to 3, which is the minimum possible for such case. / Em 1989, Gyárfás conjecturou que, para todo r natural, r caminhos monocromáticos são suficientes para vértice-particionar qualquer grafo completo r-aresta-colorido. Mais tarde, Erdos, Gyárfás e Pyber propuseram uma versão mais forte dessa conjectura, na qual r ciclos monocromáticos são procurados em vez de r caminhos monocromáticos. Nesta dissertação, apresentamos vários problemas e resultados relacionados com tais conjecturas, incluindo problemas onde o grafo a ser colorido não é um grafo completo, mas sim um grafo multipartido completo. Destacamos ainda como o Lema da regularidade de Szemerédi pode ser aplicado nesse contexto. Al em disso, provamos dois resultados originais. No primeiro deles, estendemos alguns argumentos introduzidos por Gyárfás e Lehel afim de obtermos uma prova alternativa, mais simples, para um resultado devido a Pokrovskiy. Enquanto que no segundo, mostramos que 4 ciclos monocromáticos são suficientes para vértice-particionar qualquer grafo bipartido completo balanceado 2-aresta-colorido, reduzindo assim o número de 12 ciclos monocromáticos que havia sido obtido anteriormente por Schaudt e Stein. Por fim, discutimos algumas estratégias que podem ser seguidas em trabalhos futuros a fim de reduzir a quantidade de ciclos monocromáticos necessários nesse caso de 4 para 3, o que e o mínimo possível para tal caso.

Made available in DSpace on 2016-06-02T20:28:22Z (GMT). No. of bitstreams: 1 DissBMRS.pdf: 1154928 bytes, checksum: 924e6444b56d0ec4a8d35192450c515c (MD5) Previous issue date: 2007-03-20 / Financiadora de Estudos e Projetos / In 1961, Santaló[21] suggested that, considering the family of the convex bodies in R2, it was found a complete system of inequalities for each pair and each triple of the functions area, perimeter, diameter, inradius, circunradius and minimal width. In this work, we applied the technique developed by Blaschke[2] to solve all problems suggested by Santaló, those are solved until now. / Santaló propôs (em [21]) que, fixada a família C dos corpos convexos de R2, fosse encontrado um sistema completo de desigualdades para cada par e cada tripla das funções área, perímetro, diâmetro, inraio, circunraio e largura mínima. Neste trabalho, estudamos a aplicação da técnica desenvolvida por Blaschke na resolução dos problemas propostos por Santaló que, até hoje, já se encontram solucionados.

Estudamos sistemas de passeios aleatórios sobre os vértices de um grafo completo. Inicialmente há uma partícula em cada vértice do grafo das quais somente uma está ativa, as outras estão inativas. A partícula ativa realiza um passeio aleatório simples a tempo discreto com tempo de vida que depende do passado do processo, movendo-se ao longo de elos. Quando uma partícula ativa encontra uma inativa, esta se ativa; quando salta sobre um vértice já visitado, morre. O objetivo desta dissertação é estudar a cobertura do grafo completo, ou seja, a proporção de vértices visitados ao fim do processo, quando o número $n$ de vértices tende ao infinito. Analisamos as equações de campo médio para o processo descrito acima, comparando os seus resultados com os do modelo aleatório. Aqui, os resultados do campo médio parecem reproduzir os do modelo aleatório. Depois, apresentamos um estudo similar entre o modelo estocástico e as equações de campo médio para o caso em que cada partícula possui 2 vidas. Finalmente, observamos a cobertura do grafo completo para as equações de campo médio quando o número de vidas por partículas é maior que dois. / We study random walks systems on complete graphs. Initially there is a particle at each vertex of the graph; only one is active and the other are inactive. An active particle performs a discrete-time simple random walk with lifetime depending on the past of the process moving along edges. When an active particle hits an inactive one, the latter is activated. When it jumps on a vertex which has been visited before it dies. The goal of this work is to study the coverage of the complete graph, that is, the proportion of visited vertices at the end of the process, when the number of vertices goes to infinity. We analyze the mean field equations to the process cited above, comparing their results with the ones of the random model. Here the results of the mean field approach seem to reproduce the ones of the random model. After we present a similar study between the stochastic model and mean field approximation to the case that each particle has 2 lifes. Finally we observe the coverage of the complete graph to the mean-field equations when the number of lifes by particle is bigger than two.

Estudamos sistemas de passeios aleatórios sobre os vértices de um grafo completo. Inicialmente há uma partícula em cada vértice do grafo das quais somente uma está ativa, as outras estão inativas. A partícula ativa realiza um passeio aleatório simples a tempo discreto com tempo de vida que depende do passado do processo, movendo-se ao longo de elos. Quando uma partícula ativa encontra uma inativa, esta se ativa; quando salta sobre um vértice já visitado, morre. O objetivo desta dissertação é estudar a cobertura do grafo completo, ou seja, a proporção de vértices visitados ao fim do processo, quando o número $n$ de vértices tende ao infinito. Analisamos as equações de campo médio para o processo descrito acima, comparando os seus resultados com os do modelo aleatório. Aqui, os resultados do campo médio parecem reproduzir os do modelo aleatório. Depois, apresentamos um estudo similar entre o modelo estocástico e as equações de campo médio para o caso em que cada partícula possui 2 vidas. Finalmente, observamos a cobertura do grafo completo para as equações de campo médio quando o número de vidas por partículas é maior que dois. / We study random walks systems on complete graphs. Initially there is a particle at each vertex of the graph; only one is active and the other are inactive. An active particle performs a discrete-time simple random walk with lifetime depending on the past of the process moving along edges. When an active particle hits an inactive one, the latter is activated. When it jumps on a vertex which has been visited before it dies. The goal of this work is to study the coverage of the complete graph, that is, the proportion of visited vertices at the end of the process, when the number of vertices goes to infinity. We analyze the mean field equations to the process cited above, comparing their results with the ones of the random model. Here the results of the mean field approach seem to reproduce the ones of the random model. After we present a similar study between the stochastic model and mean field approximation to the case that each particle has 2 lifes. Finally we observe the coverage of the complete graph to the mean-field equations when the number of lifes by particle is bigger than two.

O Planejamento Energético tradicional geralmente privilegia os custos econômicos dos recursos energéticos, relegando ao segundo plano questões políticas, sociais e ambientais. Este trabalho pretende estimular a mudança desta abordagem através da proposição de um modelo de caracterização de recursos energéticos integrando todas essas quatro dimensões. São dois seus objetivos: o fornecimento de uma metodologia para avaliar o custo global dos recursos energéticos e de outra para estimar o potencial de tais recursos. Para facilitar o processo de avaliação, o modelo sugere o uso da ACC - Avaliação de Custos Completos, a qual permite a análise qualitativa e quantitativa de custos, reduzindo a necessidade de dados quantitativos, limitados em certos casos. Ilustra-se a aplicação do modelo com um exemplo de caracterização dos recursos na região de Araçatuba, localizada no Oeste Paulista. Os resultados revelam que, quando considerados os custos globais, a adoção de recursos renováveis apresenta grande competitividade, ao contrário de outros que, apesar de serem economicamente atraentes, não apresentam custos globais aceitáveis. / The Traditional Energy Planning usually favors technical-economic costs, relegating political, social and environmental issues to a less important level of analyses. This work tries to encourage a change in such approach by elaborating a model of energy resources characterization integrating all four dimensions - environmental, political, social and economic. The model aims at two objectives: providing a method of assessing the global cost of energy resources and estimating its potential considering the limitations provided by these dimensions. The integration of distinct elements constitutes a complex and tricky activity that can result in inaccurate results if not taken carefully. To minimize this complexity, the Model suggests the use of the Full Cost Accounting - FCA - method, which allows the consideration of quantitative and qualitative costs, reducing the demand for quantitative data, limited in some cases. The Model has been applied in the characterization of the region of Araçatuba, located in the western part of the state of São Paulo, the most populated state in Brazil. The results reveal that the adoption of renewable sources is quite attractive, especially when global costs are taken into account. On the other hand, other resources don\'t present acceptable global costs despite being economically attractive.

O Planejamento Energético tradicional geralmente privilegia os custos econômicos dos recursos energéticos, relegando ao segundo plano questões políticas, sociais e ambientais. Este trabalho pretende estimular a mudança desta abordagem através da proposição de um modelo de caracterização de recursos energéticos integrando todas essas quatro dimensões. São dois seus objetivos: o fornecimento de uma metodologia para avaliar o custo global dos recursos energéticos e de outra para estimar o potencial de tais recursos. Para facilitar o processo de avaliação, o modelo sugere o uso da ACC - Avaliação de Custos Completos, a qual permite a análise qualitativa e quantitativa de custos, reduzindo a necessidade de dados quantitativos, limitados em certos casos. Ilustra-se a aplicação do modelo com um exemplo de caracterização dos recursos na região de Araçatuba, localizada no Oeste Paulista. Os resultados revelam que, quando considerados os custos globais, a adoção de recursos renováveis apresenta grande competitividade, ao contrário de outros que, apesar de serem economicamente atraentes, não apresentam custos globais aceitáveis. / The Traditional Energy Planning usually favors technical-economic costs, relegating political, social and environmental issues to a less important level of analyses. This work tries to encourage a change in such approach by elaborating a model of energy resources characterization integrating all four dimensions - environmental, political, social and economic. The model aims at two objectives: providing a method of assessing the global cost of energy resources and estimating its potential considering the limitations provided by these dimensions. The integration of distinct elements constitutes a complex and tricky activity that can result in inaccurate results if not taken carefully. To minimize this complexity, the Model suggests the use of the Full Cost Accounting - FCA - method, which allows the consideration of quantitative and qualitative costs, reducing the demand for quantitative data, limited in some cases. The Model has been applied in the characterization of the region of Araçatuba, located in the western part of the state of São Paulo, the most populated state in Brazil. The results reveal that the adoption of renewable sources is quite attractive, especially when global costs are taken into account. On the other hand, other resources don\'t present acceptable global costs despite being economically attractive.

[EN] In this research, a new model of computing is presented, within the framework of natural computing and computer models inspired by biology: Networks of Genetic Processors (NGP). This new model is based on the one hand, by the family of networks of bio-inspired processors, specifically Networks of Evolutionary Processors (NEP) and Networks of Splicing Processors (NSP), and on the other hand by Genetic Algorithms. We can define the new model as a network of biologically-inspired processors where operations used by processors are crossover and mutation. One of the major interests studying the NGP is the computational power of the operations of crossover and mutation acting together. The NEP is a complete model that uses operations of symbol mutation: insertion, substitution and deletion, the NSP is a complete model that uses splicing operations, but the NEP is no longer a complete model using only substitution operations, as it happens to the NSP if we restrict the context of its splicing rules to the empty context. The study of the new model presented here responds to what happens when we put together in a single model the substitution rules from the NEP (called mutation rules) and the splicing rules with empty context from the NSP (called crossover rules). When we work with networks of biologically-inspired processors there are two basic types of networks, accepting networks and generating networks. These types of networks are mainly used to work at a theoretical level or to solve decision problems. To work on a more practical level such as solving optimization problems, we propose a new type of network, Networks of Genetic processors as Parallel Genetic Algorithms, inspired by the Parallel Genetic Algorithms. In this work we prove the computational completeness of our new model by showing that it is equivalent to the Turing machine. We prove the computational completeness of Parallel Genetic Algorithms by using this result and the similarity between the NGP and Parallel Genetic Algorithms. Moreover, we propose a characterization of the Chomsky hierarchy by using the NGP. Here, we simulate every grammar in the language classes of the Chomsky's hierarchy by using a NGP with an small number of processors required for each simulation. Hence, it gives an appreciable idea of the descriptional complexity of the different families of languages. Finally, in this work there is an experimental study of the behavior of the model for the resolution of some practical problems. First, we design and implement a simulator that allows the execution of networks of Genetic Processors in any of its three defined types: accepting networks, generating networks or as Parallel Genetic Algorithms. This allows us to test the model with different optimization problems. Then, we make a study to see if the new model could solve NP problems in polynomial time. We use the decision problem of Hamiltonian cycle in a graph. Finally, we test the simulator with two optimization problems showing a good computational behavior. The problems are the Multidimensional Knapsack problem and the Traveling Salesman problem. / [ES] Desde la rama de la biocomputación, la computación con modelos inspirados en la biología, esta investigación presenta un nuevo modelo de computación: las Redes de Procesadores Genéticos (NGP). Este nuevo modelo parte, por un lado, de la familia de modelos de redes de procesadores, más concretamente de las Redes de Procesadores Evolutivos (NEP) y las Redes de Procesadores de Splicing (NSP), y por otra parte se inspira en los Algoritmos Genéticos. Así pues, se puede definir de manera informal el nuevo modelo como una red de procesadores bioinspirados donde las operaciones utilizadas por los procesadores son operaciones de cruce y mutación. Uno de los mayores intereses del estudio de las NGP es la capacidad conjunta de las operaciones de cruce y mutación, las NEP son un modelo completo que utiliza operaciones de evolución, es decir, inserción, substitución y borrado, las NSP son un modelo completo que utiliza operaciones de splicing, pero las NEP dejan de ser un modelo completo al usar sólo operaciones de substitución, al igual que le pasa a las NSP si restringimos el contexto de sus reglas de splicing a vacío. El estudio del nuevo modelo aquí presentado da respuesta a qué es lo que pasa cuando juntamos en un sólo modelo las operaciones de sustitución de las NEP (llamadas reglas de mutación) y las operaciones de splicing con contexto vacío de las NSP (llamadas reglas de cruce). Cuando se trabaja con redes de procesadores bioinspirados se definen principalmente dos tipos de redes, las redes aceptoras y las redes generadoras. Estos tipos de redes sirven principalmente para trabajar a un nivel teórico o para resolver problemas de decisión. Para trabajar a un nivel más práctico como por ejemplo con problemas de optimización, se propone un nuevo tipo de red, las Redes de Procesadores Genéticos como Algoritmos Genéticos Paralelos, llamadas así por inspirarse en los Algoritmos Genéticos Paralelos. A nivel teórico, se ha podido demostrar la completitud computacional del modelo, con lo que su potencia de computación se sitúa al mismo nivel que el de las maquinas de Turing. A raíz de este resultado y dada la gran similitud entre las NGP y los Algoritmos Genéticos Paralelos, en este trabajo se demuestra que éstos también son un modelo de computación completo. Por otra parte se ha podido realizar una caracterización de la jerarquía de Chomsky utilizando las NGP, para ello se simula cada una de las gramáticas que definen las cuatro familias de lenguajes de dicha jerarquía observando el mínimo número de procesadores necesarios para cada simulación, lo cual da una idea apreciable de la diferencia de complejidad entre las diferentes familias. No falta en este trabajo un estudio de la parte más práctica del modelo con la realización de algunas tareas. Primero se ha diseñado e implementado un simulador que permite la ejecución de Redes de Procesadores Genéticos en cualquiera de sus tres vertientes aquí definidas, como aceptoras, como generadoras o como Algoritmos Genéticos Paralelos, esto permite realizar pruebas con diferentes problemas de optimización. A continuación se ha realizado un estudio para ver si el nuevo modelo era capaz de resolver problemas NP en tiempo polinómico, para ello se ha trabajado con el problema de ver si existe algún ciclo Hamiltoniano en un grafo. Finalmente se ha probado el simulador con dos problemas de optimización en los que se ha detectado un buen comportamiento del mismo, los problemas utilizados han sido el problema de la mochila multidimensional y el problema del viajante de comercio. / [CA] Des de la branca de la biocomputació (la computació amb models inspirats amb la biologia) aquesta investigació presenta un nou model de computació: Les Xarxes de Processadors Genètics (NGP). Aquest nou model ve, d'una banda, de la família de models de xarxes de processadors, més concretament de les Xarxes de Processadors Evolutius (NEP) i de les Xarxes de Processadors de Splicing (NSP) i d'altra banda s'inspira als Algoritmes Genètics. Així doncs, es pot definir d'una manera informal el nou model com una xarxa de processadors bioinspirats on les operacions utilitzades per els processadors són operacions de creuament i mutació. Un dels elements més interessants de l'estudi de les NGP és la capacitat conjunta de les operacions de creuament i mutació, les NEP són un model complet que utilitza operacions evolutives, és a dir, insercions, substitucions i esborrats, les NSP són un model complet que utilitza operacions de splicing, però les NEP deixen de ser un model complet al gastar sols operacions de substitució, al igual que li passa a les NSP si restringim el context de les seues regles de splicing a buit. L'estudi del nou model presentat ací dóna resposta a què és el que passa quan ajuntem a un sol model les operacions de substitució de les NEP (anomenades regles de mutació) i les operacions de splicing amb context buit de les NSP (anomenades regles de creuament). Quan es treballa amb xarxes de processadors bioinspirats es defineixen principalment dos tipus de xarxes, les xarxes aceptores i les xarxes generadores. Aquests tipus de xarxes s'utilitzen principalment per a treballar a nivell teòric o per a resoldre problemes de decisió. Per treballar a un nivell més pràctic, com per exemple amb problemes d'optimització, es proposa un nou tipus de xarxa, les Xarxes de Processadors Genètics com Algoritmes Genètics Paral·lels, anomenats així per estar inspirats en els Algoritmes Genètics Paral·lels. A nivell teòric, s'ha pogut demostrar la completitut computacional del model, amb el que la seua potència computacional es situa al mateix nivell que les màquines de Turing. Degut a aquest resultat i donada la gran similitud entre les NGP i els Algoritmes genètics Paral·lels, en aquest treball es demostra que aquestos també són un model computacional complet. D'altra banda, s'ha pogut realitzar una caracterització de la jerarquia de Chomsky utilitzant les NGP, aquest procés es realitza simulant cada una de les gramàtiques que defineixen les quatre famílies de llenguatges d'aquesta jerarquia observant el mínim nombre de processadors necessaris per a cada simulació, el que ens dóna una idea apreciable de la diferència de complexitat entre les diferents famílies. No falta a aquest treball un estudi de la part més pràctica del model com la realització d'algunes tasques. Primer s'ha dissenyat i implementat un simulador que permet l'execució de Xarxes de Processadors Genètics a qualsevol de les seues tres varietats ací definides, com aceptores, com a generadores o com a Algoritmes Genètics Paral·lels, amb el que podem realitzar proves amb diferents problemes d'optimització. A continuació s'ha realitzat un estudi per vore si el nou model era capaç de resoldre problemes NP en un temps polinòmic, estudi que hem realitzat utilitzant el problema de saber si existeix algun cicle Hamiltonià en un graf. Finalment s'ha provat el simulador amb dos problemes d'optimització als que s'ha comprovat que té un bon comportament, els problemes utilitzats són el problema de la motxilla multidimensional i el problema del viatjant de comerç. / Campos Frances, M. (2016). REDES DE PROCESADORES GENÉTICOS [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/61452

De forma geral, as fases iniciais dos programas de melhoramento se caracterizam pelo tamanho populacional elevado e a natureza subjetiva da seleção. Por serem consideradas etapas de grande importância e de alto grau de complexidade, torna-se necessário a utilização de metodologias que, de forma eficiente, auxiliem os melhoristas a obterem resultados mais precisos, otimizando tempo e recursos para liberação de novas cultivares. Assim, este trabalho teve como objetivo avaliar o nível de ganho genético que um programa de melhoramento de cana-de-açúcar pode ter, adotando diferentes estratégias de seleção, em fases iniciais do melhoramento. Para tanto, dois experimentos referentes à primeira e à segunda fase de seleção do Programa de Melhoramento Genético da Cana-de-açúcar da RIDESA/UFSCar, foram instalados. Na primeira etapa, identificou-se o método de seleção entre e dentro de família (BLUPi, BLUPis e BLUPseq) com maior potencial a ser aplicado na população base do experimento, utilizando a abordagem de modelos mistos. Posteriormente, praticou-se seleção, incluindo o método massal e aleatória. Na segunda etapa, a população experimental foi constituída pelos clones previamente selecionados na etapa anterior, através das diferentes estratégias de seleção. Os valores genotípicos dos indivíduos foram preditos, e então, classificados de acordo com o caráter de interesse econômico. Na primeira etapa, dentre os métodos de seleção entre e dentro de família, o que apresentou maior ganho de seleção predito (12,7%), para toneladas de Pol por hectare (TPH), foi o procedimento BLUPseq. O método BLUPis apresentou alta correlação com o método de seleção via BLUPseq e se mostrou bastante eficiente, uma vez que, o número de indivíduos a serem selecionados em cada família é determinado de forma dinâmica, assim como a intensidade de seleção em cada repetição. Por outro lado, o método BLUPi apresentou-se impraticável, uma vez que as avaliações fenotípicas devem ser realizadas em nível de indivíduo, o que demanda muito tempo e mão de obra, além do que, identificou-se tendência em selecionar indivíduos das extremidades das parcelas. De acordo com os resultados obtidos no experimento - segunda etapa, devido a baixa variância genética (CVg ≤ 15) entre as famílias que constituíram a população base do experimento, o método de seleção de família via BLUPseq foi equivalente ao método de seleção massal. Por outro lado, se ênfase for dada na escolha de genitores em etapas de hibridação para a ampliação da base genética, o método de seleção de família pode ser recomendado. / Overall, the early stages of breeding programs are characterized by high population size and the subjective nature of the selection. Considered as a stage of great importance and with high degree of complexity, it becomes necessary to use methodologies that efficiently assist plant breeders to obtain more accurate results, optimizing time and resources for releasing new cultivars. Thus, the aim of this study was to evaluate the genetic gain level that a sugarcane breeding program may have, adopting different selection strategies at early breeding stages. Therefore, two experiments concerning the first and the second selection stages of the Sugarcane Breeding Program of RIDESA/UFSCar, were installed. In the first step, the method of selection between and within families (BLUPi, BLUPis and BLUPseq) with greatest potential to be applied into the population of the experiment were identified, through mixed models approach. Later, the selection was practiced including the mass and random selection methods. In the second stage, the experimental population consisted of clones previously selected in the previous stage through the different selection strategies. The genotypic values of individuals were predicted, and then classified according to the character of economic interest. In the first stage, from the selection methods between and within families, the BLUPseq procedure was the one with highest predicted selection gain (12.7 %) for tons of Pol per hectare (TPH). The BLUPis procedure showed high correlation with BLUPseq procedure and was quite efficient, since the number of individuals to be selected in each family is determined dynamically, as well as the selection intensity in each repetition. Moreover, the BLUPi method proved to be impracticable, since the phenotypic evaluations must be performed at the individual level, which requires long time and labor force, in addition to that, it was identified trend in selecting individuals from the plots edges. According to the results of the second stage experiment, due to low genetic variance (CVg ≤ 15) among the families which composed the experimental population base, the family selection via BLUPseq was equivalent to mass selection. On the other hand, if emphasis is given on the choice of parents in hybridization steps to broaden the genetic basis, the family selection method can be recommended.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-08-12T15:13:32Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) / Made available in DSpace on 2014-08-12T15:13:32Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) Previous issue date: 2009-03-12 / Given a graph G = (V;E) and a set of vertices D V, a vertice v 2 V is dominated by D if jN[v] \ Dj 1. When jN(v) \ Dj = 1 for all v 2 V, G is efficiently dominable. A generalization of this concept is called efficient multiple domination, which requires all vertices must be dominated by a set D V exactly k times. The aim of this dissertation is to study these topics, describing the theoretical knowledge needed for advanced researches. For this reason, many of the theorems and its proofs are detailed. Furthermore, some results on the efficient multiple domination are presented, including bounds for the size of efficient k-dominating sets, the complement and iterated line graphs of efficiently (r + 1)-dominable r-regular graphs and a N P-completeness proof for the efficient multiple domination problem in arbitrary graphs. It is expected that this work contribute to the development of future researches on the efficient domination and in the resolution of some open problems. / Dado um grafo G = (V;E) e um subconjunto de vértices D V, define-se D como um conjunto dominante de G se todo vértice v 2 V que não estiver incluído no conjunto D for adjacente a pelo menos um vértice de D. Na situação em que, para todo v 2 V, jN[v]\Dj = 1, diz-se que o grafo G é eficientemente dominado. Uma generalização desse conceito consiste na múltipla dominação eficiente, em que é requerido que todo vértice do grafo seja dominado exatamente k vezes. O objetivo deste trabalho é realizar um estudo exploratório sobre esses temas, de modo a reunir o conhecimento teórico requerido para pesquisas avançadas. Para isso, buscou-se a apresentação e o detalhamento das demonstrações dos teoremas estudados. Além disso, foram fornecidos alguns resultados sobre a múltipla dominação eficiente no que se refere aos limites para o tamanho de um conjunto k-dominante eficiente, à relação da k-dominação eficiente entre grafos regulares, seu complemento e seus grafos linha iterados, bem como à caracterização da N P-completude para o problema da múltipla dominação eficiente em grafos arbitrários. Espera-se que esta dissertação forneça subsídios teóricos para estudos futuros voltados à dominação eficiente, bem como à resolução de algumas questões em aberto.

Submitted by IZABEL CHRISTINA GAVA DE SOUZA null (izabelsouza@suzano.com.br) on 2016-09-30T11:03:11Z No. of bitstreams: 1 Tese_Izabel_2016_1.pdf: 1921899 bytes, checksum: cce906c3ffd78242151254d344282fb0 (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-09-30T13:09:58Z (GMT) No. of bitstreams: 1 souza_icg_dr_bot.pdf: 1921899 bytes, checksum: cce906c3ffd78242151254d344282fb0 (MD5) / Made available in DSpace on 2016-09-30T13:09:59Z (GMT). No. of bitstreams: 1 souza_icg_dr_bot.pdf: 1921899 bytes, checksum: cce906c3ffd78242151254d344282fb0 (MD5) Previous issue date: 2016-07-29 / Este trabalho teve como objetivo propor um novo método de melhoramento para Eucalyptus visando obter materiais genéticos para plantio operacional, por meio dos seguintes estudos: a) avaliar o ganho em produtividade volumétrica de madeira na seleção aplicada numa população clonal de Eucalyptus grandis oriunda da mistura de clones selecionados em progênies de polinização controlada (irmãos completos); b) avaliar a variabilidade genética a partir de marcadores moleculares microssatélites na população clonal selecionada, quando submetida a diferentes condições ambientais e níveis de seleção. Com as sementes obtidas no cruzamento controlado foi instalado um plantio experimental na Fazenda Ribeirão Grande (município de Salesópolis/SP) de propriedade da Suzano Papel e Celulose no ano de 2001. Aos 6 anos de idade foi realizada a seleção de árvores superiores (clones) com base nos caracteres silviculturais e densidade básica da madeira. Foram selecionados 57 clones (irmãos completos), os quais foram propagados vegetativamente, misturados para a formação do minijardim clonal e posterior produção de mudas para plantio operacional na empresa. Este material genético foi recomendado para plantio em 2010. Para este trabalho foram selecionadas três áreas de plantio operacional desse material genético, denominado aqui população clonal inicial com idade de 3,3 a 3,5 anos. Em cada local foram estabelecidas 3 parcelas de 100 árvores e realizada a avaliação silvicultural das árvores. Com os dados de DAP foi feita a ordenação dos valores (maior para o menor) e selecionadas as 40 árvores com maiores valores de DAP e boa forma do tronco, e as 15 árvores com menores valores de DAP totalizando 405 árvores. O perfil genético por meio de marcadores moleculares microssatélites foi realizado para as árvores selecionadas, clones que formam a população clonal inicial e clones genitores. O Incremento Médio Anual com casca aos 7 anos de idade (IMA7; m3/ha/ano) foi estimado por parcela e níveis de seleção de 10%, 20%, 30% e 40%. Com o perfil genético das 40 árvores selecionadas por parcela obteve-se os clones presentes na seleção, como também, os clones presentes nas 15 árvores de comportamento silvicultural inferior. Os resultados mostram que o método de seleção e melhoramento em populações clonais de E. grandis é promissor, diminuindo o tempo de obtenção de materiais genéticos para plantio operacional. Os níveis de seleção de 30% e 40% são os mais indicados para conservar um bom número de clones e obter ganhos em produtividade em curto prazo. / The objective of this work was to propose a new method for breeding to Eucalyptus in order to obtain genetic material for commercial planting by the following studies: a) evaluate the gain, in wood volumetric productivity, in the selection applied to a clonal population of Eucalyptus grandis coming from a selected clonal mixture obtained in cross-pollinated progenies (full sibling); b) evaluate the genetic variability using microsatellite markers obtained in a selected clonal population when subjected to different environmental conditions and levels of selection. Using the seeds obtained in the hand pollination, an experimental plantation was established, in 2001, at the Ribeirão Grande Farm in the municipality of Salesópolis, State of São Paulo, Brazil, owned by Suzano Pulp and Paper. At the age of 6 years old, a selection of superior trees (clones) was carried out based on silvicultural traits and wood density. Fifty-seven clones (full-siblings) were selected, propagated using vegetative technique and used for mixed plantation in a clonal garden to subsequent production of seedlings for commercial planting. This genetic material (initial clonal population) was recommended for planting in 2010. For this study, three commercial areas planted with these genetic materials at ages ranging from 3.3 to 3.5 years old were selected. On each site, 3 plots of 100 trees were established and the silvicultural evaluation of trees was made. The trees were ordered using the diameter at breast height (DBH) data (highest to lowest) and the 40 trees with the highest DBH values and good shape of the trunk were selected, and the 15 trees with lower DBH values, totaling 360 trees. The genetic profile through microsatellite markers was conducted for selected trees, for clones that form the initial clonal population and for parental clones. The Annual Average Increase in shell to the 7 years old (IMA7; m3 / ha.year) was estimated per plot and 10, 20, 30 and 40% selection of levels. Throughout the genetic profile of the 40 selected trees per plot, the presented clones in the selection were obtained, but also, the clones present in 15 trees with lower silvicultural behavior. The results show that the method selection and improvement in clonal populations of E. grandis is promising, decreasing the time for obtaining genetic materials for commercial plantation. Check levels of 30 and 40% are the most suitable to preserve a good number of clones and to obtain short-term productivity gains.