Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/18553| Tipo: | Dissertação |
| Título : | Convexidades de caminhos e convexidades geométricas |
| Título en inglés: | Convexities convexities of paths and geometric |
| Autor : | Araújo, Rafael Teixeira de |
| Tutor: | Sampaio, Rudini Menezes |
| Palabras clave : | Ciência da computação;Convexidade em grafos;Convexidade geodésica;Número de hull;Número de convexidade;Convexidade geométrica |
| Fecha de publicación : | 2014 |
| Citación : | 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. |
| Resumen en portugués brasileño: | 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. |
| URI : | http://www.repositorio.ufc.br/handle/riufc/18553 |
| Aparece en las colecciones: | DCOMP - Dissertações defendidas na UFC |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2014_dis_rtaraujo.pdf | 973,82 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.