To see the other types of publications on this topic, follow the link: Teoria dos grafos.
Dissertations / Theses on the topic 'Teoria dos grafos'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Teoria dos grafos.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
SANTOS, P. L. F. "Teoria Espectral de Grafos Aplicada ao Problema de Isomorfismo de Grafos." Universidade Federal do Espírito Santo, 2010. http://repositorio.ufes.br/handle/10/4219.
Full textAbstract:
Made available in DSpace on 2016-08-29T15:33:12Z (GMT). No. of bitstreams: 1
tese_3542_.pdf: 1219514 bytes, checksum: 46e780a84760376a53aff9fb5e279285 (MD5)
Previous issue date: 2010-08-23<br>Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram presentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura.
2
Souza, Audemir Lima. "Teoria dos grafos e aplicações." Universidade Federal do Amazonas, 2013. http://tede.ufam.edu.br/handle/tede/4788.
Full textAbstract:
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)<br>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)<br>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)<br>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<br>CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>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.<br>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.
3
Soares, de Melo Gildson. "Introdução à Teoria dos Grafos." Universidade Federal da Paraíba, 2014. http://tede.biblioteca.ufpb.br:8080/handle/tede/7549.
Full textAbstract:
Submitted by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2015-11-04T14:09:27Z
No. of bitstreams: 2
arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)<br>Approved for entry into archive by Maria Suzana Diniz (msuzanad@hotmail.com) on 2015-11-05T11:26:40Z (GMT) No. of bitstreams: 2
arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)<br>Made available in DSpace on 2015-11-05T11:26:40Z (GMT). No. of bitstreams: 2
arquivototal.pdf: 817270 bytes, checksum: ba2aa7837f218549769442c49a92611c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-08-22<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>This paper presents an introductory study of graph theory, considering its relevance
to the teaching of mathematics. Initially presents a brief history on Graph
Theory. Then the rst chapter consists of some de nitions on graphs and examples,
the second chapter deals with the paths, walks and cycles in a graph, highlighting
the Eulerian tours and Hamiltonian cycles, also boarded a special type of graphs,
trees . In Chapter 3 we address the planarity in graphs, thus presenting Euler's
Formula. Finally in Chapter 4 we present some problems involving graphs.<br>Este trabalho apresenta um estudo introdutório sobre Teoria dos Grafos, considerando
sua relevância para o ensino da Matemática. Inicialmente é apresentado um
breve histórico sobre a Teoria dos Grafos. Em seguida, o capítulo 1 é constituído por
algumas defi nições sobre grafos e exemplos, o capítulo 2 trata dos caminhos, passeios
e ciclos num grafo, destacando-se os passeios Eulerianos e os ciclos Hamiltonianos,
abordamos também um tipo especial de grafos, as árvores. No capitulo 3 abordamos
a planaridade nos grafos, apresentando assim a Fórmula de Euler. Finalmente no
capítulo 4 apresentamos alguns problemas envolvendo grafos.
4
Santos, Sandra Maria Pereira do. "Aplicações da teoria dos grafos." Master's thesis, Universidade de Aveiro, 2013. http://hdl.handle.net/10773/13313.
Full textAbstract:
Mestrado em Matemática e Aplicações<br>Nesta dissertação apresenta-se uma breve introdução à teoria dos grafos com a abordagem a algumas noções e conceitos de grafos, seguindo-se a apresentação de algumas aplicações da teoria dos grafos na resolução de problemas nas várias áreas do conhecimento. Neste trabalho é dada enfase a alguns problemas bem conhecidos, tais como o problema das pontes de Königsberg, o problema do caixeiro-viajante, o problema do carteiro Chinês e alguns problemas relacionados com a coloração de grafos.<br>In this thesis we presents a brief introduction to graph theory with the approach to some notions and concepts of graphs, followed by the presentation of some applications of graph theory to solve problems in several areas of knowledge. In this work we emphasize some well-known problems such as the Königsberg bridges problem, the problem of the traveling salesman, the problem of Chinese postman and some problems related with graph coloring.
5
Almeida, Sheila Morais de 1979. "Grafos PI." [s.n.], 2005. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276351.
Full textAbstract:
Orientadores: Celia Picinin de Mello, Anamaria Gomide<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-08-04T17:24:05Z (GMT). No. of bitstreams: 1
Almeida_SheilaMoraisde_M.pdf: 420796 bytes, checksum: 2ffdaaee7ece5527360d5a4d0a2827ff (MD5)
Previous issue date: 2005<br>Resumo: Uma representação PI consiste em duas retas paralelas, r e s, e triângulos com um vértice em r e um lado em s. Considere R uma representação PI. O grafo interseção de R é chamado grafo P I quando cada vértice do grafo corresponde a um triângulo de R e existe aresta entre dois vértices se, e somente se, os triângulos correspondentes se intersectam. Segundo o livro Graph Classes - a Survey (1999) [3], escrito por Brandstiidt, Le e Spinrad, os problemas de reconhecer e de caracterizar a classe dos grafos PI ainda não estão resolvidos. Essa é a principal motivação para o estudo da classe PI. Nesta dissertação, apresentamos um estudo dos grafos PI baseado nas suas relações com outras classes de grafos tais como os grafos de intervalos e permutação, que são classes amplamente conhecidas de grafos interseção, e os grafos trapezóides, que possuem uma estrutura muito semelhante à dos grafos PI. Esta dissertação é uma síntese de trabalhos existentes sobre a classe PI e apresenta novas condições necessárias e/ou suficientes para que um grafo seja PI<br>Abstract: A PI-representation consists of two parallellines, r and s, and triangles with one vertex on r and the other two on s. Let R be a PI-representation. The intersection graph of R is called PI graph when each vertex in the graph corresponds to a triangle in R and there exists an edge between two vertices if and only if their corresponding triangles intersect. According to the book Graph Classes - a Survey (1999) [3], by Brandstiidt, Le and Spinrad, the PI graph characterization and recognition problems are still open. This is the main motivation for the study of the PI graph class. In this dissertation, we present a study of PI graphs based on their relationship with other graph classes such as the interval and permutation graphs, which are well known intersection graph classes, and trapezoid graphs, which have a very similar structure to that of PI graphs. This dissertation is a survey on existing work on the PI graph class and presents new necessary andj or sufficient conditions for a graph to be PI<br>Mestrado<br>Teoria da Computação<br>Mestre em Ciência da Computação
6
Oliveira, Marcelo Mendes de. "AplicaÃÃes da teoria dos grafos à teoria dos grupos." Universidade Federal do CearÃ, 2008. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=5532.
Full textAbstract:
Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico<br>O propÃsito desta dissertaÃÃo à apresentar aplicaÃÃes da Teoria dos Grafos à Teoria dos Grupos. De posse do grafo associado a um grupo finito, nÃs obtemos vÃrios resultados interessantes sobre a estrutura do grupo analisando tal grafo à luz de tÃcnicas-padrÃo da Teoria dos Grafos. Mais precisamente, os nÃmeros cromÃtico e de independÃncia do grafo de um grupo finito nos permitem estimar a cardinalidade mÃxima de um subgrupo abeliano do mesmo, bem
como o tamanho mÃnimo possÃvel de um subconjunto do grupo formado por elementos que nÃo comutam dois a dois; no caso de grupos finitos abelianos, nÃs tambÃm estudamos seus
subconjuntos livres de somas.<br>This report deals with applications of Graph Theory to Group Theory. Once we construct the graph associated to a finite group, we get several interesting results on the group structure by analysing its associated graph with the help of various standard graph-theoretic tools.
More precisely, the chromatic and independence numbers of the graph of a finite group allows us to estimate the maximal cardinality of an abelian subgroup of it, as well as the minimal size of a subset of the group, all of whose elements donât commute in pairs; for finite abelian
groups, we also study their free-sum subsets.
7
Oliveira, Marcelo Mendes de. "Aplicações da teoria dos grafos à teoria dos grupos." reponame:Repositório Institucional da UFC, 2008. http://www.repositorio.ufc.br/handle/riufc/948.
Full textAbstract:
OLIVEIRA, Marcelo Mendes de; ROGÉRIO, José Robério. Aplicações da teoria dos grafos à teoria dos grupos. 2008. 74 f. Dissertação (mestrado)- Universidade Federal do Ceará, Pós-Graduação em Matemática, Fortaleza-CE, 2008.<br>Submitted by Rocilda Sales (rocilda@ufc.br) on 2011-10-27T13:30:47Z
No. of bitstreams: 1
2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5)<br>Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2011-10-27T13:33:08Z (GMT) No. of bitstreams: 1
2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5)<br>Made available in DSpace on 2011-10-27T13:33:08Z (GMT). No. of bitstreams: 1
2008_dis_mmoliveira.pdf: 349878 bytes, checksum: d6439d5ec62ea18056a42540326a4abe (MD5)
Previous issue date: 2008<br>This report deals with applications of Graph Theory to Group Theory. Once we construct the graph associated to a finite group, we get several interesting results on the group structure by analysing its associated graph with the help of various standard graph-theoretic tools. More precisely, the chromatic and independence numbers of the graph of a finite group allows us to estimate the maximal cardinality of an abelian subgroup of it, as well as the minimal size of a subset of the group, all of whose elements don’t commute in pairs; for finite abelian groups, we also study their free-sum subsets.<br>O propósito desta dissertação é apresentar aplicações da Teoria dos Grafos à Teoria dos Grupos. De posse do grafo associado a um grupo finito, nós obtemos vários resultados interessantes sobre a estrutura do grupo analisando tal grafo à luz de técnicas-padrão da Teoria dos Grafos. Mais precisamente, os números cromático e de independência do grafo de um grupo finito nos permitem estimar a cardinalidade máxima de um subgrupo abeliano do mesmo, bem como o tamanho mínimo possível de um subconjunto do grupo formado por elementos que não comutam dois a dois; no caso de grupos finitos abelianos, nós também estudamos seus subconjuntos livres de somas.
8
Costa, Polyanna Possani da [UNESP]. "Teoria dos grafos e suas aplicações." Universidade Estadual Paulista (UNESP), 2011. http://hdl.handle.net/11449/94358.
Full textAbstract:
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)<br>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<br>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
9
Costa, Polyanna Possani da. "Teoria dos grafos e suas aplicações /." Rio Claro : [s.n.], 2011. http://hdl.handle.net/11449/94358.
Full textAbstract:
Orientador: Thiago de Melo<br>Banca: Elíris Cristina Rizziolli<br>Banca: Luiz Roberto Hartmann Junior<br>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<br>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<br>Mestre
10
Pistori, Hemerson. "Construção automatica de teoria em grafos." [s.n.], 1998. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275973.
Full textAbstract:
Orientador: Jacques Wainer<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-07-24T05:33:11Z (GMT). No. of bitstreams: 1
Pistori_Hemerson_M.pdf: 2405653 bytes, checksum: e58087898fffa17a509c67aba57846e7 (MD5)
Previous issue date: 1998<br>Resumo: Este trabalho apresenta SCOT, um sistema de construção automática de teoria inspirado no programa AM de Douglas Lenat. O AM é conhecido por ter "redescoberto" uma série de conceitos e conjecturas famosos em teoria dos números, aritmética e geometria [Len82]. Apesar do grande interesse despertado por este programa, este linha de pesquisa continua sendo muito pouco explorada. Um dos grandes problemas com o AM é a complexidade do seu conjunto de heurísticas, que é representado através de um sistema de produção contendo 243 regras. Com o SCOT, nós buscamos uma melhor estruturação e organização na representação das heurísticas, facilitando assim a análise e a manipulação das mesmas. A construção automática de teoria é também conhecida como aprendizagem por descoberta ou aprendizagem por exploração<br>Abstract: In this work we present SCOT, an automatic theory construction system inspired on Lenat's program AM. AM "rediscovered" some well-known concepts and conjectures from number theory, arithmetic and geometry [Len82]. Despite the great interest surrounding that program, further contributions to this research line are scarce. One of the main problem with AM is the great complexity of the heuristic set, which is represented as a production system with 243 rules. With SCOT we propose a revival of the "AM's research", emphasizing the clarity and "manipulability" of the heuristic set. Automatic theory construction is also known as learning by discovery or learning by exploration<br>Mestrado<br>Mestre em Ciência da Computação
11
Santos, Philippe Leal Freire dos. "Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos." Universidade Federal do Espírito Santo, 2010. http://repositorio.ufes.br/handle/10/6388.
Full textAbstract:
Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1
Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5)
Previous issue date: 2010-08-23<br>In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature.<br>Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura
12
RODRIGUES, D. B. "Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares." Universidade Federal do Espírito Santo, 2011. http://repositorio.ufes.br/handle/10/4240.
Full textAbstract:
Made available in DSpace on 2016-08-29T15:33:15Z (GMT). No. of bitstreams: 1
tese_4174_.pdf: 432544 bytes, checksum: 56e998c1c8c4b2e3ad13cf3720cfbe5f (MD5)
Previous issue date: 2011-08-29<br>A Teoria Espectral de Grafos (TEG) busca analisar propriedades dos grafos através de matrizes representativas de grafos e seus espectros. De uma propriedade proveniente da TEG, a autocentralidade, surge um importante invariante para o Problema de Isomorfismo de Grafos:
se dois grafos são isomorfos então eles possuem autocentralidades proporcionais. Porém, esta propriedade não pode ser usada diretamente para resolução do Problema de Isomorfismo de Grafos Regulares (PIGR), pois todo grafo regular possui autocentralidades iguais. Este trabalho
apresenta uma estratégia para resolver o PIGR através do uso das autocentralidades para podar a árvore de busca e restringir as possibilidades de mapeamento.
13
Collao, Morales Macarena Alessandra. "Energia dos grafos." Master's thesis, Universidade de Aveiro, 2014. http://hdl.handle.net/10773/13934.
Full textAbstract:
Mestrado em Matemática e Aplicações - Cências da Computação<br>Uma das aplicações mais importantes da Teoria Espetral dos Grafos na área da Química está relacionada com a correspondência muito estreita existente entre a energia _ electron de uma molécula e os valores próprios do grafo que a representa. Esta correspondência por si só é motivação suficiente para o estudo da energia dos grafos. Nesta dissertação, para além de se introduzirem os conceitos e terminologia básicos da Teoria dos Grafos necessários para o estudo da energia (que se define como sendo a soma dos valores absolutos dos valores próprios de um grafo), determinam-se as expressões para a energia de algumas classes de grafos. Adicionalmente, apresentam-se vários majorantes e minorantes para energia dos grafos e, por último estudam-se os grafos hiperenergéticos e hipoenergéticos.<br>One of the most important applications of Spectral Graph Theory
in Chemistry is related with the thin correspondence between the _ electron energy of a molecule and the eigenvalues of the graph which represents the molecule. This correspondence is a sufficient motivation for the study of graph energy. In this work, besides the introduction of concepts and the basic terminology of Graph Theory needed for the study of the energy (which is defined as the sum of the absolute values of the eigenvalues of a graph), mathematical expressions for some classes of graphs are determined. Furthermore, several upper and lower bounds for the energy of graphs are presented and the hyperenergetic and hypoenergetic graphs are analyzed.
14
Barros, Tomas Edson. "Homotopia regular de grafos." [s.n.], 1991. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307360.
Full textAbstract:
Orientador: Jose Carlos de Souza Kiihl<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica<br>Made available in DSpace on 2018-07-13T23:16:04Z (GMT). No. of bitstreams: 1
Barros_TomasEdson_M.pdf: 810196 bytes, checksum: d440e4d7994d16169b2c0b29745be449 (MD5)
Previous issue date: 1991<br>Resumo: Não informado<br>Abstract: Not informed<br>Mestrado<br>Mestre em Matemática
15
Souza, Renato Ferreira de. "Resolução de problemas via teoria de grafos." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/.
Full textAbstract:
O objetivo deste trabalho é introduzir a noção de grafos familiarizando os alunos com um conceito pouco estudado no ensino fundamental e médio. Para isso, foram estudados algumas situações práticas e a resolução por meio de grafos. A apresentação da teoria de grafos é feita utilizando alguns dos problemas clássicos (Pontes de Königsberg e o Problema do caixeiro-viajante) que originaram a teoria tal como é conhecida nos dias de hoje.<br>The aim of this work is to introduce the notion of graphs familiarizing students with a little concept studied in elementary and middle schools. For this, some practical situations were studied and the resolution through graphs. The presentation of the theory of graphs is done using some of the classic problems (The Königsberg bridge problem and The travelling salesman problem) that originated the theory as it is known today.
16
Magalhães, Inês Monteiro Barbedo de. "Determinação de grafos regulares excecionais com recurso a (K, T)-extensões." Doctoral thesis, Universidade de Aveiro, 2015. http://hdl.handle.net/10773/14814.
Full textAbstract:
Doutoramento em Matemática e Aplicações<br>Um grafo excecional é um grafo conexo com menor valor próprio não inferior
a -2 que não é grafo linha generalizado. Esta tese tem como objetivo
apresentar uma nova t´técnica de construção de grafos regulares, com certas
propriedades de natureza combinatória e espetral invariantes, e aplicá-la na
construção de todos os grafos regulares excecionais.
O trabalho encontra-se dividido em duas partes. Na primeira parte descreve-
-se a nova t´técnica de construção de grafos regulares pela introdução de
conjuntos (κ, τ )-regulares, designada de (κ, τ )-extensão, e define-se uma
relação de ordem parcial entre grafos regulares. Mostra-se que a (κ, τ )-
extensão de um grafo se reduz à construção de matrizes de incidência de
um 1-design combinatório, para a qual se definem propriedades que previnem
a construção de grafos isomorfos. Além disso, esta t´técnica permite
a construção de grafos regulares com partição equilibrada e apresentam-se
algumas propriedades espetrais destes grafos. Na segunda parte ´e feita uma
breve descrição das três técnicas conhecidas para a construção dos grafos
regulares excecionais. Posteriormente, aplicam-se as (κ, τ )-extensões na
construção recursiva do conjunto dos grafos regulares excecionais, que se
divide em três camadas. No caso das 1a e 2a camadas, os grafos obtém-se
por (0, 2)-extensões e, no caso da 3a camada, por (1, 3)-extensões. Consequentemente,
conclui-se que, para os grafos das 1a e 2a camadas o número
de independência atinge o majorante de Hoffman e que o conjunto dos
grafos regulares excecionais possui uma estrutura de conjunto parcialmente
ordenado, sendo apresentando o respetivo diagrama de Hasse.<br>An exceptional graph is a connected graph with least eigenvalue greater
than or equal to -2 which is not a generalized line graph. The aim of this
thesis is to present a new technique for the construction of regular graphs,
with certain spectral and combinatorial invariant properties, and to apply it
in the construction of all regular exceptional graphs.
The work is divided into two parts. The first part describes a new construction
technique that introduces (κ, τ )-regular sets in regular graphs, called
(κ, τ )-extension, and defines a partial order between regular graphs. It is
shown that the process of extending a graph is reduced to the construction
of the incidence matrix of a combinatorial 1-design, considering several
rules to prevent the production of isomorphic graphs. Furthermore, this technique
allows the construction of regular graphs with an equitable partition
and some spectral properties of these graphs are presented. The second part
starts with a brief description of the three techniques, previously known for
the construction of regular exceptional graphs. Later, the (κ, τ )-extensions
are applied to the recursive construction of the set of regular exceptional
graphs, which are partitioned in three layers. In the case of the 1st and 2nd
layers, graphs are obtained by (0, 2)-extensions and in the case of 3rd layer,
by (1, 3)-extensions. Therefore, we conclude that, the independence number
attains Hoffman’s upper bound for the graphs of 1st and 2nd layers and
the set of regular exceptional graphs has a partially ordered set structure
whose Hasse diagram is presented.
17
Mendonça, Neto Candido Ferreira Xavier de 1959. "Sobre grafos perfeitos." [s.n.], 1987. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276119.
Full textAbstract:
Orientador : Claudio L. Lucchesi<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação<br>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<br>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<br>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<br>Mestrado<br>Mestre em Ciência da Computação
18
Pocai, Rafael Veiga. "Problemas computacionais em teoria topológica dos grafos." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223/.
Full textAbstract:
Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros.<br>The objective of this text is to study computational problems that emerge from the relation between graphs and bidimensional surfaces, giving special attention to the crossing number problem and graph drawings on books. We present a reduction from MULTICUT to CROSSING NUMBER, in addition to a complexity result on comparability graphs based on a known result about drawings on books.
19
Soares, Francisco Vandiésio Sousa. "Três teoremas interessantes em teoria dos grafos." reponame:Repositório Institucional da UFC, 2017. http://www.repositorio.ufc.br/handle/riufc/24437.
Full textAbstract:
SOARES, F. V. S. Três teoremas interessantes em teoria dos grafos. 2017 57 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017.<br>Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-18T18:40:29Z
No. of bitstreams: 1
2017_dis_fvssoares.pdf: 689594 bytes, checksum: c808d7f662ffa76dbeb23ee14f4bbcf1 (MD5)<br>Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde,
Revisei a Dissertação de FRANCISCO VANDIÉSIO SOUSA SOARES e encontrei alguns erros de formatação que devem ser corrigidos pelo autor. Tais erros estão listados a seguir:
1 – PALAVRAS-CHAVE ( a recomendação da ABNT é que apenas a primeira letras dos termos das palavras-chave estejam em letra maiúscula, salvo se forem nomes próprios,. Assim, o termo “Teorema das Cinco Cores”, e os subsequentes, devem apresentar a seguinte forma: “Teorema das cinco cores”) OBS.: essa regra também serve para os títulos de capítulos, seções e subseções;
2- SUMÁRIO (insira a formatação itálico nas seções terciarias “5.1.1”,”5.1.2”, “5.1.3” do sumário e no interior do trabalho)
3- REFERÊNCIAS (as referências devem seguir o padrão ABNT, o qual especifica que o último sobrenome do autor ou dos autores, caso haja mais de um, deve estar em caixa alta, iniciando a referência, há quatro referências na bibliografia do seu trabalho que que estão incorretas. Assim, referências como:
Hefez, Abramo; Fernandez, Cecilia. Introdução à Álgebra Linear (COLEÇÃO PROFMAT). Rio de Janeiro: SBM, 2012
Dever ser alteradas para:
HEFEZ, Abramo; FERNANDEZ, Cecilia. Introdução à Álgebra Linear (COLEÇÃO PROFMAT). Rio de Janeiro: SBM, 2012
Em caso de dúvidas, consulte as referências dos em autores em livros ou outras fontes confiáveis.
Atenciosamente,
on 2017-07-19T16:21:14Z (GMT)<br>Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-24T13:27:51Z
No. of bitstreams: 1
2017_dis_fvssoares.pdf: 692235 bytes, checksum: 4b683f2b5e481f09fae4126e6f9b1838 (MD5)<br>Rejected by Rocilda Sales (rocilda@ufc.br), reason: Boa tarde,
O autor esqueceu de colocar o item Referências na folha do Sumário.
Rocilda on 2017-07-25T15:51:27Z (GMT)<br>Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-25T18:16:18Z
No. of bitstreams: 1
2017_dis_fvssoares.pdf: 692486 bytes, checksum: e2919b69f55bc8ab3f42aaab72795274 (MD5)<br>Rejected by Rocilda Sales (rocilda@ufc.br), reason: Bom dia,
O item Referências fica na mesma margem da Conclusão. on 2017-07-26T13:55:59Z (GMT)<br>Submitted by Jessyca Silva (jessyca@mat.ufc.br) on 2017-07-26T15:04:09Z
No. of bitstreams: 1
2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5)<br>Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-07-28T14:58:07Z (GMT) No. of bitstreams: 1
2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5)<br>Made available in DSpace on 2017-07-28T14:58:08Z (GMT). No. of bitstreams: 1
2017_dis_fvssoares.pdf: 692491 bytes, checksum: 692aded24df0a0677bf540d9d90d0d84 (MD5)
Previous issue date: 2017-07<br>The results presented in this work constitute themselves in particular topics of Graph
Theory. One of the great advantages of the study of graphs lies in the fact that, besides
being mathematically interesting objects, graphs appear in a multitude of practical ap-
plications. Indeed, on the one hand, the statements of most of the famous problems in
Graph Theory can be easily explained to an average high school student; on the other,
the roots of those problems, most of the times, lie in important practical applications of
the theory to such diverse areas as Physics, Chemistry, Biology, Electrical Engineering
and Operations Research. In this work we restrict ourselves to the discussion of the spe-
cific problems in Graph Theory: the Five Colors Theorem, which is a problem on vertex
coloring of planar graphs, the Art Gallery Theorem, which is a result on Extremal Graph
Theory, and the Friedship Theorm, which is an amazingly beautiful result in Algebraic
Graph Theory. We present a structured and detailed discussion of such results, in the
hope that their aesthetic appeal serve as an exhortation for the inclusion of the rudiments
of Graph Theory in High School curriculum.<br>Os resultados apresentados neste trabalho são tópicos particulares de Teoria dos Grafos. Uma das grandes vantagens do estudo de grafos reside no fato de que, além de serem objetos matematicamente interessantes, grafos aparecem em uma miríade de aplicações práticas. De fato, por um lado, a maioria dos enunciados dos problemas famosos de Teoria dos Grafos pode ser facilmente explicada a um estudante da escola básica; por outro, as raízes de tais problemas, o mais das vezes, repousam em importantes aplicações práticas da teoria a áreas tão diversas quanto Física, Química, Biologia, Engenharia Elétrica e Pesquisa Operacional. Neste trabalho, vamos nos restringir à discussão de três problemas específicos de Teoria dos Grafos: o Teorema das Cinco Cores, que é um problema de coloração de vértices de um grafo planar, o Teorema da Galeria de Arte, que é um resultado de Teoria Extremal de Grafos e o Teorema da Amizade, que é um belíssimo resultado da Teoria Algébrica dos Grafos. Apresentamos tais resultados em detalhe e estruturadamente, na expectativa de que seus apelos estéticos sirvam de exortação à
inclusão dos rudimentos de Teoria dos Grafos nos currículos do Ensino Médio.
20
Vulcani, Renata de Lacerda Martins 1973. "Grafos eulerianos e aplicações." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/306826.
Full textAbstract:
Orientadores: Celia Picinin de Mello, Anamaria Gomide<br>Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica<br>Made available in DSpace on 2018-08-26T19:50:54Z (GMT). No. of bitstreams: 1
Vulcani_RenatadeLacerdaMartins_M.pdf: 2431212 bytes, checksum: 702947f1e783d410ef77eb0234852d6a (MD5)
Previous issue date: 2015<br>Resumo: Neste trabalho apresentamos uma breve introdução à teoria dos grafos, elucidando alguns conceitos básicos e destacando grafos eulerianos. Usamos o conceito de grafos eulerianos para resolver alguns passatempos e jogos conhecidos. Finalizamos apresentando algumas aplicações que envolvem grafos que não são necessariamente eulerianos<br>Abstract: In this work we present a brief introduction to graph theory, explaining some basic concepts and highlighting eulerians graphs. We use the concept of eulerians graphs to solve some well known puzzles and games. We finalize by presenting some applications involving graphs that are not necessarily eulerians<br>Mestrado<br>Matemática em Rede Nacional<br>Mestra
21
Miranda, Alberto Alexandre Assis. "Grafos pfaffianos e problemas relacionados." [s.n.], 2009. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275836.
Full textAbstract:
Orientador: Claudio Leonardo Lucchesi<br>Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-08-15T06:54:51Z (GMT). No. of bitstreams: 1
Miranda_AlbertoAlexandreAssis_D.pdf: 571362 bytes, checksum: bd3600cbf8fe0c2875d8e5c60b6abfd3 (MD5)
Previous issue date: 2009<br>Resumo: A área de grafos Pfaffianos apresenta muitos problemas em aberto. Nesta tese resolvemos dois problemas sobre grafos Pfaffianos. O primeiro problema resolvido é a obtenção de um algoritmo polinomial para reconhecimento de grafos quase-bipartidos Pfaffianos. Além disso, estendemos tanto o algoritmo como a caracterização de grafos quase-bipartidos Pfaffianos para a classe dos grafos meio-bipartidos. O segundo resultado é a obtencão de vários resultados estruturais básicos sobre grafos k-Pfaffianos. Utilizando esses resultados, obtivemos um contra-exemplo para a conjectura de Norine, que afirma que o número Pfaffiano de todo grafo é uma potência de quatro: apresentamos um grafo cujo numero Pfaffiano é 6<br>Abstract: The area of Pfaffian graphs contains many open problems. In this thesis, we solve two problems related to Pfaffian graphs. The first result is a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. Moreover, we extend this algorithm and the characterization of near-bipartite Pfaffian graphs to the class of half-bipartite graphs. The second result is obtaining several basic structural results concerning k-Pfaffian graphs. Using these results, we obtained a counter-example to Norine's conjecture, which states that the Pfaffian number of a graph is always a power of four: we present a graph whose Pfaffian number is 6<br>Doutorado<br>Matematica Discreta e Combinatoria<br>Doutor em Ciência da Computação
22
Lima, Carlos Laercio Gomes de. "Um estudo sobre teoria dos grafos e o teorema das quatro cores." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/55/55136/tde-26112016-112047/.
Full textAbstract:
Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas.<br>In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.
23
Stecca, Flavio de Freitas. "Coloração de arestas em grafos indiferença." [s.n.], 2003. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276337.
Full textAbstract:
Orientador: João Meidanis<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica<br>Made available in DSpace on 2018-08-03T20:15:11Z (GMT). No. of bitstreams: 1
Stecca_FlaviodeFreitas_M.pdf: 2291737 bytes, checksum: 854734e6990e1e125c61b7312d5f1056 (MD5)
Previous issue date: 2003<br>Resumo: Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores suficientes para pintar suas arestas) X' é igual a .6 ( G) . Se X' = .6(G) + 1, o grafo pertence à Classe 2. Um grafo é dito overfull se .6(G) l_J < m, onde nem são o número de vértices e o número de arestas, respectivamente. Grafos neighborhood overfull são grafos que têm um vértice de grau máximo cuja vizinhança induz um subgrafo overfull. Grafos indiferença overfull ou neighborhood overfull pertencem à Classe 2. Apresentaremos uma breve compilação de resultados de pesquisas. Dois destes resultados mostram que grafos indiferença com grau máximo ímpar e grafos indiferença reduzidos pertencem à Classe 1, porém o problema ainda está em aberto para um grafo indiferença qualquer. Abordamos o problema criando um modelo de programação linear para coloração de arestas. Implementamos um gerador que nos permitiu gerar grafos indiferença de dife-rentes estruturas. Estes grafos tiveram suas arestas coloridas através de programação linear. Definimos um tipo especial de grafo indiferença denominado grafo indiferença semi-universal. Criamos um método que permite cobrir um grafo indiferença com grafos indiferença semi-universais. Mostramos que resolver o problema para um grafo indife-rença qualquer equivale a estender certas colorações parciais para um grafo indiferença semi-universal qualquer. Reforçamos a conjectura de que todos os grafos indiferença não neighborhood overfull são Classe 1, através de testes práticos em milhares de grafos indi-ferença<br>Abstract: This dissertation is on the subject of edge coloring restricted to indifference graphs. Vi-zing's theorem states that any graph can be edge-colored with .6. or .6. + 1 colors. Graphs are said to be Class 1 if their chromatic index (minimum number of colors required to produce an edge-coloring) X ' equals .6.( G). If X ' = .6.( G) + 1 the graph is said to be Class 2. A graph is overfull if .6. (G) l _ J < m, where n and m are the number of vertices and number of edges, respectively. Graphs are said to be neighborhood overfull if they have a maximum-degree vertex whose neighborhood induces an overfull subgraph. Overfull and neighborhood overfull indifference graphs are Class 2. vVe will show a brief compilation of research results. Two of these results show that indifference graphs with odd maximum degree and reduced indifference graphs are Class 1, however the problem is open for a generic interference graph. The approach used for the problem was the creation of a linear programming mo dei for edge coloring. A graph generator program that allowed creation of indifference graphs with different structures was implemented. These graphs were edge colored using linear programming. We defined a special type of graph called semi-universal indifference graph. We created a method for covering an indifference graph with semi-universal indifference graphs. We show that solving the problem for indifference graphs is equivalent to ex-tending a partial edge coloring in a semi-universal indifference graph. We reinforce the conjecture that says that all indifference graphs not neighborhood overfull are Class 1, through practical tests in thousands of indifference graphs<br>Mestrado<br>Mestre em Ciência da Computação
24
Ortiz, S. Alvaro. "Modelos del Lugar Central y Teoria de Grafos." Economía, 2012. http://repositorio.pucp.edu.pe/index/handle/123456789/117461.
Full text
25
Matos, Ilda Maria Duarte de. "Teoria dos grafos no ensino básico e secundário." Master's thesis, Universidade de Aveiro, 2013. http://hdl.handle.net/10773/12083.
Full textAbstract:
Mestrado em Matemática para Professores<br>Nesta dissertação apresentam-se algumas noções gerais sobre Teoria dos Grafos e apresentam-se alguns problemas desta teoria, abordados em atividades nos diferentes níveis de ensino básico e secundário, bem como algoritmos para a sua resolução. Os problemas abordados são: o problema do caminho mais curto, o problema da árvore abrangente de custo mínimo, determinação de um circuito de Euler ou de um ciclo hamiltoniano, nos quais se enquadram os problemas do carteiro chinês e do caixeiro viajante, e as colorações de grafos. Por último, apresentam-se algumas aplicações da Teoria dos Grafos em tarefas apresentadas aos alunos do ensino básico e secundário e é feita uma análise sobre a importância da sua inclusão no programa da disciplina de Matemática nos diferentes ciclos de ensino.<br>In this dissertation we present some general notions of graph theory and some well known problems of this theory as well as algorithms to solve them. The problems considered here are: the shortest path problem, the minimum spanning tree, the determination of eulerian circuits and hamiltonian cycles, in particular, the problems of the Chinese postman and the travelling salesman, and the colorations of graphs. By last, some applications of graph theory such as problems given to students of different stages of education are presented and the importance of including theory of graphs in the program of mathematics in the different stages of education is highlighted.
26
Carvalho, Elias César Araújo de. "Particionamento de grafos de aplicações e mapeamento em grafos de arquiteturas heterogêneas." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2002. http://hdl.handle.net/10183/4206.
Full textAbstract:
Esta pesquisa visa a modelagem de clusters de computadores, utilizando um modelo analítico simples que é representado por um grafo valorado denominado grafo da arquitetura. Para ilustrar tal metodologia, exemplificou-se a modelagem do cluster Myrinet/SCI do Instituto de Informática da UFRGS, que é do tipo heterogêneo e multiprocessado. A pesquisa visa também o estudo de métodos e tecnologias de software para o particionamento de grafos de aplicações e seu respectivo mapeamento sobre grafos de arquiteturas. Encontrar boas partições de grafos pode contribuir com a redução da comunicação entre processadores em uma máquina paralela. Para tal, utilizou-se o grafo da aplicação HIDRA, um dos trabalhos do GMCPAD, que modela o transporte de substâncias no Lago Guaíba. Um fator importante é o crescente avanço da oferta de recursos de alto desempenho como os clusters de computadores. Os clusters podem ser homogêneos, quando possuem um arquitetura com nós de mesma característica como: velocidade de processamento, quantidade de memória RAM e possuem a mesma rede de interconexão interligando-os. Eles também podem ser heterogêneos, quando alguns dos componentes dos nós diferem em capacidade ou tecnologia. A tendência é de clusters homogêneos se tornarem em clusters heterogêneos, como conseqüência das expansões e atualizações. Efetuar um particionamento que distribua a carga em clusters heterogêneos de acordo com o poder computacional de cada nó não é uma tarefa fácil, pois nenhum processador deve ficar ocioso e, tampouco, outros devem ficar sobrecarregados Vários métodos de particionamento e mapeamento de grafos foram estudados e três ferramentas (Chaco, Jostle e o Scotch) foram testadas com a aplicação e com a arquitetura modeladas. Foram realizados, ainda, vários experimentos modificando parâmetros de entrada das ferramentas e os resultados foram analisados. Foram considerados melhores resultados aqueles que apresentaram o menor número de corte de arestas, uma vez que esse parâmetro pode representar a comunicação entre os processadores de uma máquina paralela, e executaram o particionamento/mapeamento no menor tempo. O software Chaco e o software Jostle foram eficientes no balanceamento de carga por gerarem partições com praticamente o mesmo tamanho, sendo os resultados adequados para arquiteturas homogêneas. O software Scotch foi o único que permitiu o mapeamento do grafo da aplicação sobre o grafo da arquitetura com fidelidade, destacando-se também por executar particionamento com melhor qualidade e pela execução dos experimentos em um tempo significativamente menor que as outras ferramentas pesquisadas.
27
Takahama, Mariana Thieme Moraes [UNESP]. "Grafos em superfícies." Universidade Estadual Paulista (UNESP), 2014. http://hdl.handle.net/11449/123144.
Full textAbstract:
Made available in DSpace on 2015-05-14T16:52:58Z (GMT). No. of bitstreams: 0
Previous issue date: 2014-12-12Bitstream added on 2015-05-14T16:59:37Z : No. of bitstreams: 1
000829398.pdf: 735180 bytes, checksum: 47660f344914d561b93a77ad264e4c4b (MD5)<br>O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin<br>The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin
28
Takahama, Mariana Thieme Moraes. "Grafos em superfícies /." Rio Claro, 2014. http://hdl.handle.net/11449/123144.
Full textAbstract:
Orientador: Alice Kimie Miwa Libardi<br>Banca: Thiago de Melo<br>Banca: Flávia Souza Machado da Silva<br>Resumo: O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin<br>Abstract: The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin<br>Mestre
29
Braga, Marília Dias Vieira. "Grafos de sequencias de DNA." [s.n.], 2000. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275909.
Full textAbstract:
Orientador: João Meidanis<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-07-27T09:25:12Z (GMT). No. of bitstreams: 1
Braga_MariliaDiasVieira_M.pdf: 1562326 bytes, checksum: e2bde728b7016815f56abc118722d3d4 (MD5)
Previous issue date: 2000<br>Resumo: Este trabalho está relacionado à Biologia Computacional, uma área da Ciência da Computação cuja existência é motivada pela busca de métodos computacionais que resolvam ou ajudem a resolver problemas de origem biológica. Esta ciência tem sido largamente utilizada no âmbito da genética, contribuindo essencialmente no seqüenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma família de problemas denominada Minimum Contig Problems (MCP) [4], que é um modelo teórico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhança com um problema de grafos denominado Cobertura de Vértices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentação de provas formais da NP-dificuldade dos problemas de MCP. A partir daí, complementamos o nosso trabalho propondo um algoritmo de aproximação para instâncias restritas de cada problema de MCP.<br>Abstract: Not informed.<br>Mestrado<br>Mestre em Ciência da Computação
30
Alves, Robson Piacente. "Coloração de grafos e aplicações." reponame:Repositório Institucional da UFSC, 2015. https://repositorio.ufsc.br/xmlui/handle/123456789/160734.
Full textAbstract:
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.<br>Made available in DSpace on 2016-04-19T04:14:50Z (GMT). No. of bitstreams: 1
337662.pdf: 4681558 bytes, checksum: 8891d71ebb8eadcc421b3f7727965490 (MD5)
Previous issue date: 2015<br>O objetivo deste trabalho é o estudo de grafos aplicado à coloração de vértices e arestas. Para tal, faremos uma breve apresentação sobre conceitos básicos de grafos, bem como a importância de suas aplicações.Buscamos aqui a resolução de problemas envolvendo coloração e sua possível aplicação matemática na educação básica.<br><br>Abstract : The objective of this work is the study of graphs applied to colouring of vertex and edges. To do this, we will give a brief presentation about basics concepts of graphs, as well as the importance of its applications.We seek here the solution of the problems involving colouring and its possible mathematical application in basic education.
31
Gonçalves, Andreia Leite. "Grafos: Aplicações ao Jogo." Master's thesis, Universidade Portucalense, 2007. http://hdl.handle.net/11328/539.
Full textAbstract:
Dissertação de Mestrado em Matemática.<br>Essencialmente este trabalho pretende fazer uma abordagem de problemas de
carácter lúdico cuja resolução possa ser relacionada com a Teoria de Grafos. A
Teoria de Grafos é talvez, de entre as teorias matemáticas, aquela que mais se pode
usar com aplicações lúdicas, com o propósito de resolver ou compreender jogos. É
uma teoria relativamente recente, nascida no século XVIII, e que entrou nos
programas do ensino secundário no fim do século XX. Duas razões importantes para
essa entrada: a grande aplicação prática mas também a possibilidade de introduzir os
conceitos teóricos através de utilização de jogos. Assim, pretende-se com este
trabalho percorrer vários jogos onde a utilização de grafos é notória. Como veremos
na parte histórica, o nascimento da Teoria de Grafos deve-se a um problema sem
interesse matemático, apenas a um entretimento, o problema das pontes de
Koenigsberg.
No Capítulo 1 é feita uma introdução histórica, desenvolvendo já resultados
importantes que foram sendo estabelecidos durante os séculos XVIII, XIX e XX.
Desde Euler, passando por Hamilton e até mais recentemente a demonstração do
teorema das quatro cores por Appel e Haken. No Capítulo 2 é feito um estudo de
carácter pedagógico realçando a componente didática do Jogo, didática essa que se
fez questão que estivesse presente nesta tese. No capítulo 3 é então desenvolvido o
aspecto matemático, neste particular a Teoria de Grafos, mediante a apresentação de
estratégias para abordar alguns jogos que servem como exemplos.<br>Orientação: Prof.º Doutor António Pascoal.
32
Silva, Leila Maciel de Almeida e. "Fluxos inteiros em grafos." [s.n.], 1991. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275927.
Full textAbstract:
Orientador: Claudio Leonardo Lucchesi<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação<br>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<br>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).<br>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).<br>Mestrado<br>Mestre em Ciência da Computação
33
Perez, Lozada Luis Arturo. "Topicos na classe dos grafos clique." [s.n.], 1996. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276129.
Full textAbstract:
Orientador: Celia Picinin de Mello<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação<br>Made available in DSpace on 2018-07-21T04:18:30Z (GMT). No. of bitstreams: 1
PerezLozada_LuisArturo_M.pdf: 2819086 bytes, checksum: a6afd3f6ffb1a048ced4a84733ff7e66 (MD5)
Previous issue date: 1996<br>Resumo: Uma dique de um grafo G é um conjunto de vértices que induz um subgrafo completo maximal de G. O grafo dique K(G) de um grafo G é o grafo interseção das diques de G. Indutivamente define-se o i-ésimo grafo dique iterado de G como Ki(G) = K(Ki-l(G)). Apresenta-se de maneira organizada uma compilação de pesquisas realizadas nos últimos anos a respeito de diversos tópicos na dasse dos grafos dique, entre eles: o estudo das propriedades dos grafos dique de conhecidas dasses de grafos; a convergência; divergência e diâmetro dos grafos clique-iterados<br>Abstract: A clique of a graph G is a set of vertices that induce a maximal complete subgraph of G. The dique graph K (G) of a graph G is the intersection graph of the diques of G. Inductively we denote the ith iterated dique graph of G by Ki(G) = X(Ki-l(G)). We wiil present in an organized way a compilation of investigations made in the last years with respect to the several topics on this class of graphs, such as: the study of proprieties of dique graphs of weil-known class of graphs; convergence; divergence and diameters of iterated dique graphs<br>Mestrado<br>Mestre em Ciência da Computação
34
Gonçalves, Alexandre Casassola. "Torneios normais." [s.n.], 1997. http://repositorio.unicamp.br/jspui/handle/REPOSIP/307358.
Full textAbstract:
Orientador: Jose Carlos de Souza Kiihl<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica<br>Made available in DSpace on 2018-07-22T06:14:00Z (GMT). No. of bitstreams: 1
Goncalves_AlexandreCasassola_M.pdf: 692699 bytes, checksum: 1b9c1637640944dd47077382ccdbf867 (MD5)
Previous issue date: 1997<br>Resumo: Não informado.<br>Abstract: Not informed.<br>Mestrado<br>Mestre em Matemática
35
Roggia, Karina Girardi. "Categoria de grafos parciais com homomorfismos totais teoria e aplicações." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2005. http://hdl.handle.net/10183/5616.
Full textAbstract:
O conceito de parcialidade e importante em diversas áreas como a Matemática e a Ciência da Computação; ele pode ser utilizado, por exemplo, para expressar computações que não terminam e para definir funções recursivas parciais. Com rela cão a grafos, categorias de homomorfismos parciais são comuns (por exemplo, em gramáticas de grafos com a técnica de single-pushout). Este trabalho propõe uma abordagem diferente: a parcialidade é usada na estrutura interna dos objetos (não nos morfismos).Istoéfeito utilizando uma extensão do conceito de Categoria das Setas, chamada de Categoria das Setas Parciais. E definida entãoa categoria Grp de grafos parciais(tais que arcos podem possuir ou não vértices de origem e/ou destino) e homomorfismos totais.A generalização deste modelo resulta em categorias de grafos parciais internos.Émostrado que Grp é bicompleta e, se C é um topos, a categoria dos grafos parciais internos a C é cocompleta. Grafos parciais podem ser utilizados para definir modelos computacionais tais como autômatos. Uma categoria de Autômatos Parciais, denominada Autp, é construída a partir da categoria de Grafos Parciais. Usando uma extensão de composição de spans de grafos para autômatos, chamada de Composição de Transições, e possível definir as computações de autômatos. Brevemente, uma composição de transi cões de dois autômatos parciais resulta em um autômato parcial onde cada transição representa um caminho de tamanho dois (entre vértices), tal que a primeira metade é uma transição do primeiro autômato e a segunda metade é uma transição do segundo. É possível compor um autômato consigo mesmo diversas vezes; no caso de n sucessivas composições de transições, pode-se obter as palavras da linguagem aceita pelo autômato que necessitam de n+1 passos de computação nos arcos que não possuem origem e nem destino definidos do autômato parcial resultante.
36
Carvalho, Marcelo H. "Decomposição otima em orelhas para grafos matching covered." [s.n.], 1996. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276045.
Full textAbstract:
Orientador: Claudio L. Lucchesi<br>Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-07-22T14:37:46Z (GMT). No. of bitstreams: 1
Carvalho_MarceloH_D.pdf: 3472839 bytes, checksum: 604447ee0052ba3daa1a6900cea3c290 (MD5)
Previous issue date: 1997<br>Resumo: O assunto do qual se trata este trabalho se insere na área de teoria dos grafos, e mais especificamente de grafos matching covered, que são grafos conexos em que toda aresta pertence a um emparelhamento perfeito. L. Lovász desenvolveu toda a base da teoria dos grafos matching covered e, como conseqüência, obteve uma caracterização para o matching lattice. Desta caracterização foi possível obter uma prova para uma relaxação da conjectura de Tutte que generaliza o problema das quatro cores. Existem dois procedimentos de decomposição de grafos matching covered que são fundamentais: um deles é a decomposição em cortes justos e o outro é a decomposição em orelhas. Para uma decomposição em orelhas podem ser usadas orelhas simples ou duplas. Uma importante questão é determinar o número mínimo de orelhas duplas de uma decomposição em orelhas de um grafo matching covered. Neste trabalho apresentamos uma resposta para esta questão. Apresentamos também duas conseqüências desta solução: uma delas é que existe uma base para o matching lattice formada apenas por emparelhamentos perfeitos, e a outra é uma caracterização para o Lin(M, Z2 ). Esta última nos permite obter uma prova para outra relaxação da conjectura de Tutte.<br>Abstract: Matching covered graphs are connected graphs in which every edge lies in a perfect matching. The base of this theory was developed by L. Lovász, and as consequence, a characterization to the matching lattice was obtained. Then it was possible to obtain a proof for a relaxation of a conjecture of Tutte, which is related to the four colors problem. There are two main 'decomposition procedures of a matching covered graph: tight cuts decomposition and ear decomposition. For ear decomposition one can use single or double ears. One important question asks about the minimum number of double ears of any ear decomposition of such graphs. This work gives an answer to this question It is also presented two consequences: that there is a base for the matching lattice formed solely by incidence vectors of perfect matching, and a characterization to Lin (M, Z2 ) which gives a proof to an other relaxation of the Tutte conjecture.<br>Doutorado<br>Doutor em Ciência da Computação
37
Carnassale, Mauro. "GFC - Uma ferramenta multilinhagem para geração de grafo de programa." [s.n.], 1991. http://repositorio.unicamp.br/jspui/handle/REPOSIP/261536.
Full textAbstract:
Orientador : Mario Jino<br>Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica<br>Made available in DSpace on 2018-07-13T23:27:16Z (GMT). No. of bitstreams: 1
Carnassale_Mauro_M.pdf: 4907860 bytes, checksum: 9ae042cdd1fd83ffb5b10d25f8855a73 (MD5)
Previous issue date: 1991<br>Resumo: Grafos de programa têm sido utilizados há muito tempo e, apesar de serem um conceito tradicional, sua aplicabilidade atual é grande e crescente. Muitas ferramentas e alguns ambientes utilizam-se dessa representação da estrutura lógica do Programa para atingirem seus objetivos. O propósito deste trabalho é apresentar a arquitetura,
aspectos fundamentais de implementação e principais aplicações de uma ferramenta que produz o grafo de programa a partir de programas escritos em diversas linguagens procedimentais. Os Programas são t raduzidos para uma linguagem intermediária, denominada LI, a partir da qual obtêm-se o grafo de programa e outros produtos relevantes. A ferramenta tambem aceita programas escritos diretament e em LI. Sua finalidade principal é apoiar outras ferramentas ou aplicações que se utilizam do grafo de programa<br>Abstract; Not informed.<br>Mestrado<br>Mestre em Engenharia Elétrica
38
Andelic, Milica. "Resultados espectrais relacionados com a estrutura dos grafos." Doctoral thesis, Universidade de Aveiro, 2011. http://hdl.handle.net/10773/7212.
Full textAbstract:
Doutoramento em Matemática<br>Nesta tese são estabelecidas novas propriedades espectrais de grafos com
estruturas específicas, como sejam os grafos separados em cliques e
independentes e grafos duplamente separados em independentes, ou ainda
grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados
em cliques e independentes são estudados, tendo como objectivo limitar o
maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor
próprio é aplicada para obter alguns majorantes e minorantes do índice do
espectro Laplaciano sem sinal dos grafos separados em cliques e
independentes bem como sobre o índice dos grafos duplamente separados em
independentes. São fornecidos alguns resultados computacionais de modo a
obter uma melhor percepção da qualidade desses mesmos extremos.
Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma
estrela complementar para um valor próprio não-principal $. Além disso, é
mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela
complementares construímos, em alguns casos, os respectivos grafos
maximais. Uma caracterização dos grafos separados em cliques e
independentes que envolve o índice e as entradas do vector principal é
apresentada tal como um majorante do número da estabilidade dum grafo
conexo.<br>In this thesis new spectral properties of graphs with a specific structure (as split
graphs, nested split and double split graphs as well as graphs with (κ,τ)-regular
sets) are deduced. Some invariants of nested split graphs are studied in order
to bound the largest eigenvalue of signless Laplacian spectra. The eigenvalue
technique is applied to obtain some lower and upper bounds on the index of
signless Laplacian spectra of nested split graphs as well as on the index of
double nested graphs. Computational results are provided in order to gain a
better insight of quality of these bounds. The graphs having a (κ,τ)-regular set
which induces a star complement for a non-main eigenvalue $ are studied.
Furthermore, it is shown that $= κ-τ. By the star complement technique, in
some cases, maximal graphs with desired properties are constructed. A
spectral characterization of families of split graphs involving its index and the
entries of the principal eigenvector is given as well as an upper bound on the
stability number of a connected graph.
39
Morgado, Andreia Cristina Dias. "Quadrados latinos e grafos." Master's thesis, Universidade de Aveiro, 2012. http://hdl.handle.net/10773/11191.
Full textAbstract:
Mestrado em Matemática e Aplicações<br>O objetivo principal desta dissertação é o estudo da relação entre Quadrados Latinos e Grafos. Demonstra-se que o tipo e as características do Grafo refletem-se no tipo e características do Quadrado Latino associado.
No primeiro capítulo são apresentados os conceitos introdutórios e as principais características dos Quadrados Latinos.
As aplicações dos Quadrados Latinos à Teoria dos Grupo são tratadas no segundo capítulo.
Para finalizar, no terceiro capítulo, são apresentados alguns conceitos introdutórios da Teoria dos Grafos, sendo estes de extrema importância para a concretização do quarto capitulo onde se encontra a parte principal do trabalho, isto é, a relação entre Quadrados Latinos e Grafos.<br>The main objective of this dissertation is the study of the relationship between Latin squares and graphs. It is shown that the type and characteristics of the graph are reflected on the type and characteristics of the associated Latin square.
The first chapter presents introductory concepts and the main characteristics of Latin squares.
The applications of Latin squares to the group theory are discussed in the second chapter.
Finally, in the third chapter, we present some introductory concepts of Graph Theory, which are extremely important to the achievement of the fourth chapter where is the main part of the work, i.e., the relationship between Latin squares and graphs.
40
Takahashi, Marcia Tomie. "Contribuições ao estudo de grafos fuzzy : teoria e algoritmos." [s.n.], 2004. http://repositorio.unicamp.br/jspui/handle/REPOSIP/261247.
Full textAbstract:
Orientadores: Akebo Yamakami<br>Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação<br>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<br>Doutorado
41
Müller, Jonathan Gil 1992, Tânia 1953 Baier, and Universidade Regional de Blumenau Programa de Pós-Graduação em Ensino de Ciências Naturais e. Matemática. "Teoria dos grafos para o ensino fundamental :desafios lúdicos /." reponame:Biblioteca Digital de Teses e Dissertações FURB, 2015. http://www.bc.furb.br/docs/DS/2015/360431_1_1.pdf.
Full textAbstract:
Orientador: Tânia Baier.<br>Com.: Produto educacional: Caderno do estudante: Teoria dos grafos para o ensino fundamental: desafios lúdicos.<br>Dissertação (Mestrado em Matemática) - Universidade Regional de Blumenau, Centro de Ciências Exatas e Naturais, Programa de Pós-Graduação em Ensino de Ciências Naturais e Matemática, Blumenau,
42
MAURI, R. "Uma Abordagem da Teoria de Grafos no Ensino Médio." Universidade Federal do Espírito Santo, 2013. http://repositorio.ufes.br/handle/10/4816.
Full textAbstract:
Made available in DSpace on 2016-08-29T15:36:14Z (GMT). No. of bitstreams: 1
tese_6790_TCC - Rone Mauri - Uma Abordagem da Teoria de Grafos no Ensino Médio.pdf: 1611736 bytes, checksum: 931bb98f4a27664e1e2156138fe2c033 (MD5)
Previous issue date: 2013-08-16<br>Este trabalho traz uma proposta para abordar a Teoria de Grafos, conteúdo que raramente é lecionado no ensino médio em escolas públicas, e objetiva trabalhar o tema através de resolução de problemas, oportunizando aos educandos a participação efetiva na construção de argumentos e desafiando-os a buscarem soluções, instigando a curiosidade e exigindo deles uma postura que os leva a tomarem decisões, favorecendo o surgimento de respostas criativas e desenvolvendo habilidades concernentes àquelas propostas no Currículo Básico Comum da rede estadual de ensino. Esta proposta traz dois capítulos, sendo o primeiro para introduzir o tema na 2ª série do ensino médio, e o segundo, para retomar conceitos já vistos no primeiro e introduzir novos conceitos aos alunos da 3ª série do ensino médio. Os dois capítulos são constituídos de problemas, tanto para introduzir conceitos e resultados quanto para aplicá-los, trazendo suas soluções e, em alguns casos, comentários dirigidos aos professores.
43
Mauri, Rone. "Uma abordagem da Teoria de Grafos no Ensino Médio." Universidade Federal do Espírito Santo, 2013. http://repositorio.ufes.br/handle/10/6471.
Full textAbstract:
Made available in DSpace on 2016-12-23T14:34:47Z (GMT). No. of bitstreams: 1
Rone Mauri.pdf: 1614722 bytes, checksum: 9403a819f35ef1a182bd8772f7204a6f (MD5)
Previous issue date: 2013-08-16<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>This work shows a proposal to approach Graph Theory, which is rarely taught at public high schools, and looks for working the theme through the resolution of problems, providing opportunities to the pupil for effective participation on the building of arguments and challenging them to search for solutions, instigating the curiosity and requiring from them an attitude that lead to take decisions, favoring the emergence of creative answers and developing abilities concerning to those proposed on the Common Basic Curriculum of the state public high school. This proposal is described in two chapters, being the first one to introduce the theme on the second grade of high school, and the second one, to retake concepts already seen on the first one and introduce new concepts to the students of the third grade of high school. Both chapters are composed of problems, to introduce concepts and results as much to apply them, bringing their solutions and, in some cases, commentaries to the teachers<br>Este trabalho traz uma proposta para abordar a Teoria de Grafos, conteúdo que raramente é lecionado no ensino médio em escolas públicas, e objetiva trabalhar o tema através de resolução de problemas, oportunizando aos educandos a participação efetiva na construção de argumentos e desafiando-os a buscarem soluções, instigando a curiosidade e exigindo deles uma postura que os leva a tomarem decisões, favorecendo o surgimento de respostas criativas e desenvolvendo habilidades concernentes àquelas propostas no Currículo Básico Comum da rede estadual de ensino. Esta proposta traz dois capítulos, sendo o primeiro para introduzir o tema na 2ª série do ensino médio, e o segundo, para retomar conceitos já vistos no primeiro e introduzir novos conceitos aos alunos da 3ª série do ensino médio. Os dois capítulos são constituídos de problemas, tanto para introduzir conceitos e resultados quanto para aplicá-los, trazendo suas soluções e, em alguns casos, comentários dirigidos aos professores
44
Gonçalves, Diego Rodrigues. "Um estudo introdutório da Teoria de Grafos através de matrizes /." Rio Claro, 2014. http://hdl.handle.net/11449/108817.
Full textAbstract:
Orientador: Thiago de Melo<br>Banca: Elíris Cristina Rizziolli<br>Banca: Tomas Edson de Barros<br>Resumo: O objetivo deste trabalho é apresentar alguns resultados elementares de Álgebra Linear e relacioná-los com a Teoria de Grafos, por meio de exemplos, sempre que possível. A ferramenta básica para isso é a teoria de matrizes<br>Abstract: The aim of this work is to present some elementary results from Linear Algebra and to relate them with Graph Theory, making use of examples if possible<br>Mestre
45
Cavalet, Lilian. "Índices de grafos livres de K s,t." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/180762.
Full text
46
Costa, Maria Elena Nunes Oliveira. "Grafos fortemente regulares e combinatória." Master's thesis, Universidade de Aveiro, 2011. http://hdl.handle.net/10773/9845.
Full textAbstract:
Mestrado em Matemática e Aplicações<br>Nesta dissertação apresenta-se uma breve introdução à teoria dos grafos, designs combinatórios e geometrias finitas e estabelecem-se algumas relações entre estas estruturas combinatórias. No contexto dos grafos, é dada ênfase aos grafos fortemente regulares e às propriedades da matriz de adjacência. Nos designs combinatórios considera-se a construção de 1-designs e estudam-se algumas propriedades dos 2-designs e sistemas de Steiner. Apresentam-se várias ligações entre designs e grafos fortemente regulares e, em particular, mostra-se que o grafo dos blocos de um design quasi-simétrico é um grafo fortemente regular. Nas geometrias finitas consideram-se propriedades básicas dos planos afins e dos planos projectivos. Das propriedades destas geometrias, destacam-se a correspondência com determinadas famílias de 2-designs e a propriedade do grafo de incidência de um plano projectivo ser um grafo bipartido regular com cintura 6.<br>In this dissertation a brief introduction to graph theory, combinatorial designs and finite geometries is presented and some interconnections among those combinatorial structures are shown. In the context of graphs, some emphasis is given to strongly regular graphs and properties of the adjacency matrices. Properties of 2-designs and Steiner systems are studied as well as the construction of 1-designs. In addition, some connections between designs and strongly regular graphs are presented and it is shown that the block graph of a quasi-symmetric design is strongly regular. The finite geometries studied are the affine planes and the projective planes. Basic properties are considered, particularly the correspondence between those geometries and several families of 2-designs and the incidence graph of a projective plane being a regular bipartite graph with girth 6.
47
Vaz, Alves Gleifer. "Normalização para os N-Grafos." Universidade Federal de Pernambuco, 2005. https://repositorio.ufpe.br/handle/123456789/2786.
Full textAbstract:
Made available in DSpace on 2014-06-12T16:01:12Z (GMT). No. of bitstreams: 2
arquivo7176_1.pdf: 981863 bytes, checksum: b65d9631609e56e387c6959338c69466 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2005<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>Os principais métodos da teoria da prova geral são: eliminação-do-corte e normalização. Na teoria da prova há muitos trabalhos voltados ao teorema da eliminação-do-corte para o cálculo de seqüentes clássico. Por outro lado, encontram-se relativamente poucas investigações direcionadas à normalização para a dedução natural clássica. Essa distinção é acentuada quando se tem a normalização para a lógica clássica através de uma estrutura de prova com mais de uma conclusão. Mencionem-se dois autores que apresentam normalização para uma estrutura com mais de uma conclusão, e.g. Ungar e Cellucci. Todavia, nenhuma investigação apresenta um tratamento direcionado às questões inerentes da definição de um procedimento de normalização dentro de uma estrutura de prova com mais de uma conclusão, onde as derivações sejam, de fato, representadas como grafos-de-prova. Portanto, o objetivo central deste trabalho é a definição do procedimento de normalização para os N-Grafos. Os N-Grafos foram definidos por de Oliveira e compõem um sistema de provas simétrico para a dedução natural, onde as regras lógicas e estruturais são apresentadas em uma estrutura de prova com múltipla conclusão e as derivações são representadas como digrafos. Para a definição da normalização dos N-Grafos, foram construídos cinco conjuntos de reduções: lógicas, estruturais, com ciclos, com seqüências de repetição de links e com permutação do enfraquecimento. Essas reduções foram baseadas nos trabalhos de Prawitz, Ungar e Cellucci, bem como, inspiradas pela própria estrutura de grafos-de-prova dos N-Grafos. Ademais, foram definidos o teorema e a prova da normalização, sendo que a prova foi construída de forma direta, em contrapartida à prova indireta de Ungar. Posteriormente, foram estabelecidas as propriedades da terminação e da confluência (fraca) para a normalização dos N-Grafos. Através da construção da normalização para os N-Grafos é possível destacar algumas propostas de trabalhos futuros como, por exemplo, a relação entre provas formais, e processos concorrentes e a investigação da correspondência entre a normalização e a identidade de provas
48
Vaz, Alves Gleifer. "Normalização para o N-grafos." Universidade Federal de Pernambuco, 2005. https://repositorio.ufpe.br/handle/123456789/2817.
Full textAbstract:
Made available in DSpace on 2014-06-12T16:01:20Z (GMT). No. of bitstreams: 2
arquivo7782_1.pdf: 981863 bytes, checksum: b65d9631609e56e387c6959338c69466 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2005<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>Os principais métodos da teoria da prova geral são: eliminação-do-corte e normalização.
Na teoria da prova há diversos trabalhos voltados ao teorema da eliminação-do-corte para
o cálculo de sequentes clássico, bem como, investigações direcionadas à normalização
para a dedução natural (DN) clássica. Por outro lado, são encontrados poucos trabalhos
que buscam definir a normalização para a lógica clássica, através de uma estrutura
de prova com mais de uma conclusão. Mencionem-se dois autores que apresentam
normalização para uma estrutura com mais de uma conclusão, e.g. Ungar [Ung92] e
Cellucci [Cel92]. Todavia, nenhuma investigação apresenta um tratamento direcionado
às questões inerentes à definição de um procedimento de normalização dentro de uma
estrutura de prova com mais de uma conclusão, onde as derivações sejam, de fato, representadas
como grafos-de-prova. Portanto, o objetivo central deste trabalho é a definição
do procedimento de normalização para os N-Grafos. Os N-Grafos foram definidos por de
Oliveira e compõem um sistema de provas simétrico para a DN, onde as regras lógicas
e estruturais são apresentadas em uma estrutura de prova com múltipla conclusão e as
derivações são representadas como dígrafos. Para a definição da normalização dos NGrafos,
foram construídos cinco conjuntos de reduções: lógicas, estruturais, com ciclos,
sequência com repetição de ciclos entrelaçados e permutação do enfraquecimento. Essas
reduções foram baseadas nos trabalhos de Prawitz, Ungar e Cellucci, bem como, inspiradas
pela própria estrutura de múltipla conclusão dos N-Grafos. Ademais, foram definidos
o teorema e a prova da normalização, sendo que a prova foi construída de forma direta,
diferentemente da prova indireta dada por Ungar. Posteriormente, foram estabelecidas
as propriedades da terminação e da confluência (fraca) para a normalização dos N-Grafos.
Através da construção da normalização para os N-Grafos é possível destacar algumas propostas
de trabalhos futuros como, por exemplo, a relação entre provas formais e processos
concorrentes, e a investigação da correspondência entre a normalização e a identidade de
provas
49
Almeida, Sheila Morais de 1979. "Coloração de arestas em grafos split." [s.n.], 2012. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275712.
Full textAbstract:
Orientador: Célia Picinin de Mello<br>Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-08-20T03:13:25Z (GMT). No. of bitstreams: 1
Almeida_SheilaMoraisde_D.pdf: 958566 bytes, checksum: ac97bf74cca2e690531df0f6d05c8a00 (MD5)
Previous issue date: 2012<br>Resumo: Por apresentar basicamente fórmulas, o resumo, na íntegra, poderá ser visualizado no texto completo da tese digital<br>Abstract: Not informed<br>Doutorado<br>Ciência da Computação<br>Doutor em Ciência da Computação
50
Inácio, Júnior Edmundo. "Planarização de grafos por divisão de vértices." reponame:Repositório Institucional da UFPR, 2010. http://hdl.handle.net/1884/22574.
Full text