Orientador: Jacques Wainer / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-05T07:24:55Z (GMT). No. of bitstreams: 1 Elias_GuilhermeSteinberger_M.pdf: 3432904 bytes, checksum: 9dba0032d1f963b571f539e39035e9d9 (MD5) Previous issue date: 2005 / Resumo: Esta é uma pesquisa, na área de Tecnologias de Informação, sobre como as inovações são disseminadas em sociedade. Tomando o trabalho de Everett Rogers (1962) sobre "difusão de inovações" como referência, o estudo situa-se na interface desta área com os campos da Sociologia e do Marketing, permitindo avaliar como as mudanças ou os novos conceitos são recebidos ou rejeitados em agrupamentos de diferentes naturezas. A representação de como as inovações penetram nestas populações tem sido feita através de simulações baseadas em grafos, onde cada vértice representa um membro da população. Nos estudos de Rogers e outros pesquisadores, prevalece uma forma aleatória de interconexão destes membros, aqui chamada de "mundo aleatório". Entretanto, mais recentemente, Watts (1999) descobriu que, sob certas condições, membros de grupos interconectam-se de forma que todos possuam apenas uns poucos intermediários entre si, em contextos onde haja vizinhanças com muitos membros já interconectados. Ainda hoje se estuda as causas para este fenômeno, chamado de "mundo pequeno". O objetivo deste trabalho é verificar como se comporta a curva de "difusão de inovações" em contextos com tais características e identificar as diferenças em relação ao modelo onde as interconexões eram aleatórias. Os primeiros resultados mostraram que, na maioria dos casos aqui analisados, a velocidade de aceitação de inovações (performance) é inferior em contextos de "mundo pequeno", se comparada aos de "mundo aleatório". Ao redesenharmos, entretanto, modelos de "mundo pequeno" com as mesmas definições de Watts e extraindo a aleatoriedade, encontramos uma performance superior, ainda que bem mais sensível do que as versões de Rogers e Watts em relação às características da população. Concluímos que a adoção de alguns modelos de "mundo pequeno" (desde que bem parametrizados) pode ser mais produtiva e permitir preservar características do mundo real, ou seja, obter efeito mais "natural". Testamos diferentes parâmetros, encontrando como mais produtivos: o grau de independência das novas conexões em relação às anteriores ( parâmetro a), a probabilidade aleatória de conexão entre dois membros quaisquer (parâmetro p), a quantidade média de conexões por membro (parâmetro km), a seleção de membros inovadores como líderes locais (além de possuírem conexão com outros grupos, detêm alto índice de conexões com seu próprio grupo). O modelo para simulação aqui utilizado, com pequeno ajuste, foi o de "multiagentes" idealizado por Maienhofer e Finholt (2000) / Abstract: This is a research in the area of Information Technology about how are the innovations disseminated in society. Taking the work of Everett Rogers (1962) about "diffusion of innovations" as reference, the study takes p1ace in the interface of this area with the fields of Sociology and Marketing, allowing evaluating how do the changes or new concepts are received or rejected in groups of different natures. The representation of how do the innovations penetrate in these populations has been done by simulations based on graphs, where each vertex represents one member of the population. In the studies of Rogers and other researchers, prevails a random shape of interconnection of these members, here known as "random world". But recent1y, Watts (1999) discovered that, under certain conditions, members of groups interconnect in such a way where all of them have on1y a few intermediates between each other, in contexts where there are neighborhoods with many members already connected. Still today, it's studied the causes for this phenomenon, known as "small world". The objective of this work is to verify how is the behavior of the curve of "diffusion of innovations" in contexts with these characteristics and identify the differences regarding the model where the interconnections were random. The first results showed that, in the majority of the cases here analyzed, the velocity of acceptance of innovations (performance) is lower in contexts of "small world", if compared to those from "random world". But, after redesigning models of "small world" based on the same definitions of Watts and extracting the randomness, we found a superior performance, even though it' s more sensible than versions of Rogers and Watts regarding the characteristics of the population. We concluded that the adoption of some models of "small world" (if with good parameters), can be more productive and allow the preservation of characteristics of real world, that means, to obtain a more "natural" effect We tested different parameters, finding advantages in the following: the degree of independence of new connections regarding the previous connections (parameter a), the random probability of connection between any two members (parameter p), the medium quantity of connections per member (parameter km), the selection of innovators members as local leaders (they have connection with other groups and high index of connections with their own group). The model used here for simulation, with little adjust, was the "multi-agents" idealized by Maienhofer and Finholt (2000) / Mestrado / Engenharia de Software / Mestre Profissional em Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T23:05:02Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_D.pdf: 1443438 bytes, checksum: c37eb2de501a4f5b10d9c8681c3a0971 (MD5) Previous issue date: 2009 / Resumo: Esta tese trata de fluxos inteiros e colorações em grafos, problemas intimamente relacionados. Concentramos nossa atenção nas Conjeturas de Tutte sobre 5-, 4- e 3-fluxos, as quais foram propostas entre as décadas de 50 e 70 e permanecem abertas até hoje. Apresentamos três abordagens para o ataque das conjeturas, com ênfase na Conjetura dos 3-Fluxos. Na primeira abordagem propomos o estudo dos grafos fluxo-críticos, aqueles que não admitem um k-fluxo, mas que passam a admitir quando sujeitos a uma simples operação de redução. O interesse no estudo dessa classe de grafos vem da observação de que todo contra-exemplo mínimo para qualquer uma das conjeturas de Tutte é fluxo-crítico. Na segunda abordagem estudamos a conexidade cíclica do contra-exemplo mínimo para uma conjetura equivalente à Conjetura dos 3-Fluxos. Na terceira abordagem buscamos uma nova demonstração do Teorema de Grötzsch, o qual é o dual planar da Conjetura dos 3-Fluxos, que não utilize a Fórmula de Euler como a demonstração original. / Abstract: The theme of this thesis is nowhere-zero flows and colourings of graphs, two subjects that are closely related. We focus mainly on the three Conjectures of Tutte concerning 5-, 4- and 3-nowhere-zero flows. These conjectures were proposed, respectively, in the 50's, 60's and 70's; all of them remain open so far. In this thesis we present three different approaches for the study of Tutte's Conjectures, with emphasis on the 3-Flow Conjecture. In the first approach, we introduce the concept of flow-critical graph. A graph is flowcritical if it does not admit a nowhere-zero k-flow but, when a simple reduction operation is applied, the resulting graph does admit a nowhere-zero k-flow. The motivation for the study of such graphs is due to the observation that any minimum counterexample for any of Tutte's conjectures lies in this particular class. In the second approach, we study the cyclic-connectivity of a minimum counterexample for an equivalent version of the 3-Flow Conjecture. In the third approach, we give a new proof for Gr¨otzsch's Theorem that differs from the original in the fact that it does not depend on Euler's Formula. / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Submitted by Lúcia Brandão (lucia.elaine@live.com) on 2015-12-14T18:11:19Z No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-20T18:20:45Z (GMT) No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-01-20T18:22:03Z (GMT) No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) / Made available in DSpace on 2016-01-20T18:22:03Z (GMT). No. of bitstreams: 1 Dissertação - Audemir Lima de Souza.pdf: 2998133 bytes, checksum: 80d0fe342d01a9b0c319d28a64167d5d (MD5) Previous issue date: 2013-08-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this work we make a simple approach to the concepts of graphs and make them better known, because although it has a wide variety of applications, is a little known subject in basic secondary education. In the intimate to disclose modeling using graph theory, concepts and definitions will be shown, models and classic examples applied by early scholars of this theory with the intention to motivate the logical reasoning of our students to assist them in the resolution of other problems. It will be shown as such information can be represented in the computer and how to decide which representation by choice. Also present algorithms that can bring in automated or computerized results because certain problems will solve only with the help of the machine. We believe that this form of modeling-problems can contribute to the improvement of teaching and learning and serve as a motivating factor for students and teachers seeking to improve their knowledge of graph theory and its applications. / Neste trabalho procuramos fazer uma abordagem simples sobre os conceitos de grafos e torná-los mais conhecidos, pois embora tenha uma grande variedade de aplicações, é um assunto pouco conhecido no Ensino Médio básico. No intimo de divulgar modelagem usando a teoria dos grafos, serão mostrados conceitos e definições, modelos e exemplos clássicos aplicados pelos primeiros estudiosos dessa teoria, com a intenção de motivar o raciocínio lógico de nossos alunos para auxiliá-los nas resoluções de outros problemas. Será mostrado como tais informações podem ser representadas no computador e como decidir por qual representação optar. Também apresentaremos algoritmos que podem nos trazer resultados automáticos ou informatizados, pois determinados problemas só resolveremos com o auxílio da máquina. Acreditamos que esta forma de modelas problemas pode contribuir para a melhoria do ensino-aprendizagem e servir como elemento motivador para alunos e professores que buscam melhorar seus conhecimentos sobre a teoria dos grafos e suas aplicações.

