Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-07-24T05:57:31Z (GMT). No. of bitstreams: 1 Barbosa_MarceloMarcos_M.pdf: 2201216 bytes, checksum: 6b62fa870c0ee2547c7f2b6fc939b03e (MD5) Previous issue date: 1998 / Resumo: Esta dissertação aborda o assunto Coloração de Arestas (Problema da Classificação) restrita aos cografos, onde o problema está em aberto. Após uma breve compilação de resultados de pesquisas tanto em coloração de arestas como em cografos, encontram-se os resultados obtidos para uma subclasse obtida ao limitarmos o número de níveis da cotree para 3: Ser subgrafo overfull é equivalente a ser overfull ou vizinhança overfull e Algoritmos que colocam na Classe 1 subconjuntos desta subclasse obtidos ao limitarmos o número de ramos da cotree para 2. / Abstract: This dissertation is on the subject of Edge Coloring (Classification Problem) restricted to cographs, for which the problem is open. After a brief compilation of research results on edge coloring and cographs, the results found for a subclass obtained when the number of levels of the cotree is limited to three: Being subgraph overfull is equivalent to being overfull or neighborhood overfull and Algorithms that place into Class 1 some subsets of this subclass obtained when the number of the branches of the cotree is limited to two. / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio L. Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T10:56:57Z (GMT). No. of bitstreams: 1 Cohen_Jaime_M.pdf: 1980563 bytes, checksum: 88f8b3def82f23368e2850ce7706fb31 (MD5) Previous issue date: 1995 / Resumo: Esta dissertação tem como objetivo apresentar igualdades minimax em grafos que envolvem cortes orientados; cortes ímpares e suas coberturas. A primeira metade da dissertação trata das igualdades que relacionam famílias disjuntas máximas de cortes com as coberturas mínimas dos cortes do grafo. Na segunda parte, os papéis destes problemas são inveI:tidos, isto é, as igualdades relacionam cortes mínimos com famílias disjuntas máximas de coberturas dos cortes. Mostramos ao longo do trabalho que em muitos casos é possível estabelecer analogias entre resultados para cortes orientados e para cortes ímpares. Estas analogias apresentam-se de duas maneiras: através de enunciados semelhantes e através de demonstrações semelhantes. Entre os teoremas apresentados na primeria parte do trabalho, destacam-se os Teoremas de ~ucchesi- Younger e de Edmonds-Giles para cortes orientados e os de Lovász e de Seymour para cortes ímpares. Também são apresentados teoremas que tratam de circuitos orientados e ímpares em grafos planares, mostrando que a analogia também se estende para outros tipos de problemas. Na segunda parte estabelecemos relações entre a igualdade minimax dual ao Teorema de Lovász com a generalização de uma famosa conjectura de Fulkerson. . Provamos um caso particular desta igualdade. Apresentamos também um resultado para um caso particular da igualdade dual ao Teorema de Lucchesi- Younger que foi provado por Schrijver e independentemente por Feofiloff e Younger. / Abstract: The goal of this dissertation is to unify some results of Graph Theory related to directed cuts, odd cuts and their coverings. In the first half of this work we show equalities that relate maximum disjoint families of cuts with the minimum coverings of the cuts of the graph. In the second half, we present the duals of those equalities, i. e., they relate minimum cuts with disjoint families of coverings. Qur main purpose. is to provi de examples that show analogies between results on directed cuts and odd cuts. The analogies are of two types: in the statements of the results and in their proofs. Among the results presented in the first half, the most important are Lucchesi- Younger and Edmonds-Giles' theorems on directed cuts and Lovász and Seymour's theorems for odd cuts. In the last part of this work we extend a result by Seymour that relates the dual of Lovász's theorem with a generalizatión of a famous conjecture due to Fulkerson. We prove a particular case of that equality. We also show an equality for a particular case of the dual of LucchesiYounger's theorem which had been proved by Schrijver and independent1y by Fe,ofiloff and Younger. / Mestrado / Mestre em Ciência da Computação

