LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom. / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O processo mais utilizado para a união de tubos de aço para o transporte de óleo e gás é a soldagem. Embora ainda se utilize a soldagem manual, a soldagem mecanizada e até mesmo a automatizada vem ganhando espaço. Assim, este trabalho comtempla a soldagem circunferencial em meia cana de tubos API 5L X65 de 8” de diâmetro nominal e 8,0 mm de espessura, junta de topo com chanfro estreito (abertura de 30°) e preparação em V, por meio de dispositivo de deslocamento (soldagem mecanizada) e com variação de parâmetros (soldagem automatizada). São apresentados os parâmetros de soldagem encontrados para a confecção da junta soldada em dois passes (um de raiz e outro de enchimento/acabamento). Os parâmetros selecionados para o passe de raiz foram retirados de um estudo anterior servindo também como forma de validação de resultados, ora obtidos na soldagem em chapas e, agora em tubos. Foram avaliados os processos GMAW com transferência metálica por curto-circuito em modo convencional e controlado (processos derivativos) utilizando fontes comerciais com diferentes tecnologias (RMD, STT e CMT). Logo após a determinação dos parâmetros de enchimento, foram realizados ensaios mecânicos voltados para sua validação (tração uniaxial, dobramento de face e raiz, nick break, impacto, dureza e macrografia,). Os resultados obtidos para o RMD e CMT foram adequados inicialmente em todos os ensaios e, em um, segundo momento foram também adequados para o STT. Entretanto, os ensaios realizados para processo convencional revelaram a existência de falta de fusão o que levou a necessidade de determinação de novos parâmetros de enchimento. Assim, foi projetado e construído um Sistema de Variação de Parâmetros para Soldagem Circunferencial (SVP) que permite a variação, em função da posição angular (inclinômetro), dos parâmetros mais adequados para cada uma das três posições angulares (plana, vertical e sobrecabeça). Para o processo convencional com variação de parâmetros foi possível obter ganhos em termos de tempo para execução da soldagem da ordem de 38% para a raiz e 30% para o enchimento. / Welding is one of the most employed process for joining steel pipes. Although, manual welding is still the most used one, mechanized version and even automatized one have increased its demand. Thus, this work deals with girth welding of API 5L X65 pipes with 8” of nominal diameter and 8.0 mm thickness, beveled with V-30º narrow gap. Torch is moved by a bug carrier (mechanized welding) and further the parameters are controlled as a function of angular position (automatized welding). Welding parameters are presented for filling the joint with two-passes (root and filling/capping passes). Parameters for the root pass were extracted from previous author´s work with weldments carried out in plates, but validated in this work for pipe welding. GMAW processes were assessed with short-circuit metal transfer in both conventional and derivative modes using different technologies (RMD, STT and CMT). After the parameter determination, mechanical testing was performed for welding qualification (uniaxial tension, face and root bending, nick break, Charpy V-notch impact, microhardness and macrograph). The initially obtained results for RMD and CMT were acceptable for all testing and, in a second moment, also for the STT. However, weld beads carried out by using the conventional process failed and revealed the existence of lack of fusion, which required further parametrization. Thus, a Parameter-Variation System for Girth Welding (SVP) was designed and built to allow varying the welding parameters as a function of angular position by using an inclinometer. The parameters were set for each of the three angular positions (flat, vertical downhill and overhead). By using such equipment and approach, the conventional process with parameter variation allowed reducing the welding time for joint accomplishment of the order of 38% for the root pass and 30% for the filling/capping pass. / Tese (Doutorado)

