Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/10086| Type: | Tese |
| Title: | Produto funcional de grafos :propriedades e aplicações |
| Author(s)/Inventor(s): | Mattos, Sergio Ricardo Pereira de |
| Advisor: | Jurkiewicz, Samuel |
| Abstract: | Nesta tese, abordamos o produto funcional de grafos, suas propriedades e aplicações. Estudamos a associatividade e mostramos que, no conjunto dos grafos, a relação “ter a mesma sequencia de graus” é uma relação de equivalência e o produto funcional ´e associativo nas classes de equivalência. No tocante a invariante conexidade, apresentamos condições em que o produto funcional de grafos bipartidos gera um grafo desconexo e generalizamos esse resultado para grafos k-partidos. Além disso, melhoramos o resultado apresentado por Lozano et al. [33], que garante a conexidade do grafo produto funcional, quando os grafos fatores são conexos. Em trabalho conjunto com Lozano e Siqueira, mostramos que o produto funcional de grafos permite construir grafos harmônicos, a partir de qualquer grafo regular. Inicialmente, provamos que para todo grafo regular G e seu complemento G′ , existem aplicações de ligação tais que o grafo produto funcional é harmônico. Em seguida, mostramos que dado um grafo regular G e seu complemento G′, se ∆(G′ ) é par, então para qualquer grafo H tal que ∆(G′ ) = ∆(H), existem aplicações de ligação tais que o grafo produto funcional é harmônico. Por fim, provamos que para n e k ∈ N, se (k + 1)|n, existe um grafo conexo harmônico k-regular com n vértices. |
| Abstract: | In this thesis, we approach the functional product of graphs, their properties, and applications. We study associativity, and show that, in the set of graphs, the relation “to have the same sequence of degrees” is an equivalence relation and the functional product is associative in the equivalence classes. With regard to the invariant connectivity, we present conditions in which the functional product of bipartite graphs generates a disconnected graph, and we generalize this result to k-partite graphs. Therefore, we improved the result reported by Lozano et al. [33], which ensures the connectivity of the functional product graph, when the factor graphs are connected. Together with Lozano and Siqueira, we show that the functional product of graphs allows to construct harmonic graphs from any regular graph. Initially, we prove that for every regular graph G and its complement G′ , there are linking applications such that the functional product graph is harmonic. After that, we show that given a regular graph G and its complement G′ , if ∆(G′ ) is even, then for any graph H such that ∆(G′ ) = ∆(H), there are linking applications such that the functional product graph is harmonic. Finally, we prove that for n and k ∈ N, if (k + 1)|n, there is a harmonic connected k-regular graph with n vertices. |
| Keywords: | Engenharia de produção Produto funcional de grafos Grafos harmônicos |
| Subject CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO |
| Program: | Programa de Pós-Graduação em Engenharia de Produção |
| Production unit: | Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia |
| Publisher: | Universidade Federal do Rio de Janeiro |
| Issue Date: | Sep-2017 |
| Publisher country: | Brasil |
| Language: | por |
| Right access: | Acesso Aberto |
| Appears in Collections: | Engenharia de Produção |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 877663.pdf | 1.99 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.