| dc.creator | Silva, Leila Maciel de Almeida e | |
| dc.date | 1991 | |
| dc.date | 1991-10-07T00:00:00Z | |
| dc.date | 2017-03-14T00:19:03Z | |
| dc.date | 2017-06-09T15:06:42Z | |
| dc.date | 2017-03-14T00:19:03Z | |
| dc.date | 2017-06-09T15:06:42Z | |
| dc.date.accessioned | 2018-03-29T02:19:11Z | |
| dc.date.available | 2018-03-29T02:19:11Z | |
| dc.identifier | SILVA, Leila Maciel de Almeida e. Fluxos inteiros em grafos. 1991. [85]f. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação, Campinas, SP. Disponível em: <http://libdigi.unicamp.br/document/?code=000035816>. Acesso em: 13 mar. 2017. | |
| dc.identifier | http://repositorio.unicamp.br/jspui/handle/REPOSIP/275927 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1314115 | |
| dc.description | Orientador: Claudio Leonardo Lucchesi | |
| dc.description | Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação | |
| dc.description | 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). | |
| dc.description | 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). | |
| dc.description | Mestrado | |
| dc.description | Mestre em Ciencia da Computação | |
| dc.format | [85]f. : il. | |
| dc.format | application/octet-stream | |
| dc.language | Português | |
| dc.publisher | [s.n.] | |
| dc.subject | GRAFO (Sistema de computador) | |
| dc.subject | Teoria dos grafos | |
| dc.subject | Processamento eletrônico de dados | |
| dc.title | Fluxos inteiros em grafos | |
| dc.type | Tesis | |
