Orientador: Sueli Irene Rodrigues Costa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-23T11:40:28Z (GMT). No. of bitstreams: 1 Alves_MarceloMunizSilva_M.pdf: 2107560 bytes, checksum: 6f6290ff4cfa14083f8d89ca2d08a5f5 (MD5) Previous issue date: 1998 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T21:07:02Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_M.pdf: 1466848 bytes, checksum: 52ed7d36d9f4f7cb6bee307b689f5f78 (MD5) Previous issue date: 2007 / Resumo: Um modulo de um grafo é um subconjunto de seus vertices que não é diferenciado, em relação à adjancencia peços demais vertices do mesmo grafo. Dado um mpodulo M de um grafo G, se todo módulo de G que intercepta M está contido nele ou o contém. M é denominado módulo forte¿Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital / Abstract: A module of a graph is a non distinguishable subset of nodes, regarding the nodes adjacency. Let M denote any module of a graph G. If every module of G wich overlaps M either contains M or is included in it, M is called a strong module...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1 Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5) Previous issue date: 2009 / Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6 / Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6 / Doutorado / Matematica Discreta e Combinatoria / Doutor em Ciência da Computação

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-17T14:13:30Z No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T13:07:06Z (GMT) No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) / Made available in DSpace on 2016-02-26T13:07:06Z (GMT). No. of bitstreams: 1 victoremanuelpintoguedes.pdf: 1012385 bytes, checksum: b255f491e5beb63bcf201beae74d43db (MD5) Previous issue date: 2014-08-09 / Este trabalho apresenta uma abordagem para a Teoria dos Grafos a ser aplicada no Ensino Médio. O objetivo é que, a partir dessa teoria, o aluno desenvolva a capacidade de elaborar métodos de resolução de problemas e de observar que problemas de Matemática Discreta não concernem somente problemas de contagem, como são usualmente abordados no Ensino Médio. Nesse trabalho, introduziremos conceitos da Teoria dos Grafos, grafos Eulerianos e Semieulerianos, buscando expor para um professor, uma abordagem possível da teoria, através dos conceitos, exemplos e problemas que devem ser exibidos para os alunos. Acreditamos que tal teoria deva ser apresentada no Ensino Médio devido a seu caráter investigativo, e por exigir do aluno uma capacidade interpretativa para buscar técnicas de resolução do problema. / This work presents an approach to Graph Theory to be applied in High School. The goal is that, from this theory, the student develops the ability to elaborate methods of solving problem and observe that discrete mathematics problems do not concern only counting problems, as they are usually approached in High School. In this paper, we introduce concepts of graph theory, Eulerian and Semieulerianos graphs, seeking to expose to a teacher, a possible approach to this theory, through the concepts, examples and problems that should be displayed to the students. We believe such a theory should be presented in High School due to its investigative character, and it requires the student an interpretative ability to pursue techniques to solve problems.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-04-18T19:25:02Z No. of bitstreams: 2 Dissertação - Simone I. M. Gama.pdf: 6174832 bytes, checksum: cb0205e2b98b47b323aebaecf952cff1 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-04-18T19:25:17Z (GMT) No. of bitstreams: 2 Dissertação - Simone I. M. Gama.pdf: 6174832 bytes, checksum: cb0205e2b98b47b323aebaecf952cff1 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-04-18T19:25:33Z (GMT) No. of bitstreams: 2 Dissertação - Simone I. M. Gama.pdf: 6174832 bytes, checksum: cb0205e2b98b47b323aebaecf952cff1 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-04-18T19:25:33Z (GMT). No. of bitstreams: 2 Dissertação - Simone I. M. Gama.pdf: 6174832 bytes, checksum: cb0205e2b98b47b323aebaecf952cff1 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-04-19 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work, the list coloring problem and choosability property in graphs are investigated. List coloring is a generalization of the vertex coloring problem in graph, and as this classic problem is to color a simple graph so that adjacent vertices have different colors, but respecting the additional constraint thaht each vertex has a list of porrible colors to be used. This problem has some variations as the (g;μ)-coloring, which involves sequential lists with lower and upper bounds known. The k-choosability is to determine the smallest size list k for which there is always a valid list coloring, whatever the distribution of the list in the graph. Thus, we investigated the correlation between k-choosability and (g;μ)-coloring, porposing the k-(g;μ)-choosability property. With this, we also analysed some proof tecnhiques in choosability, applied to determine k-(g;μ)-choosability for specific graphs are 3-(g;μ)-choosable and the technique of Marshal Hall, applied to prove that complete bipartite graphs are 2-(g;μ)-choosable. The most general result, obtaines throught a relatively simple formal proof, consisted to determine if a graph is k-colorable, then this graph is algo k-(g;μ)-choosable, leaving to be Pp 2-complete for NP-complete. Additionally, it was studied and implemented some algorithms to determine the list coloration and k-choosability for simple general graphs. / Nesta dissertação, o problema da lista coloração e a propriedade da selecionabilidade em grafos são abordados. Lista coloração é uma generalização do problema da coloração de vértices em grafos, e tal como este problema clássico, consiste em colorir um grafo simples de modo que vértices adjacentes possuam cores distintas, mas, respeitando- se a restrição adicional de que cada vértice possui uma lista restrita de possíveis cores a serem usadas. Tal problema possui algumas variações, como a (g;μ)-coloração, que envolve listas sequenciais com limite inferior e superior conhecidos. A k-selecionabilidade consiste em determinar o menor tamanho de lista k para o qual sempre há uma lista coloração, seja qual for a distribuição de lista no grafo. Nesta dissertação, se investigou a correlação entre a propriedade da k-selecionabilidade e a (g;μ)-coloração, sendo definida a propriedade de k-(g;μ)-selecionabilidade. Com isto, foram também estudadas algumas técnicas de prova em selecionabilidade, aplicadas para se determinar a k-(g;μ)-selecionabilidade para classes específicas de grafos, como a técnica de degeneração em grafos, usada para provar que grafos periplanares são 3-(g;μ)-selecionáveis e a técnica de Marshal Hall, usada para provar que grafos bipartidos completos são 2-(g;μ)-selecionáveis. O resultado mais geral, obtido através de uma prova formal, consistiu em determinar que se um grafo é k-colorível, então tal grafo também é k-(g;μ)-selecionável, deixando de ser Pp 2-completo para ser NP-completo. Adicionalmente, foram estudados e implementados alguns algoritmos para determinar a lista coloração e k-selecionabilidade em grafos simples gerais

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-09-11T13:46:43Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação Pericles Balderrama.pdf: 2562430 bytes, checksum: 225d4c2dd608f78114e9938de2d5861a (MD5) / Made available in DSpace on 2018-09-11T13:46:43Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação Pericles Balderrama.pdf: 2562430 bytes, checksum: 225d4c2dd608f78114e9938de2d5861a (MD5) Previous issue date: 2018-02-09 / This dissertation proposes a heuristic that uses the concept of market and the process of price formation as guidelines for the generation of routes in a factory plant scenario. The assumption is that the economic market is efficient in allocating scarce resources and that the price agglutinates in a single number the complexity of the productive process, simplifying the system of evaluation of economic agents. In this way, the price is adopted as the main variable in the selection of the sections that compose the routes. The price definition considered in the proposal differs from the cost per an updated variable considering only the market, that is, the interactions between economic agents. The market is modeled and implemented to simulate the movement of inputs in a manufacturing space, this space consisting of production cells interconnected by a transport grid in which the mobile robots carry inputs between the central warehouse and the production cells. In the proposed context robots are consumer economic agents and the crate of the grid are the traded products, there is a vendor that caters to all the robots. In the implementation of the proposed heuristic the Dijkstra algorithm is used to detect to the stretches that form the route with the minimum price in the market at a certain instant / Este trabalho propõe uma heurística que utiliza o conceito de mercado e no processo de formação de preço como diretrizes para a geração de rotas em um cenário de uma planta fabril. Assume-se como premissa que o mercado econômico é eficiente em alocar os recursos escassos e que o preço aglutina em um único número a complexidade do processo produtivo, simplificando o sistema de avaliação dos agentes econômicos. Desta forma, adota-se o preço como principal variável na seleção dos trechos que compõem as rotas. A definição de preço considerada na proposta diferencia-se do custo por se uma variável atualizada considerando unicamente o mercado, ou seja, as interações entre os agentes econômicos. O mercado é modelado e implementado para simular a movimentação de insumos em um espaço fabril, espaço este constituido por células de produção interligadas por uma grade de transporte na qual os robôs moveis transportam insumos entre o deposito central e as células de produção. No contexto proposto os robôs são agentes econômicos consumidores e os treicho da grade são os produtos negociados, existe um vendedor que atende a todos o conjunto de robôs. Na implementação da heurística proposta o algoritmo Dijkstra é utilizado para detectar aos trechos que forma a rota com o preço mínimo no mercado em determinado instante.

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:15:13Z (GMT). No. of bitstreams: 1 Chiba_ElaineAyumi_M.pdf: 5856831 bytes, checksum: f9d4b4bea391d9b772f2c53ce2466420 (MD5) Previous issue date: 2014 / Resumo: Representar os elementos de uma imagem em forma de grafos torna a estrutura organizada permitindo formular problemas de forma flexível e ser computacionalmente mais eficiente. Existem muitas técnicas da teoria de grafos sendo utilizadas em processamento digital de imagens. Em particular, o particionamento em grafos ou corte em grafos tem sido estudada por diversos autores como uma ferramenta de segmentação de imagens. Particionamento de um grafo refere-se à sua divisão em vários subgrafos tais que cada um deles representa um objeto de interesse na imagem. Neste trabalho, propomos um algoritmo de agrupamento hierárquico aglomerativo dos nós do grafo com base nas métricas de corte e corte médio. As segmentações foram avaliadas usando o benchmark da Berkeley BSDS500 que compara e classifica as segmentações em relação à outras técnicas existentes na literatura. Os resultados obtidos são promissores e nos permite concluir de que a combinação das métricas de corte e corte médio possibilitou melhores segmentações / Abstract: Representing the elements of an image in graphs makes the structure organized allowing to formulate problems in a flexible manner and can be more computationally efficient. There are many techniques of graph theory that are used in digital image processing. In particular, the graph partitioning or graph cut has been studied by several authors as a tool for image segmentation. Partitioning a graph refers to its division into several subgraphs such that each of them represents a meaningful object of interest in the image. In this work we propose a algorithm based on hierarchical agglomerative clustering of the graph nodes driven by the cut and mean cut criteria. The segmentati- ons results were evaluated using the benchmark of Berkeley BSDS500 that compares and classifies the results in relation to other existing techniques in the literature. The results obtained are promising and allows us to conclude that the combination of the cut and mean cut criteria possible best segmentations / Mestrado / Tecnologia e Inovação / Mestra em Tecnologia

Orientadores: Roberto de Alencar Lotufo, Letícia Rittner / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T05:00:23Z (GMT). No. of bitstreams: 1 Souza_RobertoMedeirosde_M.pdf: 27462483 bytes, checksum: fd6e6b42169addd0201eeda81c058aea (MD5) Previous issue date: 2014 / Resumo: A Árvore de Componentes é uma estrutura de dados que representa uma imagem através da relação de hierarquia de seus componentes conexos. Ela é uma estrutura adequada para a implementação de filtros conexos e que foi utilizada com sucesso em muitas aplicações. A Árvore Máxima é uma estrutura compacta para a representação da Árvore de Componentes. A principal contribuiçãoo deste trabalho é a proposta do filtro de Simplificação Maximal da Árvore Máxima (MMS) com dois possíveis critérios para efetuar o seu cálculo: um critério de limiarização normalizada (MMS-T) e um critério de Regiões Extremais Maximamente Estáveis (MMS-MSER). Uma metodologia para aplicar o filtro MMS em associação com o filtro de Extinção, que é formalmente definido nesse trabalho, é apresentada. É mostrado que após a aplicação da metodologia de simplificação, a qual escolhe o número de máximos relevantes a serem mantidos na imagem, o número de nós da Árvore Máxima simplificada é no máximo duas vezes o número de máximos mantidos. Para definir o filtro MMS, novos conceitos, como nó composto e sub-ramo são apresentados. Esses conceitos são importantes para definir muitos algoritmos da Árvore Máxima, e eles possuem interpretações interessantes em termos de processamento de imagem. Possíveis aplicações da metodologia proposta, tais como localização de texto, simplificação/segmentação de imagens e reconhecimento de objetos são ilustrados para mostrar o potencial da metodologia. Também, estudos explortatórios de detecção de regiões salientes em imagens e análise da robustez da topologia da Árvore Máxima são apresentados / Abstract: The Component Tree is a data structure that represents an image through the hierarchical relationship of its connected components. It is an adequate structure to implement connected filters, and it has been successfully used in many applications. The Max-Tree is a compact structure for the Component Tree representation. The main contribution of this work is the proposal of the Maximal Max-Tree Simplification (MMS) filter with two possible criteria to compute the filter: a normalized threshold criterion (MMS-T) and a Maximally Stable Extremal Regions (MSER) criterion (MMS-MSER). A methodology to apply the MMS filter in association to the Extinction filter, which is formally defined in this work, is presented. It is shown that after applying our simplification methodology, which sets the number of relevant maxima in the image to be kept, the number of nodes in the simplified Max-Tree is at most twice this number. In order to define the MMS filter, new concepts, such as composite node and sub-branches are introduced. These concepts are important to define many Max-Tree algorithms, and they have interesting interpretations in terms of image processing. Possible applications of the methodology proposed, such as text location, object recognition, and image simplification/segmentation are illustrated to demonstrate the potential of this methodology. Also, exploratory studies, such as detection of distinguished regions in the image, and analysis of the robustness of the Max-tree topology are presented / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Dessislava Hristova Kochloukova / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T09:11:38Z (GMT). No. of bitstreams: 1 Araujo_PaulaMacedoLinsde_M.pdf: 989128 bytes, checksum: 16ef5d7a0a914714bc4163e7549b1c3a (MD5) Previous issue date: 2014 / Resumo: Estudamos um resultado que se encontra no artigo "Finitely Presented Wreath Products And Double Coset Decompositions" de Y. de Cornulier que afirma que o produto entrelaçado entre os grupos W e G, com respeito a um G-conjunto X, é finitamente apresentável se, e somente se, as seguintes condições são satisfeitas: i. W e G são finitamente apresentáveis; ii. G age sobre X com estabilizadores finitamente gerados; iii. G age diagonalmente sobre X x X com finitas órbitas / Abstract: We study a result in the paper "Finitely Presented Wreath Products And Double Coset Decompositions" by Y. de Cornulier, which asserts that the wreath between the groups W and G with respect to a G-set X is finitely presented if and only if the following conditions hold: i. W and G are finitely presented; ii. G acts on X with finitely generated stabilizers; iii. G acts diagonally on X x X with finitely many orbits / Mestrado / Matematica / Mestra em Matemática