Orientadores: Pedro Jussieu de Rezende, Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T03:33:56Z (GMT). No. of bitstreams: 1 Silva_AndreCarvalho_M.pdf: 846347 bytes, checksum: ec1253f464900a70a0ef3bb68f9af1fa (MD5) Previous issue date: 2013 / Resumo: Grafos de visibilidade entre vértices de polígonos são estruturas que resumem as informações de visibilidade de tais vértices. Existem três relevantes problemas relativos a grafos de visibilidade: caracterização, reconhecimento e reconstrução. O problema da caracterização consiste em encontrar um conjunto de condições necessárias e suficientes para a classe de grafos de visibilidade. A procura de uma forma algorítmica para se reconhecer quando um grafo é de visibilidade define o problema de reconhecimento. O problema de reconstrução trata da questão de se reconstruir um polígono a partir de um grafo de visibilidade de tal forma que este seja isomorfo ao grafo de visibilidade do polígono. Neste trabalho, abordamos estes problemas para uma subclasse destes grafos: grafos de visibilidade de leques convexos. Dois resultados principais são apresentados nesse trabalho. O primeiro deles é um conjunto de três condições necessárias que um grafo de visibilidade de um leque convexo deve satisfazer. Adicionalmente, mostramos que estas condições são necessárias e suficientes para grafos de visibilidade de pseudo-leques convexos. Um resultado colateral deste processo é a equivalência entre grafos de visibilidade entre vértices, e grafos de visibilidade vértice-aresta, para leques convexos em posição geral. O segundo resultado consiste em que podemos reduzir o problema de reconstrução de polígonos unimonótonos para o mesmo problema para leques convexos / Abstract: The (vertex) visibility graph of a polygon is a graph that gathers all the visibility information among the vertices of the polygon. Three relevant problems related to visibility graphs are: characterization, recognition and reconstruction. Characterization calls for a set of necessary and sufficient conditions that every visibility graph must satisfy. Recognition deals with the problem of determining whether a given graph is the visibility graph of some polygon. Reconstruction asks for the generation of a polygon whose visibility graph is isomorphic to a given visibility graph. In this work, we study these problems on a restricted class of polygons, namely, convex fans: polygons that contain a convex vertex in its kernel. This work is comprised of two main results. The first one presents three necessary conditions that visibility graphs of convex fans must satisfy. We also show that those conditions are necessary and sufficient for visibility graphs of convex pseudo-fans. As a byproduct, we show that we can construct the vertex-edge visibility graph of a convex fan in general position from its vertex visibility graph. In the second major result, we show that we can reduce the reconstruction problem of unimonotone polygons to the same problem for convex fans / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

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