Nesta tese apresentamos solu c~oes de dois problemas de colora c~ao de grafos. Para as solu c~oes de ambos problemas, utilizamos ferramentas probabil sticas. Em um desses problemas de colora c~ao, consideramos o espa co de probabilidade Gk n;p dos grafos aleat orios coloridos. Provamos que, para cada k 3, o limiar para a propriedade de que um grafo aleat orio colorido cont em uma arvore geradora propriamente colorida e log n=n, que e precisamente o limiar para a conexidade. Para resolver esse problema, utilizamos uma cota para a cardinalidade de um emparelhamento m aximo em Gn;(1+ ) log n=n, provada por Frieze em 1986. Embora tal cota seja su ciente para resolver esse problema, investigamos o problema da cardinalidade de um emparelhamento m aximo no grafo aleat orio Gn;(1+ ) log n=n e obtivemos um resultado mais preciso. O outro problema de colora c~ao e um problema determin stico, por em, para a solu c~ao deste, utilizamos um resultado de enumera c~ao de grafos cuja demonstra c~ao apresenta argumentos probabil sticos. Dados r t 3 e ` 1, procuramos por grafos com n v ertices que admitem o maior n umero de r-colora c~oes tais que no m aximo t1 cores aparecem pelo menos ` vezes em arestas incidentes a cada v ertice, isto e, r-colora c~oes livres de St;`-arco- ris (estrelas com t` arestas coloridas com t cores distintas tal que cada cor e atribu da a exatamente ` arestas). Para n grande, mostramos que, o grafo completo Kn e o unico grafo extremal. / In this thesis, we obtain solutions for two graph coloring problems, both of which rely on probabilistic tools. In one of these coloring problems, we consider the probability space Gk n;p of edge-colored random graphs. We prove that, for all xed k 3, the threshold for the property that an edge-colored random graph contains a properly colored spanning tree is log n=n, precisely the threshold for connectivity. To solve this problem, we used a bound for the size of a maximum matching in Gn;(1+ ) log n=n, proved by Frieze in 1986. Although such bound is su cient to solve this problem, we investigated the problem of the size of a maximum matching in the random graph Gn;(1+ ) log n=n and we obtained a more precise result. Even though the other coloring problem is deterministic, we used a graph enumeration whose proof is probabilistic. Given r t 3 and ` 1, we look for n-vertex graphs that admit the maximum number of r-edge-colorings such that at most t 1 colors appear at least ` times in edges incident with each vertex, that is, r-edge-colorings avoiding rainbow-St;` (stars with t` edges colored with t distinct colors such that each color is assign to exactly ` edges). For large n, we show that, the complete graph Kn is always the unique extremal graph.

Cografos representam uma classe de grafos que pode ser de nida e caracterizada de diversas maneiras. A estrutura de relacionamento entre seus vértices, permite que um cografo possa ser construído de forma recursiva a partir de um único vértice. Neste trabalho estudamos algumas caracterizações clássicas de cografos, dentre as quais abordamos: livre de P4, formas recursivas utilizando união, complemento e junção, diâmetro de todo subgrafo induzido 2, vértices irmãos, propriedade CK(clique Kernel), e formas recusivas utilizando duplicação e coduplica ção de vértices. A principal contribuição foi relacionar algumas das diferentes formas de caracterizações de um cografo com a de nição de grafo complementar redutível. Apresentamos algumas formas de representar cografos, que podem ser encontradas em diversos trabalhos, como forma normalizada, coárvore e matriz de adjacência. Estudamos um algoritmo que auxilia na localização de autovalores em cografos, como contribuição apresentamos os detalhes teóricos sobre seu funcionamento através da Lei na Inércia de Sylvester, e da obtenção de matrizes congruentes à matriz A+xI, onde A é a matriz de adjacência de um cografo, x é um número real e I é a matriz identidade de mesma ordem de A. Com este algoritmo, estudamos alguns resultados clássicos sobre o espectro de um cografo, que são: a multiplicidade dos autovalores 1 e 0, e que um cografo não possui autovalores no intervalo (1; 0). Além disso, apresentaremos algumas aplicações para obter famílias de cografos com a mesma energia de grafos completos Kn. / Cographs are a class of graphs that can be de ned and characterized in several ways. The structure given in terms of vertices enable a cograph to be built by recursive form from a single vertice. In this work, we study some classical characterizations of cographs, among which: P4 - free, recursive form with union, complement and join, diameter of all induced subgraph connected 2, siblings vertices, property CK(cliqueKernel), and recursive form by duplication and coduplication of vertices. As main contribution, we establish a relationship between some characterizations of cographs, which is a complement reducible graph. We also show some ways to make a mathematical representation that can be found in various works, as normalized form, cotree and adjacency matrix. We study an algorithm that can help us to nd eigenvalues in cographs, as an additional contribution we provide the theoretical details about its operation through the Sylvester Law of Inertia and how to get congruent matrices from A+xI, where A is the adjacency matrix of a cograph, x is a real number and I is a identity matrix with the same order of A. Using the algorithm, we study some classical results about spectral set of a cograph, as the multiplicity of eigenvalues 1 and 0, and the statement of no cographs have eigenvalues in (1; 0). In addition, we show some applications to nd cograph families with the same energy of complete graphs Kn.

