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.

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.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar. / The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

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.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2016. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-07-21T17:21:02Z No. of bitstreams: 1 2016_GustavoMaiaQueirozdeMendonça.pdf: 16621580 bytes, checksum: fb2e7c4fe5521587dc6f85065ebcb929 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-08-18T18:40:35Z (GMT) No. of bitstreams: 1 2016_GustavoMaiaQueirozdeMendonça.pdf: 16621580 bytes, checksum: fb2e7c4fe5521587dc6f85065ebcb929 (MD5) / Made available in DSpace on 2016-08-18T18:40:35Z (GMT). No. of bitstreams: 1 2016_GustavoMaiaQueirozdeMendonça.pdf: 16621580 bytes, checksum: fb2e7c4fe5521587dc6f85065ebcb929 (MD5) / Na segmentação de objetos em vídeos por intermédio de um rastreamento quadro a quadro de regiões, a manutenção da coerência temporal depende diretamente da qualidade desse rastreamento ao longo dos quadros. Para esse fim, adaptou-se para o domínio dos superpixels processados como grafos de regiões, princípios de um extrator de características bastante difundido, o SIFT, que exibe grande eficiência na identificação/rastreamento de objetos em cenas. Um descritor é criado para cada região, a partir de histogramas de orientação do gradiente de setores ao redor do vértice, calculado de forma a garantir, como no SIFT, invariância à escala, rotação e iluminação. As contribuições do descritor proposto na segmentação de objetos em vídeo, feita a partir de corte em grafos, são testadas em três níveis: ajuste, ou compensação, de movimento do objeto em cena; reforço nos pesos de ligação entre arestas dos grafos, para os elementos considerados correspondentes entre os quadros e; determinação de grafos equivalentes com redução no número elementos guiada pela correspondência encontradas a partir algoritmo proposto. ________________________________________________________________________________________________ ABSTRACT / In the segmentation of object in video through frame to frame region tracking, the temporal coherence maintenance depends directly on the quality of the regions tracking along the frames. To this aim, principles of a widespread feature extractor, the SIFT, were adapted for the superpixels domain rendered as region graphs, which exhibits high efficiency in identification/tracking of objects in scenes. A descriptor is created to each vertex of graph, from orientation histograms of the gradient of bins around the vertex, calculated to ensure, as the SIFT, a scale, rotation and lighting invariance. The contributions of the proposed descriptor in the segmentation of objects in video, performed by a graph cut, are tested on three levels: the adjustment or compensation of the movement of object in scenes; the strengthening of the connection weights between edges of the graphs for the elements considered matches between frames and; the determination of equivalent graphs with reduction in the number elements guided by matches found through the proposed algorithm.

Neste trabalho tratamos de um problema clássico bem conhecido em Teoria dos Grafos: o problema da existência de um ciclo hamiltoniano. Um grafo é dito hamiltoniano se possui um ciclo hamiltoniano, ou seja, apresenta um ciclo que percorre todos os vértices do grafo. Estudamos problemas clássicos associados a este problema em termos do número de arestas, do grau mínimo e da sequência de graus dos vértices de um grafo. Além disso, estudamos resultados espectrais para o problema de hamiltonicidade referentes às matrizes de adjacências e laplaciana. A principal contribuição deste trabalho é a apresentação detalhada de condições suficientes e condições necessárias que garantem um ciclo hamiltoniano em um grafo já existentes na bibliografia. / In this work we study a well-known problem in Graph Theory: the existence of a Hamilton cycle, namely a cycle that goes through every vertex in the graph. We consider classical su cient conditions related with this problem in terms of the number of edges, the minimum degree and the vertex degree sequence of a graph. Furthermore, we study spectral results for the hamiltonian problem in terms of the adjacency and laplacian matrix. The main contribution of this work is our detailed presentation of necessary and su cient conditions for the existence of a Hamilton cycle in a graph.