As recentes descobertas de petróleo e gás na camada do Pré-sal representam um enorme potencial exploratório no Brasil, entretanto, os desafios tecnológicos para a exploração desses recursos minerais são imensos e, consequentemente, têm motivado o desenvolvimento de estudos voltados a métodos e materiais eficientes para suas produções. Os tubos condutores de petróleo e gás são denominados de elevadores catenários ou do inglês \"risers\", e são elementos que necessariamente são soldados e possuem fundamental importância nessa cadeia produtiva, pois transportam petróleo e gás natural do fundo do mar à plataforma, estando sujeitos a carregamentos dinâmicos (fadiga) durante sua operação. Adicionalmente, um dos problemas centrais à produção de óleo e gás das reservas do Pré-Sal está diretamente associado a meios altamente corrosivos, tais como H2S e CO2. Uma forma mais barata de proteção dos tubos é a aplicação de uma camada de um material metálico resistente à corrosão na parte interna desses tubos (clad). Assim, a união entre esses tubos para formação dos \"risers\" deve ser realizada pelo emprego de soldas circunferenciais de ligas igualmente resistentes à corrosão. Nesse contexto, como os elementos soldados são considerados possuir defeitos do tipo trinca, para a garantia de sua integridade estrutural quando submetidos a carregamentos cíclicos, é necessário o conhecimento das taxas de propagação de trinca por fadiga da solda circunferencial. Assim, neste trabalho, foram realizados ensaios de propagação de trinca por fadiga na região da solda circunferencial de Inconel® 625 realizada em tubo de aço API 5L X65 cladeado, utilizando corpos de prova do tipo SEN(B) (Single Edge Notch Bending) com relações entre espessura e largura (B/W) iguais a 0,5, 1 e 2. O propósito central deste trabalho foi de obter a curva da taxa de propagação de trinca por fadiga (da/dN) versus a variação do fator de intensidade de tensão (ΔK) para o metal de solda por meio de ensaios normatizados, utilizando diferentes técnicas de acompanhamento e medição da trinca. A monitoração de crescimento da trinca foi feita por três técnicas: variação da flexibilidade elástica (VFE), queda de potencial elétrico (QPE) e análise de imagem (Ai). Os resultados mostraram que as diferentes relações B/W utilizadas no estudo não alteraram significantemente as taxas de propagação de trinca por fadiga, respeitado que a propagação aconteceu em condições de escoamento em pequena escala na frente da trinca. Os resultados de propagação de trinca por fadiga permitiram a obtenção das regiões I e II da curva da/dN versus ΔK para o metal de solda. O valor de ΔKlim obtido para o mesmo foi em torno de 11,8 MPa.m1/2 e os valores encontrados das constantes experimentais C e m da equação de Paris-Erdogan foram respectivamente iguais a 1,55 x10-10 [(mm/ciclo)/(MPa.m1/2)m] e 4,15. A propagação de trinca no metal de solda deu-se por deformação plástica, com a formação de estrias de fadiga. / Recent oil and gas discoveries in the Pre-Salt layer represent a huge exploration potential in Brazil, however, the technological challenges for the exploitation of these mineral resources are immense and therefore have motivated the development of studies looking for efficient methods and materials for their productions. The oil and gas pipellines, called risers, are elements that are necessarily welded and have fundamental importance in the production chain, since they transport oil and natural gas from the sea bed to the platforms and are subject to dynamic loads (fatigue) during operation. Additionally, one of the central problems in the production of oil and gas in the Pre-Salt reserves is directly associated with a highly corrosive media, such as H2S and CO2. A cheaper way to protect the pipelines from these medias is applying a protective layer of a corrosion resistant metal on the inner diameter of these pipes, creating a cladded pipe. Thus, a joining process of these pipes to form the risers must be carried out by the use of girth welds with a corrosion resistance material similar to the clad metal. As the welded structures are seen as potential location of \"crack like\" defects, to ensure the structural integrity of such component when subjected to repetitive loading conditions, it is necessary to know the fatigue crack growth rates for the girth weld. Therefore, in this work it was carried out fatigue crack propagation tests in the weld region of an API 5L X65 cladded pipe with Inconel® 625, girth welded using Inconel® 625 electrodes. From the welded region, Single Edge Notch Bending specimens, SEN(B), were removed with different thickness and width ratios (B/W= 0.5, 1, and 2). From the fatigue tests, the crack propagation rates (da/dN) as function of the variation of the stress intensity factor (ΔK), were determined for the weld metal, using different crack size measurement techniques: the elastic compliance (EC), electric potential drop (EPD) and image analysis (IA). The results showed that the different B/W ratios used in study did not modified significantly the fatigue crack growth rates, considering that crack propagation took place under small scale yielding conditions. The results of fatigue crack growth tests allowed to obtain the regions I and II of da/dN x ΔK curves for the weld metal. The ΔKth value obtained for the weld metal was around 11,8 MPa.m1/2 and the found values of the experimental constants C and m of Paris-Erdogan\'s equation were respectively equal to 1,55 x10-10 [(mm/cycle)/( MPa.m1/2)m] and 4.15. The micromechanism of fatigue crack growth took place by plastic deformation, with the formation of fatigue striations.

We implement a package for the construction of a new class of Low Density Parity Check (LDPC) codes based on a new random high girth graph construction technique, and study the performance of the codes so constructed on both the Additive White Gaussian Noise (AWGN) channel as well as the Binary Erasure Channel (BEC). Our codes are “near regular”, meaning thereby that the the left degree of any node in the Tanner graph constructed varies by at most 1 from the average left degree and so also the right degree. The simulations for rate half codes indicate that the codes perform better than both the regular Progressive Edge Growth (PEG) codes which are constructed using a similar random technique, as well as the MacKay random codes. For high rates the ARG (Almost Regular high Girth) codes perform better than the PEG codes at low to medium SNR’s but the PEG codes seem to do better at high SNR’s. We have tried to track both near codewords as well as small weight codewords for these codes to examine the performance at high rates. For the binary erasure channel the performance of the ARG codes is better than that of the PEG codes. We have also proposed a modification of the sum-product decoding algorithm, where a quantity called the “node credibility” is used to appropriately process messages to check nodes. This technique substantially reduces the error rates at signal to noise ratios of 2.5dB and beyond for the codes experimented on. The average number of iterations to achieve this improved performance is practically the same as that for the traditional sum-product algorithm.