Resumo não disponível

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

Atualmente, o uso de sistemas de informação está amplamente difundido, sendo que praticamente todas as áreas de negócio têm necessidade de tais sistemas. Estes sistemas são formados por funcionalidades que implementam regras do negócio e persistem os dados em bases de dados. Os usuários podem utilizar estes sistemas através das interfaces de usuário, que são as unidades onde estão implementadas as funcionalidades, que estão estruturadas por meio de menus. Através destes menus, o usuário pode navegar e selecionar aquela interface de usuário que contenha a funcionalidade que ele está buscando. A motivação para este trabalho veio da grande dificuldade que é manter sistemas, em uma linha de produção de software, íntegros do ponto de vista das interfaces do usuário. A cada sistema novo ou manutenção em sistema já existente, garantir que as interfaces do usuário tenham os mesmos padrões de aparência e comportamento, exige um grande esforço de verificação e validação, o que pode ser minimizado por um processo onde a estrutura das interfaces do usuário esteja em um modelo baseado em padrões. Sempre que uma aparência ou comportamento for alterado para um padrão, ele pode ser replicado em todos os sistemas modelados, permitindo, assim, não somente uma melhoria na produtividade como também um ganho em qualidade. O objetivo principal deste trabalho é definir e validar um metamodelo que permita modelar a estrutura destas interfaces de usuário de um sistema de informação. Para construir este metamodelo, foi escolhida uma estrutura de grafos. Esta escolha foi devido à naturalidade com que uma interface de usuário pode ser representada como um vértice e os relacionamentos por arestas. Inicialmente foram identificados e normalizados os padrões das interfaces de usuário de uma grande amostra de sistemas de informação. O metamodelo foi construído com base nestes padrões. Utilizando este metamodelo, foi possível construir modelos completos para um sistema hipotético e para três sistemas reais, comprovando que ele pode ser usado na modelagem das interfaces de usuário de outros sistemas similares.

Este trabalho vem a dar mais uma contribuição para o já consagrado uso de teoria das categorias para descrever e estabelecer relações entre formalismos diferentes. Esta dissertação tem como objeti principal estabelecer uma relação entre os formalismos de reded de Petri e gramáticas de grafos a partir de suas já difundidas represetações categóricas, utilizando, para isto, a linguagem da teoria das categorias. / This works comes to be one more contribution to the well diffused use of the category theory to describe and stablish relationships between different formalisms. The main goal of this dissertation is to stablish a relationship between the Petri nets and graph grammar fomalisms, using category theory and their categorical representations found in the literature.

