Sobre o Grafo de K-incidência para o K-Problema Discretizável de Geometria de Distâncias

Abstract

O Problema de Geometria de Distâncias (DGP) consiste em determinar se existe uma realização de um grafo simples, ponderado, G = (V, E, d), em algum espaço euclidiano, 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}. Uma subclasse importante de problemas é chamada de DDGP (DGP discretizável) e consiste de um DGP onde algumas hipóteses adicionais permitem que o problema seja discretizado. Neste trabalho apresentaremos os grafos de K-discretização e de K-incidência para o DDGP.[...]