O objetivo desta dissertação é apresentar uma pesquisa e investigação que validam uma proposta de sequência didática que utiliza a perspectiva metodológica da Resolução de Problemas para ensinar conceitos relacionados à Teoria de Grafos na escola básica, mais especificamente, no Ensino Fundamental. Para tanto, a metodologia de pesquisa escolhida foi o Estudo de Caso, de acordo com Fiorentini e Lorenzato (2006), Ventura (2007) e Gil (1995). O referencial teórico é baseado nos trabalhos do GTERP1, de Onuchic e Allevato (1999) e (2004), Polya (2006), Pozo (1998), Santos (2002) e De Maio (2009), bem como os PCNs2 e outros artigos/livros relacionados à Teoria de Grafos e à Resolução de Problemas. Apresentaremos uma prática realizada com cinco grupos de uma turma do sétimo ano do Ensino Fundamental, em uma escola particular de Porto Alegre, no ano de 2014. Concluímos que a escolha desse tópico da Matemática aliado à perspectiva metodológica da Resolução de Problemas contribui para o desenvolvimento intelectual e matemático, bem como para a formação de um indivíduo mais autônomo e crítico. / The aim of this dissertation is to show a research and investigation that validate a didactic propose of sequence that use the methodological perspective of Problem Solving to teach concepts related to Graph Theory in primary school, more specifically, in Elementary School. For this, the research methodology chosen was Case Study according to Fiorentini and Lorenzato (2006), Ventura (2007) and Gil (1995). The theoretical approach is based on the work of GETERP, Onuchic and Allevato (1999) and (2004), Polya (2006), Pozo (1998), Santos (2002) and De Maio (2009), as well as the National Curriculum Parameters (PCNs), books and articles dealing with Graph Theory and the Problem Solving. We will introduce a practice carried out with five groups of a class of seventh year of primary school, in a private school of Porto Alegre, in 2014. We conclude that the choice of this topic of mathematics combined with methodological perspective of Problem Solving contribute to the intellectual and mathematician development, as well as the formation of a more autonomous and critical individual.

o objetivo principal deste trabalho é apresentar uma proposta de inserção de Teoria de Grafos no Ensino Médio. Para tanto, será feita uma fundamentação de alguns aspectos acerca da Teoria de Grafos e Resolução de Problemas. Apresentaremos uma prática realizada em dois grupos de segundo ano do Ensino Médio, numa escola particular de Porto Alegre, no ano de 2006. A Teoria de Grafos apresenta aspectos pertinentes que merecem espaço no currículo da Escola Básica. Apresentaremos uma seleção de possíveis atividades a serem implementadas numa perspectiva metodológica de Resolução de Problemas. A escolha por tal perspectiva metodológica em Educação Matemática está vinculada à prática de Ensino de Matemática que acreditamos ser capaz de contribuir para a formação de um indivíduo autônomo, criativo e capaz de aprender a aprender. / The main goal of this thesis is to present a proposal for the insertion of Graph Theory in High School. In order to do that, we present some principIes of Graph Theory and review some important writings about Problem Solving methodology. We will give a suggested practice done with two groups in the second year of High School, in a private school of Porto Alegre in 2006. Graph Theory has some aspects that deserve space in the curriculum of the Basic School. We will show a selection of possible activities to be implemented within a methodological perspective of Problem Solving. The choice for this methodological perspective in Mathematics Education is related to a practice in Mathematics Teaching that we believe contributes for a development of a more autonomous and creative person. A person that is and able to learn how to learn.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work brings an approach to the basic notions of Graph Theory, presenting historical context, concepts, de nitions and examples in order to provide the reader with previous knowledge of the theory. The main objective is to perform a study of the graphs applied to the staining using the dual graph and the method of the greedy algorithm. To do so, we will present the demonstration attempt of the 4-Color Theorem that had been developed by Kempe and the proof of the 5-Color Theorem, made 11 years later by Heawood. Finally, we will seek the resolution of some situations problems that will be modeled through the coloring of vertices. / Este trabalho traz uma abordagem às noções da Teoria dos Grafos, apresentando contexto histórico, conceitos, definições e exemplos com o intuito de proporcionar ao leitor conhecimentos prévios da teoria. O principal objetivo é efetuar um estudo dos grafos aplicados à coloração mediante o uso do grafo dual e o métdo do algoritmo guloso. Para tanto, executaremos um esboço acerca da tentativa de demonstração do Teorema das 4 Cores que fora desenvolvida por Kempe e da prova do Teorema das 5 Cores, feita 11 anos mais tarde por Heawood. Por fim, buscaremos a resolução de algumas situações problemas que serão modeladas através da coloração de vértices. / São Cristóvão, SE

