Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-08-30T17:24:15Z No. of bitstreams: 1 texto completo.pdf: 4232344 bytes, checksum: 570158c74aae3b6b7b1e909cc8bc8bce (MD5) / Made available in DSpace on 2016-08-30T17:24:15Z (GMT). No. of bitstreams: 1 texto completo.pdf: 4232344 bytes, checksum: 570158c74aae3b6b7b1e909cc8bc8bce (MD5) Previous issue date: 2015-08-28 / Um tema de estudo do ensino médio ́e a relação entre os números de vértices, arestas e faces, para poliedros convexos regulares, conhecida como Teorema de Euler. No caso geral esta relação ́e conhecida como característica de Euler. Neste trabalho apresentaremos exemplos de poliedros não convexos que satisfazem o Teorema de Euler e algumas formas de calcular a característica de Euler para poliedros no caso em geral, com o objetivo de fornecer um material mais acessível para professores que trabalham com este tema. / One topic of study in the high school is the relation between the number of vertices, the number of edges and the number of faces, for regular convex polyedra, known as Euler’s theorem. In the general case this relationsship is known as Euler characteristic. In this paper we present examples of non-convex polyhedrons which satisfies the Euler’s Theorem. We present some ways to computer the Euler characteristic to polyhedrons in the general case.

O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.

Freitas, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014. / Submitted by Juliana Almeida (julianaufc@gmail.com) on 2014-10-30T18:26:55Z No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Approved for entry into archive by Juliana Almeida(julianaufc@gmail.com) on 2014-10-30T18:28:27Z (GMT) No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Made available in DSpace on 2014-10-30T18:28:27Z (GMT). No. of bitstreams: 1 2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) Previous issue date: 2014 / In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K5 minor. / Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5.

SOARES, R. P. Jogos de perseguição-evasão, decomposições e convexidade em grafos. 2013. 206 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:11:52Z No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Approved for entry into archive by José Jairo Viana de Sousa(jairo@ufc.br) on 2015-11-25T13:04:50Z (GMT) No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) / Made available in DSpace on 2015-11-25T13:04:50Z (GMT). No. of bitstreams: 1 2013_tese_rpsoares.pdf: 1865132 bytes, checksum: e9214578093ec3c62c3eee11e731fdc6 (MD5) Previous issue date: 2013 / Esta tese é centrada no estudo de propriedades estruturais de grafos cujas compressões permitem a concepção de algoritmos eficientes para resolver problemas de otimização. Estamos particularmente interessados em decomposições, em jogos de perseguição-evasão e em convexidade. O jogo de Processo foi definido como um modelo para a reconfiguração de roteamento em redes WDM. Muitas vezes, jogos de perseguição-evasão, em que uma equipe de agentes tem como objetivo limpar um grafo não direcionado, estão intimamente relacionados com decomposições em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo é monotônico e definimos uma nova decomposição em grafos equivalente a tal jogo. A partir de então, investigamos outras decomposições em grafos. Propomos um algoritmo FPT para calcular vários parâmetros de largura em grafos. Em particular, este é o primeiro algoritmo FPT para calcular a largura em árvore especial e a largura em árvore q-ramificada de um grafo. Em seguida, estudamos um outro jogo perseguição-evasão que modela problemas de pré-obtenção. Nós introduzimos uma versão mais realista do jogo de Vigilância a versão on-line. Estudamos a diferença entre o jogo de Vigilância clássico e suas versões conectadas e on-line, fornecendo novos limites para essa diferença. Nós, então, definimos um modelo geral para o estudo de jogos perseguição-evasão, com base em técnicas de programação linear. Este método permite-nos dar os primeiros resultados de aproximação para alguns desses jogos. Finalmente, estudamos outro parâmetro relacionado com a convexidade e a propagação da infecção em redes, o “hull number”. Nós fornecemos vários resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposições em grafos. Alguns destes resultados respondem problemas em aberto na literatura.

Made available in DSpace on 2016-08-29T15:33:24Z (GMT). No. of bitstreams: 1 tese_9681_Ata de Defesa.pdf: 637986 bytes, checksum: 049a7d2723e6d0c1208ad9aad2eb9d0d (MD5) Previous issue date: 2016-03-28 / Um dos problemas clássicos da Teoria de Grafos é o problema de isomorfismo de grafos. Esse problema trata de determinar se, dado dois grafos, é possível definir um mapeamento entre seus vértices de forma que sejam respeitadas as conexões definidas por suas arestas. Um algoritmo proposto recentemente para resolver esse problema é o IVL (Iterated Vertex Labelling) [Baroni (2012)]. O GROOVE (GRaph-based Object-Oriented VErification) é uma ferramenta de verificação de modelos baseados em grafos que faz uso de algoritmos de isomorfismo. No contexto do GROOVE, o problema de isomorfismo de grafos se apresenta de uma maneira diferente do problema clássico: não se deseja determinar se dois grafos são isomorfos, e sim se, dado um grafo, ele é isomorfo a algum dos elementos de um conjunto de grafos. Neste trabalho, propõe-se a adaptação do IVL para o GROOVE e a realiza- ção de experimentos computacionais com o objetivo de determinar se essa adaptação traz ganhos de performance para a ferramenta. Os resultados levam à conclusão de que o IVL tem desempenho análogo ao algoritmo de isomorfismos que já está implementado no GROOVE. Além desses resultados, foi investigado em um cenário similar o uso de filtros de não-isomorfismo, com a intenção de determinar o não-isomorfismo entre dois grafos a um custo computacional baixo. Os resultados dos testes indicam que essa abordagem é bastante promissora, sendo capaz de detectar não-isomorfismos com eficiência de quase 100% , com tempos de execução bem mais baixos que os performados pelo algoritmo atual do GROOVE quando executado nesse cenário adaptado. / The graph isomorphism is a classical problem in Graph Theory, which consists of determining if, given two graphs, it is possible to define a mapping between their vertexes in a way so that the connection defined by their edges are respected. An algorithm proposed recently to solve this problem is the IVL (Iterated Vertex Labelling) [Baroni (2012)]. GROOVE (GRaph-based Object-Oriented VErification) is a graph-based model checking tool which makes use of isomorphism algorithms. In GROOVE’s context, the graph isomorphism problem is set differently from the classical problem: they are not interested on determining if two graphs are isomorphic, instead, they want to determine if, given a graph, it is isomorphic to one of the elements of a graph set. In this work, it’s proposed the IVL adaptation to GROOVE and computational experiments in order to test if this new adapted algorithm brings performance gains to the tool. It can be concluded from the results that IVL has a similar performance compared to the current implementation in GROOVE. Beyond those results, it was investigated in a similar framework the use of non-isomorphism filters, intending to determine the non-isomorphism between two graphs in a low computational cost. The test results point out that this is a promising approach, being able to detect non-isomorphisms with almost 100% efficiency, with a much lower running time when compared to current GROOVE algorithm when executed in this framework.

Dissertação (mestrado) - Universidade Federal de Santa Catarina. Centro Tecnologico / Made available in DSpace on 2016-01-08T15:39:56Z (GMT). No. of bitstreams: 1 82967.pdf: 5887865 bytes, checksum: 4125e0165ec77609d74b1306dc2f0ce5 (MD5) Previous issue date: 1987 / O presente trabalho tem por objetivo realizar uma análise comparativa entre dois algoritmos que determinam um caminho de mínimo custo, entre um vértice inicial e um vértice final especificados de um grafo com custos não-negativos. Inicialmente é feito um estudo desses algoritmos, bem como suas apresentações. Posteriormente é apresentada uma análise comparativa quanto ao desempenho computacional dos mesmos. Finalmente são relacionados os problemas estudados e um exemplo ilustra cada procedimento.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Mecânica. / Made available in DSpace on 2012-10-22T01:46:52Z (GMT). No. of bitstreams: 1 201660.pdf: 898356 bytes, checksum: 77a11015bf7aa1f3449bbad089828c10 (MD5) / Esta tese apresenta um método sistemático para calcular a cinemática diferencial de manipuladores por meio da extensão do método de Kirchhoff-Davies, usando o conceito de cadeia cinemática virtual. As cadeias cinemáticas virtuais são adicionadas convenientemente à

Orientador : Prof. Dr. Marcos Castilho / Coorientador : Prof. Dr. Luis Allan Künzle / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 15/07/2016 / Inclui referências : f. 55-57 / Área de concentração : Ciência da computação / Resumo: Nas últimas décadas, redes de Petri têm sido amplamente utilizadas como ferramenta para modelar, analisar, simular e avaliar o comportamento e desempenho de sistemas com peculiaridades de sincronização, concorrência e compartilhamento de recursos, como sistemas de manufatura, robótica, sistemas de tempo real entre outros. Um dos problemas enfrentados durante a modelagem desses sistemas está na explosão combinatória do número de estados, o que inviabiliza qualquer método de análise que tenha como base a enumeração desses estados, como o grafo de alcançabilidade. McMillan desenvolveu uma técnica conhecida como desdobramento - unfolding, a qual gera uma nova rede, de complexidade menor que a do grafo de alcançabilidade, que permite evitar análises enumerativas em sistemas modelados por redes de Petri. Em 2002, o algoritmo de McMillan foi aperfeiçoado por Esparza, Römer e Vogler, sendo criado o algoritmo ERV Unfolding, implementado nas ferramentas CUnf, MOLE e PUnf. Essas ferramentas são soluções específicas stand-alone, tendo como desvantagem a complexidade dos algoritmos e a consequente dificuldade de manutenção, prejudicando a alteração dos códigos para estudos e simulação de redes de Petri em ambientes distintos. A abordagem matricial de uma rede de Petri permite com maior facilidade, o estudo das propriedades estruturais e comportamentais da rede, sendo inclusive um facilitador para a implementação de um algoritmo de desdobramento, uma vez que a técnica será implementada através de operações matriciais. A abordagem matricial permite também a simulação e validação de projetos, visando minimizar falhas ou interrupções (deadlocks) do sistema. Assim, a presente proposta de dissertação tem como objetivo construir uma abordagem matricial para o desdobramento em redes de Petri, implementando-a como um módulo da ferramenta MATLAB. As implementações serão validadas através de estudo de caso, sendo posteriormente avaliados os resultados obtidos e as limitações da ferramenta em relação aos algoritmos citados. Palavras-chave: Redes de Petri, desdobramento, algoritmos, MATLAB. / Abstract: In recent decades, Petri nets have been widely used as a tool to model, analyze, simulate and evaluate the behavior and performance of systems with synchronization peculiarities, competition and resource sharing, as manufacturing systems, robotics, real-time systems among others. One of the problems faced during the modeling of these systems is the combinatorial explosion of the number of states, which prevents any method of analysis which is based on the enumeration of these states, as the states of reachability graph. McMillan created a technique known as split - unfolding, which generates a new network, complexity lower than the reachability graph, thus avoiding enumerative analysis systems modeled by Petri nets. In 2002, the algotirmo McMillan was perfected by Esparza, Römer and Vogler, being created the ERV Unfolding algorithm, implemented in CUnf, MOLE and PUnf tools. These tools are specific stand-alone solutions, with the disadvantage of the complexity of the algorithms and the consequent difficulty of maintenance, damaging the change of codes for studies and simulation of Petri nets in different environments. The matrix approach of a Petri net with greater ease allows the study of the structural and behavioral properties of the network, including being an enabler for implementing an unfolding algorithm, since the technique is implemented using matrix operations. The matrix approach also allows the simulation and design validation to minimize failures or interruptions (deadlocks) system. The proposed thesis aims to build a matrix approach for deployment on Petri nets, implementing it as a module of MATLAB tool. The implementations will be validated through case studies, and later evaluated the results and the limitations of the tool relative to those cited algorithms. Keywords: Petri net, unfolding, algorithm, MATLAB.

Orientador : Prof. Dr. André Luiz Pires Guedes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 10/04/2015 / Inclui referências : fls. 107-114 / Resumo: Este texto descreve um projeto de mestrado que consiste em uma comparaçãao de algumas invariantes da teoria dos grafos no contexto da previsão da estabilidade de moléculas de fulerenos. As invariantes investigadas incluem, entre outras, o critério de Fowler-Manolopoulos, o diâmetro, o índice de Wiener, a frustração bipartida de arestas, o número de independência, o número de emparelhamentos perfeitos, o número de Fries, e o número de Taylor. O objetivo principal aqui é computar seus valores para todos os isômeros de fulereno com até 130 vértices, e para todos os isômeros IPR com até 160 vértices. Até onde se sabe, ainda não foi feita nenhuma comparação experimental sobre a eficácia relativa dessas invariantes na previsão da estabilidade de fulerenos. Palavras-chave: Grafos, fulerenos, estabilidade, invariantes. / Abstract: This text describes a master's degree project that consists of a comparison of some graph theoretic invariants in the context of predicting the stability of fullerene molecules. Investigated invariants include, among others, the Fowler-Manolopoulos criterion, the diameter, the Wiener index, the bipartite edge frustration, the independence number, the number of perfect matchings, the Fries number, and the Taylor number. The main objective here is to compute their values for each fullerene isomer with up to 130 vertices, and each IPR isomer with up to 160 vertices. As far as is known, no experimental comparison has yet been made about the relative effectiveness of these invariants in predicting the stability of fullerenes. Keywords: Graphs, fullerenes, stability, invariants.

Orientador : Prof. Dr. André Luiz Pires Guedes / Coorientadora : Profª. Drª. Marina Groshaus / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 05/06/2017 / Inclui referências : f. 41-42 / Resumo: Na coloração de grafos existem algumas versões dos problemas de coloração de vértices e de coloração de arestas. Eles podem ser definidos a partir de conceitos como coloração por listas (colorir os elementos do grafo dados subconjuntos do conjunto de cores) ou colorir os elementos do grafo de forma que não existe uma estrutura monocromática. Um grafo G _e dito k-biclique aresta-selecionável se para qualquer atribuição de listas de cores para as arestas, onde cada lista tem tamanho k, existe uma coloração de E(G), onde cada aresta só pode usar as cores de sua lista, tal que não existe uma biclique (subgrafo induzido bipartido completo maximal) monocromática. Se k é o menor valor tal que G é k-biclique aresta-selecionável então k é o biclique índice de seleção de G. Assim nós podemos definir o k-biclique aresta-selecionabilidade como o problema de decidir se um grafo é k-biclique aresta-selecionável ou não. Nessa dissertação estudamos esse problema por provar que os grafos sem triangulo não isomorfo a um ciclo ímpar são 2-estrela aresta-selecionáveis (estrelas não monocromáticas), os bipartidos cordais são 2-biclique aresta-selecionáveis e mostramos um limite inferior do biclique índice de seleção dos grafos potencias de ciclos e potências de caminhos. E também apresentamos algoritmos polinomiais para computar uma 2-biclique (estrela) aresta-coloração das classes de grafos sem triangulo não isomorfo a um ciclo ímpar e bipartido cordal. Palavras-chave: Coloração por listas, Biclique, Coloração de arestas. / Abstract: In graph coloring there are some versions of the vertex coloring and edge coloring problems. They can be defined using concepts like list coloring (to color graph elements given subsets of the set of colors) or coloring the elements of a graph such that there is no monochromatic structure. A graph G is said to be k-biclique edge-choosable if for any list assignment of colors to graph edges, which each list has size k, there is a coloring of E(G), that the edges can only use colors from theirs lists, such that there is no monochromatic biclique (maximal induced complete bipartite subgraph). If k is the smallest value such that G is k-biclique edge-choosable then k is the biclique choice index of G. Therefore we can define the k-biclique edge-choosability as the problem to decide if a given graph is k-biclique edge-choosable or not. In this dissertation we studied this problem by proving that triangle-free graphs not isomorphic to odd cycle are 2-star edge-choosable, the chordal bipartite are 2-biclique edge-choosable and showing a lower bound for the biclique choice index of power of cycles and power of paths. And we also show polynomial algorithms to compute a 2-biclique (star) edge-coloring for the graph classes triangle-free not isomorphic to odd cycle and chordal bipartite. Keywords: List coloring, biclique, edge coloring.