No description available.

Low Density Parity Check (LDPC) codes are the parity check codes of long block length, whose parity check matrices have relatively few non-zero entries. To improve the performance at relatively short block lengths, LDPC codes are constructed by either pseudo-random or quasi-cyclic methods instead of random construction methods. In this thesis, pseudo-random code construction methods, the effects of closed loops and the graph connectivity on the performance of pseudo-random LDPC codes are investigated. Moreover, quasi-cyclic LDPC codes, which have encoding and storage advantages over pseudo-random LDPC codes, their construction methods and performances are reviewed. Finally, performance comparison between pseudo-random and quasi-cyclic LDPC codes is given for both regular and irregular cases.

Traditional solutions to information security in communication systems act in the application layer and are oblivious to the effects in the physical layer. Physical-layer security methods, of which information-theoretic security is a special case, try to extract security from the random effects in the physical layer. In information-theoretic security, there are two asymptotic notions of secrecy---weak and strong secrecy This dissertation investigates the problem of information-theoretic strong secrecy on the binary erasure wiretap channel (BEWC) with a specific focus on designing practical codes. The codes designed in this work are based on analysis and techniques from error-correcting codes. In particular, the dual codes of certain low-density parity-check (LDPC) codes are shown to achieve strong secrecy in a coset coding scheme. First, we analyze the asymptotic block-error rate of short-cycle-free LDPC codes when they are transmitted over a binary erasure channel (BEC) and decoded using the belief propagation (BP) decoder. Under certain conditions, we show that the asymptotic block-error rate falls according to an inverse square law in block length, which is shown to be a sufficient condition for the dual codes to achieve strong secrecy. Next, we construct large-girth LDPC codes using algorithms from graph theory and show that the asymptotic bit-error rate of these codes follow a sub-exponential decay as the block length increases, which is a sufficient condition for strong secrecy. The secrecy rates achieved by the duals of large-girth LDPC codes are shown to be an improvement over that of the duals of short-cycle-free LDPC codes.

Les standards consacrés à la conception des oléoducs se concentrent principalement sur les chargements opérationnels, tels que les pressions internes et externes, et les procédures d'analyse de défauts actuelles n'exploitent pas les capacités d'écrouissage du matériau. Pourtant, dans des conditions extrêmes, les oléoducs peuvent être soumis à des contraintes au-delà de la limite d'élasticité jusqu'à atteindre 2.5% de déformations plastiques. Ici, les procédures proposées par ExxonMobil et PRCI basées sur des critères en déformation sont présentées, et l'utilisation de l'éprouvette SENT (Single Edge Notched Tension) pour caractériser la ténacité est étudiée, en comparant les différentes procédures d'essais recommandées. Puis, une importante campagne expérimentale a été réalisée pour caractériser deux aciers pour oléoducs à température ambiante et à basses températures. Les comportements mécaniques des matériaux de base et d'apport ont été identifiés grâce à l'utilisation de l'analyse inverse, et il est montré que le modèle d'endommagement GTN permet de modéliser finement les essais sur éprouvettes de laboratoire. Enfin, deux essais sur structures (pression et flexion, puis pression et traction) ont été réalisés de manière à comparer les approches globales et le modèle d'endommagement GTN. Ce dernier démontre une bonne transférabilité de l'éprouvette vers la structure. / Pipeline design codes and standards traditionally focus on the operational loadings such as internal and external pressures that are likely to exist over the entire lifetime of the pipeline. Existing Engineering Critical Assessments are mostly based on stress considerations, where the design margin is given as a percentage of the yield strength. In extrem environments, pipelines may experience stresses beyond the yield and plastic deformations up to 2.5 %. In such conditions, strain-based design procedures apply. In this work, a literature review of the existing strain based methods is proposed, including ExxonMobil and PRCI multi-tier approaches. The use of the Single Edge Notched Tension (SENT) specimen to measure the material toughness is then studied, benchmarking the recommended testing procedures from literature. A comprehensive experimental campaign was carried out to fully characterize two actual line pipes at room and low temperatures. The mechanical behavior of parent and weld materials are identified using an inverse analysis, and GTN damage model is shown to allow accurate modeling of the laboratory testings. Finally, two full scale tests (pressure + bending or pressure + tension) were carried out to benchmark the global approaches and GTN damage model. The latter showed a very good transferability from specimens to the structure.

No description available.