Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T03:38:43Z (GMT). No. of bitstreams: 1 Pereira_LuizFernandodeFaria_M.pdf: 862122 bytes, checksum: 06f038348723d2201293366e75808ffd (MD5) Previous issue date: 2013 / Resumo: Uma partição em caminhos de um grafo dirigido é uma partição do conjunto de vértices deste grafo em caminhos dirigidos. Dada uma métrica sobre partições em caminhos chamada k-norma, o problema de interesse é estabelecer para um dado grafo quais das suas partições em caminhos tem a menor k-norma dentre todas as suas possíveis partições em caminhos. Chamamos estas partições de k-ótimas. Na década de 1980, Claude Berge conjecturou que para toda partição k-ótima, existe um conjunto de k conjuntos independentes disjuntos que, em certo sentido, interceptam o maior número possível de caminhos desta partição. A validade ou a falsidade desta proposição ainda não foi demonstrada, e ela é conhecida como a conjectura de Berge sobre partições em caminhos. Nesta dissertação, fizemos um estudo geral sobre a conjectura de Berge, sua história recente, e o trabalho matemático que foi desenvolvido sobre ela. Exibimos demonstrações para diversos casos particulares da conjectura que já foram resolvidos, como para grafos bipartidos, hamiltonianos, acíclicos, partições compostas somente de caminhos curtos, partições compostas somente de caminhos longos, e para valores fixos de k. Uma parte significativa do trabalho foi dedicada à reescrita da demonstração recente do caso particular onde k = 2, feita por Eli Berger e Irith Hartman, e uma análise do método usado / Abstract: A path partition of a directed graph is a partition of its vertex set into directed paths. Given a metric over path partitions called the k-norm, the problem we are interested in is to determine for a given graph which of its path partitions have the smallest k-norm among all possible path partitions. These partitions are called k-optimal. In the 1980's, Claude Berge conjectured that for every k-optimal path partition, there exists a set of k disjoint independent sets which intercepts the maximum number of paths in this partition. The validity of this proposition has not yet been demonstrated, and it is known as Berge's conjecture on path partitions. In this work, we consider Berge's conjecture, its recent history, and the related mathematical work that has been accomplished. We show proofs for many particular cases of the conjecture, including for acyclic graphs, bipartite graphs, hamiltonian graphs, partitions which include only short paths, partitions which include only long paths, and for fixed values of k. A significant part of this work was dedicated to the rewriting of a recent proof for the particular case where k = 2 by Eli Berger and Irith Hartman, and an analysis of their method / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Roberto de Alencar Lotufo, Michel Couprie / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T20:58:19Z (GMT). No. of bitstreams: 1 Carvalho_MarcoAntonioGarciade_D.pdf: 2684164 bytes, checksum: 081708f37f7ec76c4b442c6d9701028d (MD5) Previous issue date: 2004 / Doutorado

Orientadores: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T22:32:38Z (GMT). No. of bitstreams: 1 Takahashi_MarciaTomie_D.pdf: 1514697 bytes, checksum: bf74eb1142b348387b3427a6f3cb4420 (MD5) Previous issue date: 2004 / Doutorado