Orientador: Thiago de Melo / Banca: Elíris Cristina Rizziolli / Banca: Luiz Roberto Hartmann Junior / Resumo: Neste trabalho estudamos a Teoria de Grafos e a aplicamos na solução de alguns problemas clássicos, como por exemplo O Problema das Pontes de Königsberg, O Problema do Caixeiro Viajante, Classificação dos Poliedros Regulares e Coloração de Mapas. As ferramentas básicas foram Topologia Geral e Álgebra / Abstract: In this work we study Graph Theory and we apply it in the solution of some classical problems, for example Königsberg Bridges Problem, Travelling Salesman Problem, Classification of Regular Polyhedra and Map Coloring. The prerequisites are General Topology and Algebra / Mestre

Made available in DSpace on 2014-06-11T19:27:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-12-01Bitstream added on 2014-06-13T19:06:46Z : No. of bitstreams: 1 costa_pp_me_rcla.pdf: 598986 bytes, checksum: 67c1c7e0c368ded41dbfb9631bdf1362 (MD5) / Neste trabalho estudamos a Teoria de Grafos e a aplicamos na solução de alguns problemas clássicos, como por exemplo O Problema das Pontes de Königsberg, O Problema do Caixeiro Viajante, Classificação dos Poliedros Regulares e Coloração de Mapas. As ferramentas básicas foram Topologia Geral e Álgebra / In this work we study Graph Theory and we apply it in the solution of some classical problems, for example Königsberg Bridges Problem, Travelling Salesman Problem, Classification of Regular Polyhedra and Map Coloring. The prerequisites are General Topology and Algebra

Made available in DSpace on 2019-03-29T23:38:31Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-08-19 / There are studies that show distribution of crimes by census tracts in large cities follows a power law, criminality is an example of a complex system that can be mapped into geographic regions. This evidence means there are few places that concentrate many crimes and many places that concentrate few crimes. From this premise, if a geographic region formed by several census tracts has a distribution follows a power law, would be possible to split this region into several parts so these parts remain similar distributions to the distribution of region? The work proposed in this dissertation tries to answer this question using complex networks and evolutionary algorithms. The representation of a network in this work is a planar graph where the nodes are centroids of geographic areas, the edges represent the adjacency between these areas, and each node has a weight representing some data from an area, the weight would be the number of crimes registered in this area. The problem of this research lies in the context partitioning a planar graph in order to find the distributions of the partitions that have similar weights of the nodes with the distribution of weights of the nodes of the graph, each distribution of partition will function as a sample of distribution of graph, following a power law, these distribution of partitions will be useful to have a better understanding of complex systems that can be mapped into geographic regions. It was created two evolutionary algorithms aiming to solve the cited problem, in the tested databases it was possible to find approximately 90% of partitions with distribution of weights of nodes similar to the distribution of weights of the nodes of the original graph, and following power law. Keywords: Graph partitioning, Power Law, Planar graphs, Complex Networks and Evolutionary Algorithms. / Há trabalhos que evidenciam que a distribuição de crimes por setores censitários em grandes cidades segue uma lei de potência, a criminalidade é um exemplo de sistema complexo que pode ser mapeado em regiões geográficas. A evidência citada significa que, há poucos lugares que concentram muitos crimes e muitos lugares que concentram poucos crimes. Partindo dessa premissa, se uma região geográfica formada por vários setores censitários possuem uma distribuição que segue lei de potência, seria possível dividir essa região em várias partes de tal forma que essas partes mantenham distribuições semelhantes à distribuição da região? O trabalho proposto nesta dissertação tenta responder essa pergunta utilizando redes complexas e algoritmos evolutivos. A representação de uma rede neste trabalho é um grafo planar onde os nodos são centroides de áreas geográficas, as arestas representam a adjacência entre essas áreas, e cada nodo tem um peso representando um dado da área, que poderia ser o número de crimes registrados nesta área. O problema desta pesquisa reside no contexto de particionar um grafo planar com o intuito de encontrar partições que possuem distribuições dos pesos dos nodos semelhantes à distribuição dos pesos dos nodos do grafo, cada distribuição da partição funcionará como uma amostra da distribuição do grafo, seguindo uma lei de potência, essas distribuições das partições serão úteis para ter um melhor entendimento de sistemas complexos que podem ser mapeados em regiões geográficas. Foram criados dois algoritmos evolutivos objetivando solucionar o problema citado, nas bases de dados testadas foi possível encontrar aproximadamente 90% das partições com distribuições dos pesos dos nodos semelhantes à distribuição do grafo original, e seguindo lei de potência. Palavras-chave: Particionamento de Grafos, Lei de Potência, Grafos Planares, Redes Complexas e Algoritmos Evolutivos.