Orientadores: Célia Picinin de Mello, Christiane Neme Campos / Texto em português e inglês / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:30:28Z (GMT). No. of bitstreams: 1 Luiz_AtilioGomes_M.pdf: 1439406 bytes, checksum: e2dc07f910b1876087a8f61428919e30 (MD5) Previous issue date: 2014 / Resumo: O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005. Este problema consiste em associar cores às arestas e aos vértices de um grafo G=(V(G),E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u,v pertencentes a V(G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes. Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte. Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo Delta(G)+3 cores. Com base nesta observação, eles conjeturaram que Delta(G)+3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários, tendo sido verificada apenas para algumas famílias de grafos. Nesta dissertação, apresentamos uma resenha dos principais resultados existentes envolvendo a coloração total semiforte. Além disso, determinamos o número cromático total semiforte para as seguintes famílias: os grafos simples com Delta(G)=3 e sem vértices adjacentes de grau máximo; os snarks-flor; os snarks de Goldberg; os snarks de Blanusa generalizados; os snarks de Loupekine LP1; e os grafos equipartidos completos de ordem par. Verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+2. Investigamos também a coloração total semiforte dos grafos tripartidos e dos grafos equipartidos completos de ordem ímpar e verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+3. Os resultados obtidos confirmam a validade da Conjetura da Coloração Total Semiforte para todas as famílias consideradas nesta dissertação / Abstract: The adjacent-vertex-distinguishing-total-colouring (AVD-total-colouring) problem was introduced and studied by Zhang et al. around 2005. This problem consists in associating colours to the vertices and edges of a graph G=(V(G),E(G)) using the least number of colours, such that: (i) any two adjacent vertices or adjacent edges receive distinct colours; (ii) each vertex receive a colour different from the colours of its incident edges; and (iii) for any two adjacent vertices u,v of G, the set of colours that color u and its incident edges is distinct from the set of colours that color v and its incident edges. The smallest number of colours for which a graph G admits an AVD-total-colouring is named its AVD-total chromatic number. Zhang et al. determined the AVD-total chromatic number for some classical families of graphs and noted that all of them admit an AVD-total-colouring with no more than Delta(G)+3 colours. Based on this observation, the authors conjectured that Delta(G)+3 colours would be sufficient to construct an AVD-total-colouring for any simple graph G. This conjecture is called the AVD-Total-Colouring Conjecture and remains open for arbitrary graphs, having been verified for a few families of graphs. In this dissertation, we present an overview of the main existing results related to the AVD-total-colouring of graphs. Furthermore, we determine the AVD-total-chromatic number for the following families of graphs: simple graphs with Delta(G)=3 and without adjacent vertices of maximum degree; flower-snarks; Goldberg snarks; generalized Blanusa snarks; Loupekine snarks; and complete equipartite graphs of even order. We verify that the graphs of these families have AVD-total-chromatic number at most Delta(G)+2. Additionally, we verify that the AVD-Total-Colouring Conjecture is true for tripartite graphs and complete equipartite graphs of odd order. These results confirm the validity of the AVD-Total-Colouring Conjecture for all the families considered in this dissertation / Mestrado / Ciência da Computação / Mestre em Ciência da Computação