Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/18553
Título: Convexidades de caminhos e convexidades geométricas
Título em inglês: Convexities convexities of paths and geometric
Autor(es): Araújo, Rafael Teixeira de
Orientador(es): Sampaio, Rudini Menezes
Palavras-chave: Ciência da computação
Convexidade em grafos
Convexidade geodésica
Número de Hull
Número de convexidade
Convexidade geométrica
Data do documento: 2014
Citação: ARAÚJO, R. T. (2014)
Resumo: Nessa dissertação apresentamos resultados de complexidade relativos ao número de hull e o número de convexidade na convexidade P3. Mostramos que o número de hull e o número de convexidade é NP-difícil mesmo em grafos bipartidos. Motivados por nossa pesquisa em convexidade baseada em caminhos introduzimos uma nova convexidade a qual definimos como convexidade dos caminhos induzidos de ordem três ou P∗ 3 . Mostramos uma relação da convexidade geodésica com a convexidade P∗ 3 no caso onde o grafo ´e uma jun¸c˜ao de um Km com um grafo n˜ao completo. Estudamos também convexidade geométrica e caracterizamos algumas classes de grafos em determinadas convexidade como as florestas de estrela na convexidade P3, cografos cordais na convexidade P∗ 3 , e as florestas na convexidade TP. Mostramos também convexidades que são geométricas somente em uma determinada classe de grafos como os cografos na convexidade P4+-free, os grafos livres de F na convexidade F-free entre outras. Por fim demonstramos alguns resultados de convexidade geodésica e P∗ 3 na em grafos com poucos P4’s.
Abstract: In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P∗ 3 . We show a relation between the geodetic convexity and the P∗ 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P∗ 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P∗ 3 in graphs with few P4’s.
Descrição: ARAÚJO, Rafael Teixeira de. Convexidades de caminhos e convexidades geométricas. 2014. 52 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014.
URI: http://www.repositorio.ufc.br/handle/riufc/18553
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2014_dis_rtaraujo.pdf973,82 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.