Orientadores: Akebo Yamakami, Marcius Fabius Henriques de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-26T00:18:33Z (GMT). No. of bitstreams: 1 Takahashi_MarciaTomie_M.pdf: 4855054 bytes, checksum: 254a9111230a0122347cac87871a420e (MD5) Previous issue date: 2000 / Resumo: Em um problema de planejamento da produção, dado um ambiente de manufatura multiestágio, multiperíodo, multiproduto com demanda determinística, é importante a determinação de um conjunto de decisões que, num horizonte de planejamento e explorando a capacidade do sistema, evite atrasos e não atendimento aos pedidos dos clientes. O objetivo deste trabalho é o estudo do método de decomposição de Dantzig- Wolfe para a resolução deste problema trabalhando com a estrutura especial bloco-angular nas restrições. Aproveitando o paralelismo natural do problema, um estudo é realizado em um ambiente paralelizado com arquitetura do tipo MIMD, visando analisar o comportamento do método. Os programas visam a estrutura do método e são do tipo mestre-trabalhador com comunicação por troca de mensagens. A seguir, é feita uma comparação com outros métodos: Penalização Linear-Quadrática, Pontos Interiores e Simplex. A comparação dos métodos é feita utilizando o tempo (CPU time) na resolução dos cenários gerados a partir de dados reais de uma empresa / Abstract: In a production planning problem, for a multistage multiperiod multiproduct manufacturing environment with deterministic demand, the determination of a decision set that avoid backorder satisfacting system constraints is a crucial problem. In this work, the special block-angular structure of the problem is explored using the Dantzig- Wolfe decomposition method. AIso, exploring the natural parallel structure of the problem and the studied method, parallel environment (MIMD architeture) has been used. The programs are master-workers type. All inter-task communication is by message passing. After, Dantzig-Wolfe method is compared with Linear-Quadratic Penalty, Interior Point and Simplex methods. Several scenarios were created with real data from a brazilian industry. The methods comparison is done using the CPU time / Mestrado / Mestre em Engenharia Elétrica

Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T01:00:50Z (GMT). No. of bitstreams: 1 Silva_LeilaMacieldeAlmeidae_M.pdf: 2512572 bytes, checksum: bac1797d1e4cff92457eeaac832615b5 (MD5) Previous issue date: 1991 / Resumo: Neste trabalho é desenvolvido o estudo de fluxos inteiros em grafos, especificamente as Conjeturas de Tutte sobre a existência de k-fluxos (k = 3,4,5) que generalizam teoremas sobre coloração de grafos planares. A dissertação consiste de cinco capítulos. O capítulo 1 apresenta as Conjeturas de Tutte, além de um breve histórico sobre coloração de grafos. O capítulo 2 apresenta relações entre colorações de grafos planares, fluxos inteiros e fluxos modulares. O capítulo 3 apresenta configurações redutíveis, ou seja, subgrafos que não ocorrem em contra-exemplos mínimos para as Conjeturas de Tutte. O capítulo 4 apresenta os seguintes resultados conhecidos sobre a Conjetura dos 5-' fluxos: teorema dos 8-fluxos (Jaeger), teorema dos 6-fluxos (Seymour) e teorema dos 5-fluxos para grafos em superfícies de gênus baixo (Younger Moller-Carstens Drinkmann). O capítulo 5 apresenta os seguintcs resultados conhecidos sobre a Conjetura dos 3-fiuxos: teorema dos 4-fluxos (Jaeger) e teorema dos 3-fiuxos para grafos planares (Grotzsch; Grünbaum-Aksionov; Steinberg- Younger). / Abstract: A study of integer flows in graphs is developed, specifically on Tutte's Conjectures on the existence of k-flows (k = 3,4,5) that generalize theorems about planar graph colourings. This work consists of five chapters. The first chapter presents Tutte's Conjectures and a brief historical review of graph colouring. Chapter 2 presents relations among planar graph colouring, integer flows and modular flows. Chapter 3 presents reducible configurations, that is, subgraphs that do not occur in minimal counter-examples for Tutte's Conjectures. Chapters 4 presents well ' known results on the 5-flow Conjecture: Jaeger's 8-flow theorem, Seymour's 6flow theorem and the 5-flow theorem for graphs embedded on surfaces of low genus (Younger; Mõller-Carstens-Dririkmalin). Chapter 5 presents well known results on the 3-fiow Conjecture: Jaeger's 4-flow theorem and the 3-flow theorem for planar graphs (Grõtzsch; Grünbaum-Aksionov, Steinberg-Younger). / 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-15T05:25:59Z (GMT). No. of bitstreams: 1 MendoncaNeto_CandidoFerreiraXavierde_M.pdf: 1216674 bytes, checksum: 8e85895a8cb7f162a8e6807b1c063822 (MD5) Previous issue date: 1987 / Resumo: O primeiro capítulo introduz a noção de grafos perfeitos e as antigas conjeturas de Berge. A primeira delas, demontrada por Lovász, consta do capítulo 1 com o nome de Teorema dos Grafos Perfeitos. O segundo capítulo apresenta propriedades fundamentais dos grafos críticos (i. é, imperfeitos minimais) e os chamados grafos particionáveis. O capítulo termina com a apresentação dos grafos de cliques máximos de Tucker. O terceiro e último capítulo apresenta uma variada coleção de classes de grafos perfeitos. Foi consegui da uma tênue unificação de algumas dessas classes. O apêndice considera a segunda conjetura, a chamada conjetura "forte", e apresenta um resumo de algumas classes para as quais a conjetura vale / Abstract: The first chapter introduces the notion of perfect graphs and Berge's old conjecture, proved by Lovász, appears in chapter 1 under the name or Perfect Graphs Theorem. The second chapter presents fundamental properties of critical graphs (i. e., minimal imperfect graphs) and the so-called partitionable graphs. The chapter concludes with a presentation of Tucker's maximum clique graphs. The third and the last chapter presents a broad colection or classes of perfect graphs. The chapter presents a weak unification or these classes. The appendix analyzes the second conjecture, the so-called "strong" conjecture, and presents a survey of some classes over which this conjecture holds / Mestrado / Mestre em Ciência da Computação

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-05-24T17:50:03Z (GMT). No. of bitstreams: 1 338254.pdf: 521472 bytes, checksum: 0de8b7f4b116405482ddf4f65b71477c (MD5) Previous issue date: 2015 / Dados um corpo K e o grafo dirigido E, definido por (E 0, E 1, r, s), em que r e s são funções aplicadas nas arestas de E, vamos definir as K-à lgebras de Caminhos e as K-à lgebras de Caminhos de Leavitt do grafo E, que denotaremos respectivamente por A(E) e L_K(E), como as K-álgebras geradas a partir dos conjuntos de arestas e vértices do grafo E, e com relações que serão definidas neste trabalho. Iremos mostrar exemplos de grafos que geram à lgebras de Caminhos e à lgebras de Caminhos de Leavitt isomorfas a estruturas matemáticas já conhecidas, de forma a entender melhor como se comportam estas álgebras. Além disso, iremos provar resultados destas álgebras que são obtidos através de informações do grafo E. O principal resultado que iremos verificar neste trabalho diz como o grafo E pode implicar nas à lgebras de Caminhos de Leavitt serem simples, ou não.<br> / Abstract : Given K a field and the directed graph E, defined by (E 0,E 1,r,s), such that r and s are functions applied to the edges of E, we'll define the Path K-Algebras and the Leavitt Path K-Algebras of the graph E, that we are going to respectively call A(E) and L_K(E), as the K-algebras generated by the sets of edges and vertices of E, with relations that will be defined in this work. We'll be seeing examples of graphs that generate Path Algebras and Leavitt Path Algebras that are isomorphic to mathematical structures already known, as a way of better understanding how these algebras work. Furthermore, we'll be proving results of these algebras based on informations obtained from the graph E. The main result that we are going to prove here show us how the graph E can make the Leavitt Path Algebra be simple or not.

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-08-04T02:02:28Z (GMT). No. of bitstreams: 1 Minami_LiviaTeresa_M.pdf: 563009 bytes, checksum: be7f826dceafe196636b0ff05c5dad78 (MD5) Previous issue date: 2004 / Resumo: Este trabalho aborda propriedades de grafos que sao quocientes de reticulados e explora conexoes destes com a teoria de codigos corretores de erros. Esta organizado na seguinte forma: No primeiro capitulo sao introduzidos conceitos e principais resultados de teoria de grafos a serem utilizados. O segundo capitulo contem uma breve introdu»cao µa teoria de codigos corretores de erros e ¯nalmente no terceiro capitulo sao analisadas propriedades de grafos que sao quocientes de reticulados e suas relacoes com codigos em aspectos como rotulamentos e construcao de codigos / Abstract: Graphs which are quotients of lattices are studied in this dissertation and some of their connections to error correcting codes are explored. The text is organized as follows. In Chapter 1 the main concepts and results in Graph theory are introduced. Chapter 2 contains s brief introduction to error correcting codes theory and Chapter 3 is devoted to the study of properties of graphs which are quotient of lattices and their relations with codes in aspects like labelings and the construction of perfect codes / Mestrado / Matematica / Mestre em Matemática

Orientador: Walter Alexandre Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-20T18:42:45Z (GMT). No. of bitstreams: 1 MonteCarmelo_EmersonLuizdo_M.pdf: 2409540 bytes, checksum: b6122d0996eacaf5c5bc2ab13ba69bd3 (MD5) Previous issue date: 1995 / Resumo: Não informado / Abstracdt: Not informed / Mestrado / Mestre em Matemática

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-16T02:00:59Z (GMT). No. of bitstreams: 1 Taube_JaimedeMattos_M.pdf: 1255661 bytes, checksum: ff5047b766e8267439eee9debee809b1 (MD5) Previous issue date: 1992 / Resumo: Nesta dissertação é feito um estudo problema do carteiro chinês: as diferentes apresentações, formulações e métodos de resolução. Foi feita uma implementação do método de resolução do problema definido em redes não orientadas que utiliza a teoria de emparelhamento. Finalmente, é feito o estudo de um problema de distribuição de jornal. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada