Orientador: Candido Ferreira Xavier de Mendonça Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-11-01T12:49:48Z (GMT). No. of bitstreams: 1 Xavier_EricoFabricio_M.pdf: 2893754 bytes, checksum: 024785fd687ba8f119cb99c3faa86797 (MD5) Previous issue date: 1999 / Resumo: O splitting number de um grafo G consiste no número mínimo de operações de quebra de vértice que devem ser realizadas em G para produzir um grafo planar, onde uma operação de quebra de vértice em um determinado vértice u significa substituir algumas das arestas ( u, v) por arestas (u', v), onde u' é um novo vértice. O skewness de G é o número mínimo de arestas que devem ser removidas de G para torná-Io planar. O vertex deletion number de G é o menor inteiro k tal que existe um subgrafo induzido planar de G obtido através da remoção de k vértices de G.Neste trabalho, apr~sentamos valores exatos para o splitting number, o skewness e o vertex deletion number dos grafos Cn x Cm, onde Cn é o circuito simples com n vértices, e para o splitting number e o vertex deletion number de uma triangulação dos grafos Cn x Cm / Abstract: The splíttíng number of a graph G is the minimum number of splitting steps needed to turn G into a planar graph; where each step replaces some of the edges (u, v) incident to a selected vertex u by edges (u', v), where u' is a new vertex. The skewness of G is the minimum number of edges that need to be deleted from G to produce a planar graph. The vertex deletíon number of G is the smallest integer k such that there is a planar induced subgraph of G obtained by the removal of k vertices of G. In this work, we show exact values for the splíttíng number, skewness and vertex deletíon number of the graphs Cn x Cm, where Cn is the simple circuit on n vertices, and for the splíttíng number and vertex deletíon number of a triangulation of Cn x Cm / Mestrado / Mestre em Ciência da Computação

Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. / Made available in DSpace on 2012-10-16T22:12:42Z (GMT). No. of bitstreams: 0Bitstream added on 2016-01-08T17:34:02Z : No. of bitstreams: 1 138806.pdf: 2193196 bytes, checksum: 2514d856661c8ebb3a9df581d2d6a7d3 (MD5)

A presente tese de doutorado trata de problemas de coloração de hipergrafos. Mais precisamente, nós trabalhamos com o chamado Problema de Erdos e Rothschild no caso de colorações arco- ris de hipergrafos. Nossas contribuições envolvem os hipergrafos plano de Fano (hipergrafo 3-uniforme com 7 v ertices e 7 hiperarestas onde todo par de v ertices e coberto) e K(k) +1 (hipergrafo obtido do grafo K+1 onde cada aresta recebe k 2 novos v ertices). Para F 2 fFano;K(k) +1g, encontramos o hipergrafo k-uniforme com o maior n umero de r-colorações de hiperarestas que não contêm cópia de F com a propriedade de que todas as suas hiperarestas têm cores distintas. Como ferramentas para tais demonstrações, obtivemos resultados mais precisos de estabilidade para K(k) +1 e outros hipergrafos ou famílias de hipergrafos, bem como um resultados de estabilidade para colorações para uma classe de hipergrafos lineares, que contém Fano e K(k)+1. Para os resultados de estabilidade para colorações utilizamos o Lema de Regularidade, introduzido por Szemeredi no contexto de grafos, e o Lema de Imersão, ambos considerados mais tarde para hipergrafos lineares por Kohayakawa, Nagle, Rodl e Schacht. / In this thesis we consider problems about colorings of hypergraphs. More precisely, we deal with the so-called Erd}os and Rothschild Problem in the case of rainbow colorings of hypergraphs. Our contributions involve the hypergraphs Fano plane (the 3-uniform hypergraph on 7 vertices and 7 hyperedges where every pair of vertices is covered) and K(k) `+1 (the hypergraph obtained from K`+1 where each edge is enlarged by k 2 new vertices). For F 2 fFano;K(k) `+1g, we obtained the k-uniform hypergraph with the largest number of r-colorings of hyperedgees not containing a copy of F with the property that all hyperedges are colored di erently. As a tool for such proofs, we obtained a sharper stability result for K(k) `+1 and other hypergraphs and families of hypergrahs. We also obtained a color stability result for a class of linear hypergraphs, which contains Fano and K(k) `+1. For these color stability result we used the Regularity Lemma, originally stated by Szemer edi for graphs, and the Embedding Lemma, both considered later for linear hypergraphs by Kohayakawa, Nagle, Rodl and Schacht

Dissertação (mestrado profissional) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática, Florianópolis, 2015. / Made available in DSpace on 2016-04-19T04:14:50Z (GMT). No. of bitstreams: 1 337662.pdf: 4681558 bytes, checksum: 8891d71ebb8eadcc421b3f7727965490 (MD5) Previous issue date: 2015 / O objetivo deste trabalho é o estudo de grafos aplicado à coloração de vértices e arestas. Para tal, faremos uma breve apresentação sobre conceitos básicos de grafos, bem como a importância de suas aplicações.Buscamos aqui a resolução de problemas envolvendo coloração e sua possível aplicação matemática na educação básica.<br> / Abstract : The objective of this work is the study of graphs applied to colouring of vertex and edges. To do this, we will give a brief presentation about basics concepts of graphs, as well as the importance of its applications.We seek here the solution of the problems involving colouring and its possible mathematical application in basic education.

No description available.

A presente tese de doutorado trata de problemas de coloração de hipergrafos. Mais precisamente, nós trabalhamos com o chamado Problema de Erdos e Rothschild no caso de colorações arco- ris de hipergrafos. Nossas contribuições envolvem os hipergrafos plano de Fano (hipergrafo 3-uniforme com 7 v ertices e 7 hiperarestas onde todo par de v ertices e coberto) e K(k) +1 (hipergrafo obtido do grafo K+1 onde cada aresta recebe k 2 novos v ertices). Para F 2 fFano;K(k) +1g, encontramos o hipergrafo k-uniforme com o maior n umero de r-colorações de hiperarestas que não contêm cópia de F com a propriedade de que todas as suas hiperarestas têm cores distintas. Como ferramentas para tais demonstrações, obtivemos resultados mais precisos de estabilidade para K(k) +1 e outros hipergrafos ou famílias de hipergrafos, bem como um resultados de estabilidade para colorações para uma classe de hipergrafos lineares, que contém Fano e K(k)+1. Para os resultados de estabilidade para colorações utilizamos o Lema de Regularidade, introduzido por Szemeredi no contexto de grafos, e o Lema de Imersão, ambos considerados mais tarde para hipergrafos lineares por Kohayakawa, Nagle, Rodl e Schacht. / In this thesis we consider problems about colorings of hypergraphs. More precisely, we deal with the so-called Erd}os and Rothschild Problem in the case of rainbow colorings of hypergraphs. Our contributions involve the hypergraphs Fano plane (the 3-uniform hypergraph on 7 vertices and 7 hyperedges where every pair of vertices is covered) and K(k) `+1 (the hypergraph obtained from K`+1 where each edge is enlarged by k 2 new vertices). For F 2 fFano;K(k) `+1g, we obtained the k-uniform hypergraph with the largest number of r-colorings of hyperedgees not containing a copy of F with the property that all hyperedges are colored di erently. As a tool for such proofs, we obtained a sharper stability result for K(k) `+1 and other hypergraphs and families of hypergrahs. We also obtained a color stability result for a class of linear hypergraphs, which contains Fano and K(k) `+1. For these color stability result we used the Regularity Lemma, originally stated by Szemer edi for graphs, and the Embedding Lemma, both considered later for linear hypergraphs by Kohayakawa, Nagle, Rodl and Schacht

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2013. / Submitted by Luiza Silva Almeida (luizaalmeida@bce.unb.br) on 2013-07-17T20:41:38Z No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5) / Approved for entry into archive by Leandro Silva Borges(leandroborges@bce.unb.br) on 2013-07-17T21:22:19Z (GMT) No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5) / Made available in DSpace on 2013-07-17T21:22:19Z (GMT). No. of bitstreams: 1 2013_AllanKardecMessiasdaSilva.pdf: 811006 bytes, checksum: d150f5332d05a0c2ccff34412c37b29f (MD5) / O presente trabalho é uma introdução ao estudo de um grafo chamado Degree Graph. Este grafo é associado aos graus dos caracteres de um grupo nito no seguinte modo: os vértices são os primos que dividem os graus dos caracteres irredutíveis e dois vértices p; q são conexos com uma aresta se o grupo possui um caráter irredutível cujo grau é divisível pelo produto pq. O Degree Graph foi estudado inicialmente em grupos solúveis e apenas a pouco teve seus estudos avançados para grupos não solúveis. Donald L. White completou o estudo para grupos simples em 2009 com o artigo `Degree Graphs of Simple Groups', onde ele descreve para todos os grupos nitos simples os correspondentes Degree Graphs. Vamos neste trabalho mostrar estes estudos para todos os grupos alternados, e alguns grupos simples lineares, simpléticos e unitários. O principal resultado que vamos ilustrar em detalhes é o fato que, se n 9, o Degree Graph do grupo alternado An é um grafo completo. Este resultado usa uma conjectura de Alvis, provada por Barry e Ward. _______________________________________________________________________________________ ABSTRACT / The present work is an introduction to the study of a graph called Degree Graph. This graph is associated to the degrees of the characters of a nite group in the following way: the vertices are the primes that divide the degrees of the irreducible characters and two vertices p; q are connected with an edge if the group has an irreducible character whose degree is divisible the product pq. O Degree Graph was initially studied for soluble groups and only recently also for non soluble groups. In 2009 Donald L. White completed the study for simple groups in the paper `Degree Graph of Simple Groups', where he describes for all nite simple groups the corresponding Degree Graphs. In this work, we will illustrate these studies for all alternating groups and some simple linear, symplectic and unitary groups. The main result that we will describe in detail is the fact that if n 9, the Degree Graph of the alternating group An is a complete graph. This result makes use of a conjecture of Alvis, proved by Barry Ward.

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T04:18:30Z (GMT). No. of bitstreams: 1 PerezLozada_LuisArturo_M.pdf: 2819086 bytes, checksum: a6afd3f6ffb1a048ced4a84733ff7e66 (MD5) Previous issue date: 1996 / Resumo: Uma dique de um grafo G é um conjunto de vértices que induz um subgrafo completo maximal de G. O grafo dique K(G) de um grafo G é o grafo interseção das diques de G. Indutivamente define-se o i-ésimo grafo dique iterado de G como Ki(G) = K(Ki-l(G)). Apresenta-se de maneira organizada uma compilação de pesquisas realizadas nos últimos anos a respeito de diversos tópicos na dasse dos grafos dique, entre eles: o estudo das propriedades dos grafos dique de conhecidas dasses de grafos; a convergência; divergência e diâmetro dos grafos clique-iterados / Abstract: A clique of a graph G is a set of vertices that induce a maximal complete subgraph of G. The dique graph K (G) of a graph G is the intersection graph of the diques of G. Inductively we denote the ith iterated dique graph of G by Ki(G) = X(Ki-l(G)). We wiil present in an organized way a compilation of investigations made in the last years with respect to the several topics on this class of graphs, such as: the study of proprieties of dique graphs of weil-known class of graphs; convergence; divergence and diameters of iterated dique graphs / Mestrado / Mestre em Ciência da Computação

