Supongamos que usted tiene una conectada, no ponderada, de grafo no dirigido de $48$ nodos. Ahora imagine que usted podrá elegir $6$ nodos y con la etiqueta especial. (En el caso general, podemos seleccionar el $K$ nodos a ser especial entre el $N$ total de nodos en el gráfico, donde $K < N$.) Vamos a llamar a los otros $42$ nodos genéricos.
Una vez que el $6$ nodos especiales son elegidos, se forman nuevas aristas entre cada par de nodos especiales. (A la velocidad de los viajes a través de lugares remotos en el gráfico).
Tengo un par de preguntas:
- Hay una sola, ya documentado algoritmo que está diseñado precisamente para resolver este problema? Es decir, se determina la ubicación de los nodos especiales, tales que la distancia promedio desde cualquier nodo genérico a su más cercano nodo especial se reduce al mínimo?
- Estoy resolver el mismo problema si me reformular la pregunta de arriba para leer "... la distancia media entre dos nodos del grafo (con el nuevo especial de bordes añadidos) es mínimo?"
- ¿Qué tipos de gráficos, y la teoría de grafos, están relacionadas con la resolución de este tipo de problema? Obviamente ruta más corta tipo de preguntas. Pero hay un concepto como el de "cobertura"?
El objetivo formulado en términos muy genéricos, es ser capaz de recorrer, tan pronto como sea posible, de cualquier nodo en el gráfico a cualquier otro nodo arbitrario.
Para un poco más de contexto, esta teoría de grafos pregunta fue inspirado por el juego de mesa de la Pandemia. Un par de colegas y yo hemos tratado de buscar en la web / Wikipedia pero no he encontrado nada definitivo todavía.
