Busca pelas simetrias do DDGP via grafos K−incidentes

Resumo

O Problema de Geometria de Distâncias (DGP) consiste em determinar se existe uma realização de um grafo G = (V,E, d) simples, conexo e ponderado, em algum espaço RK, onde K > 1, de forma que as distâncias entre as realizações de pares de vértices u e v coincidam com o peso duv da aresta {u, v}. Na Definição 0.1 formalizamos esse conceito que segue diretamente de [2]. Definição 0.1. Dado um grafo simples, não direcionado e ponderado, G = (V,E, d), e um inteiro positivo K, encontre uma função x : V → RK tal que ∀{u, v} ∈ E, ∥xu − xv∥ = duv. (1) A função x é chamada de realização de G. Iremos considerar, na maioria dos casos, K = 2 ou K = 3, mas os resultados podem ser estendidos para um K qualquer. Uma subclasse desse problema é conhecida por DDGP (DGP discretizável), onde, adicionando uma ordem conveniente aos vértices do grafo (ver [2]), o problema pode ser discretizado e resolvido por meio de um algoritmo conhecido como Branch and Prune (BP) [4], cujo espaço de busca pode ser representado por uma árvore binária. Em vista do que definimos até agora, o intuito deste trabalho é apresentar os grafos de K-discretização e de K-incidência para o DDGP, com a finalidade de tentar explorar o número de soluções deste problema, bem como as suas simetrias.