Orientador: Claudina Izepe Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-26T16:57:25Z (GMT). No. of bitstreams: 1 Carvalho_MarceloDantasde_M.pdf: 1298387 bytes, checksum: 14167c08257e5465066717df5f9963e6 (MD5) Previous issue date: 2000 / Resumo: 0 objetivo principal deste trabalho é apresentar uma classificação para os dígrafos semicompletos hamiltonianos, extendendo os resultados obtidos para os torneios. Para isso utilizamos da teoria da homotopia regular de grafos de Davide C. Demaria, apresentando resultados sobre torneios simplemente desconexos, a caracterização de torneios por 3-ciclos e o conceito de ciclo conado e não-conado para dígrafos, introduzido por Kiihl e Tironi. Com a noção de ciclo minimal e característico para dígrafo uma classificação para os dígrafos semicompletos hamiltonianos surge então naturalmente. Esses resultados, quando encontrados para torneios, proporcionaram a obtenção de uma classe de torneios reconstrutíveis (torneios normais) e pesquisa nesse sentido deve ser efetuada para dígrafos. Apresentamos em apêndice a matriz de um dígrafo, os torneios de moon, normais e, brevemente, o problema da reconstrução de grafos / Abstract: The main target in this work is to present a classification for the hamiltonian semicomplete digraphs, extending the results previously obtained for the tournaments. In this way we apply the regular homotopy of finite directed graphs theory developed by Davide G. Demaria, presenting results on simply disconnected tournaments, on the caracterization of tournaments by 3-cicles and the concept of coned and non-coned cicle for digraphs, introduced by Kiihl and Tironi. With the notion of minimal and caracteristic cicle we naturally get a classification of the semicomplete hamiltonian digraphs. These results, when used for tournaments led to a new class of reconstructible ones (named normal) and future research on the extension of these results for digraphs in general seems to be interesting. We present in appendixes the array of a digraph, the tournaments of Moon, Normal and, briefly, the reconstruction problem for graphs / Mestrado / Mestre em Matemática

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T09:25:12Z (GMT). No. of bitstreams: 1 Braga_MariliaDiasVieira_M.pdf: 1562326 bytes, checksum: e2bde728b7016815f56abc118722d3d4 (MD5) Previous issue date: 2000 / Resumo: Este trabalho está relacionado à Biologia Computacional, uma área da Ciência da Computação cuja existência é motivada pela busca de métodos computacionais que resolvam ou ajudem a resolver problemas de origem biológica. Esta ciência tem sido largamente utilizada no âmbito da genética, contribuindo essencialmente no seqüenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma família de problemas denominada Minimum Contig Problems (MCP) [4], que é um modelo teórico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhança com um problema de grafos denominado Cobertura de Vértices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentação de provas formais da NP-dificuldade dos problemas de MCP. A partir daí, complementamos o nosso trabalho propondo um algoritmo de aproximação para instâncias restritas de cada problema de MCP. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação