Uma abordagem computacional do contorno de grafos

Resumo

Neste trabalho consideramos um problema relacionado a convexidade geodésica em grafos. O conceito de convexidade em estruturas discretas foi estendido a partir do conceito para matemática contınua. Os grafos adotados são finitos, simples e conexos. Seja G um grafo, denotamos seu conjunto de vértices por V (G) e o conjunto de arestas por E(G), onde n é o número de vértices de G e m é o número de arestas de G. O intervalo fechado I[S] de um conjunto S  V (G) é o conjunto de todos os vértices que se encontram em algum caminho mınimo entre pares de vértices de S, incluindo os vértices em S. Um conjunto S  V (G) é geodésico se I[S]  V (G). A distância d(v,w) entre dois vértices v,w  V (G) é o número de arestas no caminho mınimo entre v e w. A excentricidade ecc(v) de um vértice v é o máximo de d(v,w) para todo vértice w  V (G). O diâmetro diam(G) de G é máximo ecc(v) para todo vértice v  V (G). O contorno Ct(G) de G é o conjunto dos vértices cuja excentricidade é maior ou igual que a de seus vizinhos. Neste trabalho consideramos o problema de determinar se o conjunto de contorno de um grafo é geodésico. Este problema foi definido em [3], onde os autores apresentaram o grafo G1 da Figura 1, observe que Ct(G1)  {a, b, c} e I[Ct(G1)]  V (G)\{d}, logo Ct(G1) não é um conjunto geodésico. Além disso, provaram que o contorno dos grafos pertencentes a classe distância hereditária é geodésico. Em [2], os autores apresentaram o grafo G4 da Figura 1, que é obtido estendendo-se o grafo G1, e analogamente a G1 temos que Ct(G4)  {a, b, c} e I[Ct(G4)]  V (G) \ {d}. Ainda mais, G4 é um grafo de permutação. Por fim, provaram que para todo grafo cordal o contorno é geodésico e apresentaram um esquema de classes de grafos classificadas em 3 tipos: classes onde todo grafo possui o contorno geodésico; classes onde nem todo grafo possui o contorno geodésico; e classes em aberto, onde a resposta não era conhecida. Em [1], todos as classes mencionadas como em aberto em [2] receberam respostas definitivas e, além disso, os autores apresentaram um novo grafo cujo contorno não é geodésico. Os 3 artigos mencionados no parágrafo anterior apresentaram, em 8 anos, apenas 3 grafos diferentes tais que o contorno não é geodésico. A dificuldade de obtenção desses exemplos se deve, primeiramente, porque tais grafos não são comuns, mas principalmente pelo grande trabalho necessário para calcular manualmente as excentricidades dos vértices de G, determinar Ct(G) e verificar se Ct(G) é geodésico. Esta dificuldade torna a abordagem computacional promissora para análise do problema, e este é o foco deste trabalho. Dado um grafo G, o algoritmo implementado para verificar se Ct(G) é geodésico consiste em: calcular a excentricidade de cada vértice de G, aplicando n vezes o algoritmo de busca em largura; determinar para cada vértice v  V (G) se v  Ct(G), comparando a excentricidade de v com a de seus vizinhos; e testar se I[Ct(G)]  V (G), verificando para cada vértice v  V (G) se existe x, y  Ct(G) tal que v se encontra em um caminho mınimo entre x e y. O algoritmo descrito tem complexidade Parcialmente financiado por Proppi/PDI/UFF †bolsista de Iniciação Cientıfica PIBIC/UFF O(n3), nossa ideia central é analisar conjuntos de grafos, com alguma propriedade especıfica, e verificar se neste conjunto existem grafos cujo contorno não é geodésico. Por exemplo, verificar se existe um grafo Ct(G) de 10 vértices tal que I[Ct(G)] 6 V (G). No entanto, o número total de grafos não isomorfos de 10 vértices é muito grande, portanto acrescentamos alguns testes ao algoritmo para melhorar seu desempenho. Alguns desses testes foram extraıdos de [1], onde os autores provaram que o contorno de um grafo G qualquer é geodésico se diam(G)  4 ou diam(G)  7 para um grafo G bipartido. Além disso, desenvolvemos o resultado a seguir. [...]