Teoría

    DEFINICIÓN



    Sea G = (V, E) un grafo conexo de orden |G| = |V| = n, y sean dos vértices x, y є V:


    • La distancia entre x e y la notaremos como d(x,y), recordamos que es el número de aristas de un camino corto entre x e y.
    • El diámetro se denota como D de G y es el máximo valor de la distancia entre dos vértices de G, D = max { d(x,y), x , y є V }.
    • Un vértice x є V resuelve un par de vértices u, v є V si d(x,u) ≠ d(x,v). Un conjunto S, S є V, resuelve G, si para todo par de vértices de G existe un vértice de S que los resuelve.
    • La dimensión métrica de G la llamaremos ß y es el cardinal mínimo que tiene un conjunto S que resuelve G, ß = min {|S| , S resuelve G}. Diremos que un conjunto S, S є V, es una base si S resuelve G y |S| = ß.

    Por otro lado, denominamos un conjunto de vértices ordenados a un conjunto W = {w1,w2 ... wk} en el que el orden (w1,w2...wk) ha sido impuesto. Para un subconjunto ordenado W = {w1,w2...wk} de V(G), nos referimos a un k-vector (k-tupla ordenada) como la representación métrica de v con respecto a W:

    r ( v | W ) = ( d ( v, w1 ) , d ( v, w2 ), ... , d (v, wk ) )

    El conjunto W es llamado un conjunto resolutivo de G si r (u | W) = r (v | W), esto implica que u = v para todo u, v є V(G). Además, si W es un conjunto resolutivo de cardinalidad k para el grafo G de orden n, entonces el conjunto { r (v | W) | v є V(G) } consta de n k-vectores distintos. Un conjunto resolutivo de cardinalidad mínima para un grafo G es llamado mínimo conjunto resolutivo.

    Por ejemplo, considerando el grafo G de la figura,
    siendo W = {v1, v2, v3, v4, v5} entonces r (v1, W) = (0, 1, 1, 1, 2)

    Con objeto de aclarar mejor lo que es un conjunto resolutivo, se van a exponer a continuación unos ejemplos partiendo del grafo de la figura:

    Vamos a comprobar si el conjunto W1= {v1,v3}
    es un conjunto resolutivo para G. Calculamos los vectores de distancias desde todos los vértices de G a W1:
    r (v1 / W1) = ( 0, 1 ) r (v2 / W1) = ( 1, 1 )r (v3 / W1) = ( 1, 0 )
    r (v4 / W1) = ( 1, 1 )r (v5 / W1) = ( 1, 2 )

    Se observa que r (v2 / W1) = (1, 1) = r (v4 / W1) por lo que no es un conjunto resolutivo ya que no genera una base.

    En el caso de W2 = { v1 , v2 , v3 },
    sí es un conjunto resolutivo, ya que sus vectores de distancias sí generan una base al no repetirse ninguno de sus vectores de distancias, como vemos a continuación:
    r (v1 / W2) = ( 0, 1, 1 ) r (v2 / W2) = ( 1, 0, 1 )r (v3 / W2) = ( 1, 1, 0 )
    r (v4 / W2) = ( 1, 2, 1 )r (v5 / W2) = ( 2, 1, 1 )

    En la siguiente figura, se visualiza la representación en la aplicación de todos los conjuntos resolutivos de cardinalidad 3 del grafo, así como los vectores de distancias de los conjuntos resolutivos obtenidos, en este caso se observan las del conjunto {v1,v2,v3}:


    Sin embargo, W2 no es un conjunto mínimo resolutivo, ya que hay conjuntos con cardinalidad menor que resuelven el grafo también, como W3 = {v1,v2}
    Queda demostrado en la próxima figura que W3 es un conjunto resolutivo, ya que sus vectores de distancias forman una base:
    r (v1 / W3) = [0,1] r (v2 / W3) = [1,0]r (v3 / W3) = [1,1]
    r (v4 / W3) = [1,2] r (v5 / W3) = [2,1]


    Además, se comprueba que W3 es conjunto mínimo, ya que no hay otro conjunto de menos cardinalidad que resuelva el grafo G, por lo tanto, ya tenemos la dimensión métrica de G, puesto que ß = min { |S| , S resuelve G } = min{ |W3|, W3 resuelve G } , resultando que ß = |W3| = 2.