Consultas de distancia para reconstruir un gráfico desconocido

Question

Dejemos que $G$ sea un grafo finito, simple, conexo y no dirigido en $n$ vértices. Supongamos que su objetivo es determinar $G$ únicamente a través de consultas. Cada consulta elige un $v_i$ y devuelve las distancias más cortas (número de aristas) de $v_i$ entre sí $v_j$ , $j \neq i$ . Así, para un $4$ -de vértices, un $v_1$ la consulta podría devolver lo siguiente (índices en la primera fila, distancias en la segunda): $$ \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 0 & 1 & 1 & 2 \\ \end{array} \right] $$

---

         

Estos datos son compatibles con los gráficos (a), (b), (c), (d) anteriores, pero no (e), porque la distancia de $v_1$ a $v_4$ debe ser $2$ no $1$ . Si ahora consultamos las distancias de $v_2$ y recibir esta información, $$ \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 0 & 2 & 1 \\ \end{array} \right] $$ entonces sólo (a) y (c) son compatibles. Parece necesaria una consulta más necesaria para precisar cuál.

En el caso de que el usuario elija cada consulta después de revisar los resultados de las consultas anteriores:

Q1 . ¿Existen clases de gráficos en $n$ vértices que requieren $n$ consultas para precisar su estructura?

Creo que si uno conoce la matriz de distancia completa, entonces la matriz de adyacencia está determinada, y así $G$ se determina.

Q2 . ¿Pueden bastar las consultas sublineales para (a) alguna clase natural de grafos (por ejemplo, árboles)? clase natural de grafos (por ejemplo, árboles?), o (b) para algún modelo de grafos aleatorios (por ejemplo, Erdős-Rényi)?

Answer 1

Esta es una pregunta intrigante. A partir de una consulta, se puede establecer una gran cantidad de no bordes: si dos vértices difieren en distancia de un tercero en dos o más, estos dos vértices no son vecinos. Por lo tanto, parece que a partir de una consulta de unos pocos vértices "remotos" se pueden determinar muchos no-conductos y acercarse a la determinación del grafo. Sin embargo, "triangular" un grafo (en el sentido que voy a introducir), significa que no se puede triangular un grafo con unas pocas observaciones de distancia en el sentido que pide Joseph. En concreto, se necesitan al menos n/3 consultas.

Este es mi sentido de la triangulación, que debería funcionar para cualquier grafo base, pero comenzando con un camino por ejemplo de m vértices. Haremos un grafo de n=3m vértices añadiendo triángulos al grafo original: por cada vértice v, añadiremos un vértice u y w, y las únicas aristas nuevas son el triángulo que conecta u,v, y w; u y w no se conectan a nada más en la construcción.

Para cada par de u y w, hay que consultar uno de ellos para ver si hay una arista entre ellos. Todas las demás consultas "tienen que pasar por v", y no podrán determinar si u y w tienen esa arista. Por tanto, se necesitan n/3 consultas para cubrir los triángulos. Combinando esta idea con el comentario, puedes (K_d)-gular un grafo para forzar que una gran fracción de vértices sean consultados para determinar el grafo. Por supuesto, puedes hacerlo aún más interesante eliminando una arista de cada colgante K_d.

Gerhard "El zoo gráfico tiene un nuevo miembro" Paseman, 2019.12.21.