A Teoria Espectral de Grafos tem como objetivo descobrir propriedades de um grafo G através da análise do espectro de uma matriz associada ao grafo. Nesta dissertação estudamos a matriz de adjacência A(G), a matriz laplaciana L(G) e a matriz laplaciana sem sinal Q(G). Para cada uma dessas matrizes estudamos o comportamento dos autovalores no que diz respeito `a integralidade. Mais especificamente, estudamos os grafos integrais, os grafos Q-integrais e os grafos L-integrais, que são os grafos que têm espectro inteiro em relação `as matrizes A(G), Q(G) e L(G), respectivamente. Estudamos a variação espectral inteira via adição de aresta para a matriz laplaciana. Vimos que se os autovalores da matriz laplaciana variam de maneira inteira, então um dos autovalores aumenta em duas unidades ou dois dos autovalores aumentam em uma unidade cada um. Esses dois tipos de variações são conhecidas como variação espectral inteira em um lugar e dois lugares [26, 33], respectivamente. Essas duas variações foram cruciais para estabelecermos uma estratégia para construção de grafos L-integrais por adição de arestas. Além disso, estudamos os grafos construtivelmente laplaciano integrais [28], que são um subconjunto dos grafos L-integrais. Caracterizamos este subconjunto através dos subgrafos induzidos e mostramos uma técnica alternativa para calcular o seu espectro. Estudamos também algumas famílias com infinitos grafos integrais e grafos Q-integrais construídos através do join de grafos regulares [12, 15, 24]. / The spectral graph theory aims to discover properties of a graph G by analyzing the spectrum of a matrix associated to the graph. In this thesis, we study the adjacency matrix A(G), Laplacian matrix L(G) and the signless Laplacian matrix Q(G). For each of these matrices we study the behavior of eigenvalues with respect to integrality. More specifically, we study integral graphs, Q-integral graphs and L-integral graphs, which are graphs that have integral spectrum with regard to the matrices A(G), Q(G) and L(G), respectively. We study the spectral integral variation for the Laplacian matrix under the addition of an edge. We have seen that if the eigenvalues of the Laplacian matrix change by integer quantities, then one of the eigenvalues increases by two units or two of the eigenvalues increase by one unit each. These two types of variation are known as spectral integral variation in one place and two places [26, 33], respectively. These two variations were crucial to establish a strategy for building L-integral graphs by adding edges. Moreover, we studied the class of constructably Laplacian integral graphs, that are a subset of L-integral graphs. We characterize this subset through vertex-induced subgraphs and show an alternative technique for calculating their spectrum. We also study some families with infinite integral graphs and Q-integral graphs built through the join of regular graphs [12, 15, 24].

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.

Os sistemas computacionais estão tomando proporções cada vez maiores envolvendo situações bastante complexas, onde muitas vezes erros são inaceitáveis, como em sistemas bancários, sistemas de controle de tráfego aéreo, etc... Para obter software confiável e com desempenho aceitável, pode-se aliar técnicas de desenvolvimento formal de software a técnicas de simulação de sistemas. O ambiente PLATUS reúne essas duas áreas: modelos de simulação são descritos usando gramáticas de grafos uma linguagem de especificação formal. Gramáticas de grafos são uma generalização de gramáticas de Chomsky, substituindo strings por grafos. Neste trabalho, serão tratadas gramáticas de grafos baseados em objetos, um modelo onde vértices e arcos são tipados, e as especificações são modulares (a especificação de um sistema consiste em várias gramáticas de grafos combinadas). Assim, o modelo de um sistema pode ser descrito de forma precisa, e a linguagem de especificação é bastante abstrata e expressiva. Num ambiente de simulação a questão da recuperação de dados merece uma atenção especial, uma vez que a eficiência do simulador está diretamente ligada a agilidade na obtenção das informações. Neste trabalho, o objetivo principal é definir uma representação para gramáticas de grafos que facilite o armazenamento, a recuperação e análise das estruturas identificadas no ambiente PLATUS, ou seja, gramáticas de grafos baseadas em objetos. São definidas também funções que implementam os procedimentos necessários, para a recuperação de dados durante a simulação. A eficiência dessas funções é demonstrada através do cálculo de sua ordem de complexidade. As estruturas são validadas através da implementação de um protótipo de banco de dados.

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.