Made available in DSpace on 2014-06-12T17:41:06Z (GMT). No. of bitstreams: 2 arquivo7693_1.pdf: 8738169 bytes, checksum: 69cbd4ee0190ffb58cf4da16220d65c5 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2004 / Neste trabalho mostrou-se que através da teoria dos grafos é possível se reconhecer automaticamente as operações de fresamento. Para tal partiu-se dos desenhos em CAD da peça bruta e da peça a usinar. Através de uma operação booleana de diferença determinou-se o volume a ser removido em forma de cavaco. Este volume foi subdividido e codificado em sub-volumes, a partir dos vértices da peça final, projetados nas direções x, y e z. Com os sub-volumes foram construídos os grafos, que têm como origem nas fronteiras da peça bruta. Em seguida foram definidas regras, em forma de perguntas, que aplicadas aos grafos geram respostas em forma de código com treze campos que são preenchidos com os caracteres 0 , 1 e x (zero, um e xis). Estes códigos são capazes de identificar de forma peculiar cada uma das operações de fresamento

Submitted by Puentes Torres Antônio (antoniopuentes@hotmail.com) on 2016-07-29T19:42:16Z No. of bitstreams: 1 Dissertacao.Aline.pdf: 2469962 bytes, checksum: 8ab538e60b5af90484efc4cda4a1f3b2 (MD5) / Approved for entry into archive by Geociências (bigeoufba2016@gmail.com) on 2016-08-02T13:42:43Z (GMT) No. of bitstreams: 1 Dissertacao.Aline.pdf: 2469962 bytes, checksum: 8ab538e60b5af90484efc4cda4a1f3b2 (MD5) / Made available in DSpace on 2016-08-02T13:42:43Z (GMT). No. of bitstreams: 1 Dissertacao.Aline.pdf: 2469962 bytes, checksum: 8ab538e60b5af90484efc4cda4a1f3b2 (MD5) / RESUMO A compreensão da rede urbano-regional pressupõe não somente a análise dos núcleos que a compõem, mas, primordialmente, das relações e funções, cujos grau e intensidade refletem a sua coesão e importância no âmbito regional. Para tal, torna-se imprescindível à implantação e manutenção de uma rede de transportes que cumpra eficientemente a sua função como um sub-sistema fundamental para a sustentabilidade organizacional do sistema regional. É neste ponto em que está centrada a ênfase da pesquisa quando objetiva analisar a rede de transporte aéreo no Estado da Bahia como elemento fundamental para o seu desenvolvimento e inserção nos cenários nacional e internacional, partindo de uma abordagem centrada no enfoque sistêmico, com essência na Teoria Geral dos Sistemas na Análise das Redes Geográficas, e estrutural a partir da aplicação da Teoria dos Grafos. Enfoque este que tem como principal ponto de questionamento o atendimento aos organismos (as regiões) constituídos no território baiano, cuja dinâmica sócio-espacial justifique a implantação de atividades desse setor, tecnologicamente especializado e extremamente dependente de constantes investimentos e, conseqüentemente, de uma demanda que a justifique, ou seja, um setor altamente seletivo e ainda segregador do ponto de vista do social como um todo integrado. Assim, considerando a espacialização das ligações aéreas diretas (sem escalas e conexões) e os problemas de acessibilidade e interação sócio-espacial advindos das dificuldades ou impossibilidade de movimentação pelo espaço e, assim dizendo, a sua “apropriação” por meio do direito ao uso, constata-se que, apesar da importância do Estado, os desequilíbrios regionais internos não permitem uma real inserção na dinâmica nacional. A integração sócio-espacial de seus centros mais dinâmicos e a busca pela inserção das economias marginais é o caminho mais racional e o primeiro passo para a sua estabilização e desenvolvimento econômicos. Tanto no cenário nacional quanto no internacional, a posição de subordinação da região é bem caracterizada e definida pela história de sua evolução. A importância dessa subordinação política e econômica é tal, que o Estado tem como área de influência direta da rede de transporte aéreo apenas os Estados limítrofes, ao Norte, os demais Estados da Região Nordeste (região em que a Bahia conseguiu se consolidar como liderança) e, ao Sul e Sudeste, os Estados de São Paulo, Minas e Rio de Janeiro, cuja relação é, como mencionada anteriormente, de dependência. Em resumo, a influência da Bahia está basicamente no Nordeste, nas relações com suas mais importantes cidades, especificamente as capitais. / ABSTRACT The comprehension of regional urban web presupposes not only an analysis of centers which compose the web, but, primordially, the analysis of relationships and functions, whose degree and intensity reflect its cohesion and its importance in regional context. On that occasion, becomes necessary the implantation and maintenance of a transport web that accomplish efficiently its function as a fundamental sub-system to the maintenance of regional system. That’s the point of this work that aim to analyse the air transport web in the State of Bahia as fundamental element to its development and insertion in national and international sceneries. This work is focused in systematical approach, based on essence of Systems General Theory in Analysis of Geographic Webs, and structural by Graph Theory. This focus has as main question the supply to the organisms (regions) existents in the baiense territory, whose socialspatial dynamic justifies the implantation of activities of this sector, technologically specialized and extremely dependent of constants investitures and, consequently, of a demand that justifies it, it means, a sector highly selective and segregator from social point of view as a whole integrate. Therefore, considering the space of direct air-bone binding (without intermediate landing and connection) and the accessibility problems and social-spatial interaction originated by difficulties or impossibility of motion in the space and its “appropriation” by right of employ, it proves that, even State’s importance, the internal regional unbalances don’t allow a real insertion in national dynamic. The integration socialspatial of its centers more dynamics and the searching for insertion of marginal economies is the rational way and the first step to its stabilization and economics develops. As much as in national scenery and international scenery, the position of subordination of region is well characterized and defined by history of its evolution. The importance of this political subordination and economical is so grave that the State has an area of direct influence of air transport web only the adjacent States, to the North, the States of Northern Region (region where Bahia got consolidated as leadership) and, to the South and Southern, the States of São Paulo, Minas and Rio de Janeiro, whose relationship is determinate by dependence, as mentioned before. In short, the Bahia’s influence is basically in Northern, on relationships with its most important cities, specifically the metropolis.