Orientador: Celia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas , Instituto de Computação / Made available in DSpace on 2018-08-06T12:11:33Z (GMT). No. of bitstreams: 1 Campos_ChristianeNeme_D.pdf: 1048367 bytes, checksum: e8270db6704873ddaf2043927ca93e99 (MD5) Previous issue date: 2006 / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation aims to introduce the basic concepts of graph theory to explore the concept of planarity and present a beautiful theorem connected to this theme. Graph theory is a very effective tool for solving problems involving several areas of knowledge. Some of these problems are related to planarity of graphs. Thus, this work presents Kuratowski’s theorem, with the beauty of its demonstration, which provides a necessary and sufficient condition for a graph to be planar, observing if it contains a specific type of subgraph related to complete and split graphs. / A presente dissertaçãoo tem como objetivo introduzir os conceitos básicos da teoria dos grafos para explorar o conceito de planaridade e apresentar um belo teorema ligado a esse tema. A teoria dos grafos é uma ferramenta muito eficaz na resolução de problemas que envolvem diversas áreas de conhecimento. Alguns destes problemas estão relacionados `a planaridade de grafos. Dessa forma, este trabalho apresenta o teorema de Kuratowski, com a beleza de sua demonstra¸c˜ao, que fornece uma condição necessária e suficiente para um grafo ser planar, observando se o mesmo contém um tipo específico de subgrafo relacionado a grafos completos e bipartidos. / São Cristóvão, SE

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to present a basic study of social networks and to show how some elements of this theory can be presented in classroom to illustrate and encourage the study of Graph Theory. To reach our goal, we developed some social network applications in State schools, through activities involving students and teachers as well as relationships between teachers and the educational institutions in which they work, activities which were developed using UCINET software. / Este trabalho tem como objetivo apresentar um estudo básico de redes sociais e mostrar como alguns elementos desta teoria podem ser apresentados em sala de aula para ilustrar e estimular o estudo da Teoria dos Grafos. Por isso, desenvolvemos algumas aplicações de redes sociais em sala de aula e instituições públicas de ensino, por meio de atividades envolvendo alunos e professores, bem como relações entre professores e as respectivas instituições de ensino nas quais trabalham, atividades as quais foram desenvolvidas através do software UCINET.

Orientador : Edson Moschim / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-31T15:17:34Z (GMT). No. of bitstreams: 1 Padua_FabianoJoaoL_M.pdf: 506585 bytes, checksum: 8bd26b8dae1ab8c932d8a24712288887 (MD5) Previous issue date: 2001 / Mestrado

Orientador: Akebo Yamakami / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:52:58Z (GMT). No. of bitstreams: 1 Verga_Juliana_M.pdf: 625534 bytes, checksum: 396d5b5c1dafff5b2fbb632e185c4a72 (MD5) Previous issue date: 2009 / Resumo: A teoria dos grafos é comumente utilizada na área da engenharia para resolver problemas que podem ser representados na forma de redes. Dentre diversos problemas abordados, o problema de fluxo multiproduto é um dos que também podem ser modelados por grafos. Este trabalho apresenta uma proposta de solução para o problema de fluxo multiproduto fuzzy. O problema foi modelado através de um grafo, cujos nós representam pontos de oferta e demanda de produtos, os quais trafegam pelos arcos da rede. O algoritmo proposto visa encontrar soluções factiveis e boas para o problema de fluxo multiproduto fuzzy em redes com incertezas nos custos e capacidades, contendo múltiplas origens e múltiplos destinos. As incertezas são modeladas por meio da teoria dos conjuntos fuzzy, que tem sido aplicada com sucesso em problemas com incertezas. / Abstract: The graph theory is commonly used in the area of engineering to solve problems that can be represented in the form of nets. Among several problems, the multicommodity flow problem is one that can be modeled by graphs. This work presents an approach for solving the fuzzy multicommodity flow problem. The problem was modeled through a graph whose nodes represent points of supply and demand of commodities, which pass through arcs of the network. Our algorithm aims to find a set of good feasible solutions for the fuzzy multicommodity flow problem in networks with uncertainties in the costs and capacities, containing multiple origins and multiple destinations. The uncertainties are modeled by means of the fuzzy sets theory, which has been successfully applied to problems with uncertainties. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores: Akebo Yamakami, Marcia Tomie Takahashi / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-08T13:05:12Z (GMT). No. of bitstreams: 1 Hernandes_Fabio_D.pdf: 995506 bytes, checksum: c4a27a827d2ca5ec109571ba03e4e094 (MD5) Previous issue date: 2007 / Resumo: A teoria de grafos é uma importante área da programação matemática, tendo um importante papel em áreas tais como engenharia e pesquisa operacional. Em particular, ela fornece ferramentas para tratar problemas de redes (tais como: alocação, caminho mínimo, fluxo máximo, etc.), que têm aplicações em diversas subáreas da engenharia (por exemplo: telecomunicações, transporte, manufatura, etc.). Estas aplicações podem, entretanto, possuir incertezas em seus parâmetros ou em sua estrutura. Baseado nisto, este trabalho trata de algumas importantes aplicações de problemas em grafos com incertezas em seus parâmetros ou estruturas e propõe algoritmos para encontrar suas soluções. As aplicações estudadas são: problemas de caminho mínimo, problemas de fluxo máximo, problemas de fluxo de custo mínimo e problemas de coloração de grafos. As incertezas são modeladas por meio da teoria dos conjuntos fuzzy, que tem sido aplicada com sucesso em problemas com incertezas e imprecisões / Abstract: The graph theory is an important area of mathematical programming, it has an important role in fields such as engineering and operational research. In particular, it provides the tools to tackle network problems (e.g. allocation, shortest path, maximum flow, etc), which have applications in several sub areas of engineering (e.g. telecommunications, transportation, manufacturing, etc). These applications can, however, possess uncertainties in their parameters or in their structure. Based on that, this work addresses some important applications of graph problems with uncertainties in their structure or parameters and proposes algorithms to find the solution to them. The applications studied are: shortest path problems, maximum flow problems, minimum cost flow problems and graph coloring problems. The uncertainties are modeled by means of the fuzzy sets theory, which has been successfully applied to problems with uncertainties and vagueness / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:57:31Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_M.pdf: 37565259 bytes, checksum: cddb8b852bd82318a8c784f1f223a076 (MD5) Previous issue date: 2007 / Resumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (¿route first, cluster second¿). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (¿cluster first, route second¿). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ¿route first cluster second¿ ou ¿cluster first route second¿), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geral / Abstract: This work¿s main study object consists on algorithms for routing meter readers, from which proposals towards solution¿s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader¿s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution¿s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor¿s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparisons / Mestrado / Automação / Mestre em Engenharia Elétrica