SOBRE CONVEXIDADE E POSTO GEODÉTICO

Resumo

Seja um grafo (simples) uma estrutura G=(V,E) onde V é um conjunto de vértices e E conjunto formado por pares de vértices não ordenados. Uma convexidade em um grafo finito G é uma família de subconjuntos de vértices C de tal modo que o ø e V(G) pertencem a C, além de ser fechado sob interseções, isto é, se dois conjuntos pertencem a C, sua interseção também pertence. Os conjuntos em C são ditos convexos. O menor conjunto convexo em C que contém um conjunto de vértices S será chamado de hull ou envoltória de S. S será convexamente independente se cada elemento de S não pertence a envoltória dos outros membros de S. Com isso, podemos definir posto, que será a cardinalidade do maior conjunto convexamente independente de G. A convexidade geodética consiste no estudo de convexidade sobre a ótica de menor caminho entre dois vértices u e v de G. Nesse trabalho, lemos artigos relacionados a convexidade em grafos. Em tais artigos, estudamos resultados relacionados a complexidade computacional da aproximação do posto geodético, bem como teoremas que auxiliam na construção de algoritmos em tempo linear para o calculo do posto de um grafo construído através da operação de junção e união, através do uso da árvore de decomposição modular do Grafo G, onde a operação de união consiste apenas em juntos os dois grafos sem adição de arestas e na junção ocorre a união dos vértices e o acréscimo de todos as possíveis arestas entre os vértices dos grafos adicionadas. Relacionamos também o resultado com a convexidade P3*, onde consiste em caminho minimo de tamanho 3, sem considerar a possível existência de ciclos. Vemos que ocorrem parâmetros semelhantes em grafos com poucos P4 e mais geralmente em grafos do tipo aranha, sendo ela magra ou gorda.