To see the other types of publications on this topic, follow the link: Teoria espetral de grafos.
Dissertations / Theses on the topic 'Teoria espetral de 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 espetral de 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
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.
2
Pinheiro, Sofia Alexandra Marques Jorge. "Majorantes para a ordem de subgrafos induzidos k-regulares." Doctoral thesis, Universidade de Aveiro, 2014. http://hdl.handle.net/10773/12863.
Full textAbstract:
Doutoramento em Matemática<br>Muitos dos problemas de otimização em grafos reduzem-se à determinação
de um subconjunto de vértices de cardinalidade máxima que induza
um subgrafo k-regular. Uma vez que a determinação da ordem
de um subgrafo induzido k-regular de maior ordem é, em geral, um
problema NP-difícil, são deduzidos novos majorantes, a determinar em
tempo polinomial, que em muitos casos constituam boas aproximações
das respetivas soluções ótimas. Introduzem-se majorantes espetrais
usando uma abordagem baseada em técnicas de programação convexa
e estabelecem-se condições necessárias e suficientes para que sejam
atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro
das matrizes de adjacência, laplaciana e laplaciana sem sinal. É
ainda apresentado um algoritmo não polinomial para a determinação de
umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular
de ordem máxima para uma classe particular de grafos. Finalmente,
faz-se um estudo computacional comparativo com vários majorantes e
apresentam-se algumas conclusões.<br>Many optimization problems on graphs are reduced to the determination
of a subset of vertices of maximum cardinality inducing a k-regular
subgraph. Since the determination of the order of a k-regular induced
subgraph of highest order is in general a NP-hard problem, new upper
bounds, determined in polynomial time which in many cases are good
approximations of the respective optimal solutions are deduced. Using
convex programming techniques, spectral upper boundswere introduced
jointly with necessary and sufficient conditions for those upper bounds
be achieved. Additionally, upper bounds based on adjacency, Laplacian
and signless Laplacian spectrum are introduced. Furthermore, a nonpolynomial
time algorithm for determining a subset of vertices of a graph
which induces a maximum k-regular induced subgraph for a particular
class is presented. Finally, a comparative computational study is provided
jointly with a few conclusions.
3
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
4
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.
5
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.
6
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.
7
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
8
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.
9
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.
10
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.
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
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
13
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
14
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
15
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
16
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
17
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.
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
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
21
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.
22
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
23
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
24
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
25
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.
26
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.
27
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
28
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
29
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.
30
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
31
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.
32
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.
33
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.
34
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.
35
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
36
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
37
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.
38
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
39
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
40
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
41
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
42
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
43
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,
44
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
45
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.
46
Araújo, Samuel Nascimento de. "Número de dominação romana em grafos." reponame:Repositório Institucional da UFC, 2016. http://www.repositorio.ufc.br/handle/riufc/21822.
Full textAbstract:
ARAUJO, Samuel Nascimento de. Número de dominação romana em grafos. 2016. 51 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016.<br>Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-25T17:42:43Z
No. of bitstreams: 1
2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5)<br>Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-01-26T20:23:42Z (GMT) No. of bitstreams: 1
2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5)<br>Made available in DSpace on 2017-01-26T20:23:42Z (GMT). No. of bitstreams: 1
2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5)
Previous issue date: 2016<br>In a Roman domination of a graph, vertices are assigned a value from {0,1,2} in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this dissertation, we show the history of the problem and prove that the Roman domination number is NP-Complete even for induced subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results when we consider digraphs as an input for the problem such as bipartite tournaments and planar digraphs.<br>No problema de dominação romana de um grafo, os vértices são atribuídos um valor de {0,1,2}, de tal maneira que cada vértice atribuído o valor 0 é adjacente a um vértice que foi atribuído o valor 2. O número de dominação romana é a menor soma possível de todos os valores dos vértices em tal atribuição. Nesta dissertação apresentamos a história do problema, e provamos que o número dominação romana é NP-Completo mesmo para subgrafos induzidos de grids e é APX-difícil mesmo para grafos bipartidos com o grau máximo 4. Nós também provamos que o número de dominação romana é tratável por parâmetro fixo para grafos com treewidth local limitada, como grafos com grau máximo limitado ou genus limitado (como por exemplo grafos planares). Nós também obtivemos resultados de complexidade quando consideramos digrafos como entrada para o problema, tais como torneios bipartidos e digrafos planares.
47
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
48
Pedrotti, Vagner 1980. "Problemas em grafos com poucos P4's em grafos indiferença." [s.n.], 2011. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275714.
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-19T10:47:23Z (GMT). No. of bitstreams: 1
Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5)
Previous issue date: 2011<br>Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração<br>Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems<br>Doutorado<br>Ciência da Computação<br>Doutor em Ciência da Computação
49
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
50
Cohen, Jaime. "Cortes orientados e cortes impares em grafos." [s.n.], 1995. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276026.
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-20T10:56:57Z (GMT). No. of bitstreams: 1
Cohen_Jaime_M.pdf: 1980563 bytes, checksum: 88f8b3def82f23368e2850ce7706fb31 (MD5)
Previous issue date: 1995<br>Resumo: Esta dissertação tem como objetivo apresentar igualdades minimax em grafos que envolvem cortes orientados; cortes ímpares e suas coberturas.
A primeira metade da dissertação trata das igualdades que relacionam famílias disjuntas máximas de cortes com as coberturas mínimas dos cortes do grafo. Na segunda parte, os papéis destes problemas são inveI:tidos, isto é, as igualdades relacionam cortes mínimos com famílias disjuntas máximas de coberturas dos cortes.
Mostramos ao longo do trabalho que em muitos casos é possível estabelecer analogias entre resultados para cortes orientados e para cortes ímpares. Estas analogias apresentam-se de duas maneiras: através de enunciados semelhantes e através de demonstrações semelhantes.
Entre os teoremas apresentados na primeria parte do trabalho, destacam-se os Teoremas de ~ucchesi- Younger e de Edmonds-Giles para cortes orientados e os de Lovász e de Seymour para cortes ímpares. Também são apresentados teoremas que tratam de circuitos orientados e ímpares em grafos planares, mostrando que a analogia também se estende para outros tipos de problemas.
Na segunda parte estabelecemos relações entre a igualdade minimax dual ao Teorema de Lovász com a generalização de uma famosa conjectura de Fulkerson. . Provamos um caso particular desta igualdade. Apresentamos também um resultado para um caso particular da igualdade dual ao Teorema de Lucchesi- Younger que foi provado por Schrijver e independentemente por Feofiloff e Younger.<br>Abstract: The goal of this dissertation is to unify some results of Graph Theory related to directed
cuts, odd cuts and their coverings.
In the first half of this work we show equalities that relate maximum disjoint families of cuts with the minimum coverings of the cuts of the graph. In the second half, we present the duals of those equalities, i. e., they relate minimum cuts with disjoint families of coverings.
Qur main purpose. is to provi de examples that show analogies between results on directed cuts and odd cuts. The analogies are of two types: in the statements of the results and in their proofs.
Among the results presented in the first half, the most important are Lucchesi- Younger and
Edmonds-Giles' theorems on directed cuts and Lovász and Seymour's theorems for odd cuts.
In the last part of this work we extend a result by Seymour that relates the dual of Lovász's theorem with a generalizatión of a famous conjecture due to Fulkerson. We prove a particular case of that equality. We also show an equality for a particular case of the dual of LucchesiYounger's theorem which had been proved by Schrijver and independent1y by Fe,ofiloff and Younger.<br>Mestrado<br>Mestre em Ciência da Computação