BASTOS, Antonio Josefran de Oliveira. Sequências convergentes de estruturas discretas e testabilidade. 2012. 62 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T18:57:48Z No. of bitstreams: 1 2007_dis_adbnogueira.pdf: 13756193 bytes, checksum: bb4a338bd2622ad6f90479ce37824ccd (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:31:42Z (GMT) No. of bitstreams: 1 2007_dis_adbnogueira.pdf: 13756193 bytes, checksum: bb4a338bd2622ad6f90479ce37824ccd (MD5) / Made available in DSpace on 2016-07-13T13:31:42Z (GMT). No. of bitstreams: 1 2007_dis_adbnogueira.pdf: 13756193 bytes, checksum: bb4a338bd2622ad6f90479ce37824ccd (MD5) Previous issue date: 2012 / In this work, we studied the recent theory of convergent graph sequences and its extensions to permutation and partially ordered sets with fix dimension. We’ve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable. / Neste trabalho, estudamos a teoria recente de convergência de sequências de grafos e suas extensões para permutações e ordens parciais de dimensão fixa. Conjecturamos um lema de regularidade fraca de grafos em intervalos que, se for verdadeira, nos possibilita estender essa teoria para grafos ordenados, que são grafos tais que existe uma ordem total entre os vértices. Mostramos algumas relações interessantes de permutações e ordens parciais com grafos ordenados. Com isso, conseguimos uma prova alternativa para a existência de objetos limites de qualquer sequência convergente de permutações. Provamos também que toda propriedade hereditária de permutações ou grafos ordenados é testável.

O objetivo principal deste trabalho é tratar as implicações geométricas e topológicas da planaridade, destacando a influência desse conceito em problemas geométricos fundamentais. Tais problemas são derivados da fórmula de Euler e suas diversas aplicações. Também problemas topológicos, como o problema de coloração de mapas, são estudados na dissertação. A teoria de grafos tem extensiva utilização em matemática aplicada, pois demonstra ser uma poderosa ferramenta para a modelagem de diversas situações reais em física, química, biologia, engenharia elétrica e pesquisa operacional. Tanto em problemas práticos como em problemas teóricos tem-se o fato que a maioria das aplicações admitem métodos de resolução mais eficientes se o grafo associado for planar. A determinação da planaridade de um grafo é importante em diversas aplicações na indústria, engenharia e outras. Um aspecto neste estudo é que a planaridade é uma propriedade preservada mediante o isomorfismo de grafos. Também apresenta-se duas caracterizações da planaridade, uma devido a Kuratowski e outra devido a Wagner. São dois resultados clássicos da teoria de grafos, que identificam condições necessárias e suficientes para um dado grafo ser planar, e cujas técnicas de demonstração são ainda importantes em combinatória. / The main goal of this work is to treat the geometrical and topological implications of planarity, highlighting the infl.uence of t his concept over fundamental problems. Such problems are derived from the Euler's formula and its applications. Topological problems, such as map colouring, are also dealt with in this thesis. Graph theory has extensive use in applied mathematics, because it shows to be a powerful tool for modelling real situations in physics, chemistry, biology, electrical engineering and operational research. In theory, as well as in practical problems, it is the fact most applications admit more efficient solution methods if the associated graph is planar. The determination of the planarity of a graph is important in various applications in industry, engineering and others. An aspect of this survey is that planarity is an invariant property preserved throu~h graph isomorphisms. It is also presented two characterizations of planarity. One is due to Kuratowski and the other is due to Wagner. These are two classical results of graph theory, that identify necessary and sufficient conditions for a graph to be planar, whose t echniques are still important in combinatorics.

BASTOS, Antonio Josefran de Oliveira. Sequências Convergentes de Estruturas Discretas e Testabilidade. 2012. 47 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2012. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-31T19:31:54Z No. of bitstreams: 1 2012_dis_ajobastos.pdf: 836578 bytes, checksum: 7267190dcdfd4c22a13a8a661fa593b4 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-31T19:32:46Z (GMT) No. of bitstreams: 1 2012_dis_ajobastos.pdf: 836578 bytes, checksum: 7267190dcdfd4c22a13a8a661fa593b4 (MD5) / Made available in DSpace on 2016-05-31T19:32:46Z (GMT). No. of bitstreams: 1 2012_dis_ajobastos.pdf: 836578 bytes, checksum: 7267190dcdfd4c22a13a8a661fa593b4 (MD5) Previous issue date: 2012 / In this work, we studied the recent theory of convergent graph sequences and its extensions to permutation and partially ordered sets with fix dimension. We’ve conjectured a lemma of weak regularity on intervals that, if this conjecture is true, we can extend this theory to ordered graphs, which are graphs such that there is a total order on its vertices. We show some interesting relations on permutation and partially ordered sets with ordered graphs. Then, we obtain another proof to the existence of limit objects for all convergent permutation sequences. We also proved that all hereditary property of either permutation or ordered graph is testable. / Neste trabalho, estudamos a teoria recente de convergência de sequências de grafos e suas extensões para permutações e ordens parciais de dimensão fixa. Conjecturamos um lema de regularidade fraca de grafos em intervalos que, se for verdadeira, nos possibilita estender essa teoria para grafos ordenados, que são grafos tais que existe uma ordem total entre os vértices. Mostramos algumas relações interessantes de permutações e ordens parciais com grafos ordenados. Com isso, conseguimos uma prova alternativa para a existência de objetos limites de qualquer sequência convergente de permutações. Provamos também que toda propriedade hereditária de permutações ou grafos ordenados é testável.