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
Department : 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 SizeFormat 
877663.pdf1,99 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.