En teoría de grafos, un gráfico geodésico es un gráfico no dirigido tal que existe un camino más corto único (no ponderado) entre cada dos vértices.
Los gráficos geodésicos fueron introducidos en 1962 por Øystein Ore , quien observó que generalizan una propiedad de los árboles (en la que existe un camino único entre cada dos vértices independientemente de la distancia), y pidió una caracterización de los mismos. [1] Aunque estos gráficos pueden reconocerse en tiempo polinomial , "más de sesenta años después, una caracterización completa aún es difícil de alcanzar". [2]
Cada árbol , [1] cada gráfico completo , [3] y cada gráfico de ciclo de longitud impar es geodésico. [4]
Si es un gráfico geodésico, reemplazar cada borde por un camino de la misma longitud impar producirá otro gráfico geodésico. [5] En el caso de un gráfico completo , es posible un patrón más general de reemplazo por caminos: elija un número entero no negativo para cada vértice y subdivida cada arista agregándole vértices. Entonces el gráfico completo subdividido resultante es geodésico, y cada gráfico geodésico completo subdividido se puede obtener de esta manera. [6] [7]
Si cada componente biconectado de un gráfico es geodésico, entonces el gráfico en sí es geodésico. En particular, todo gráfico de bloques (gráficos en los que los componentes biconectados están completos ) es geodésico. [3] De manera similar, debido a que un gráfico de ciclo es geodésico cuando tiene una longitud impar, cada gráfico de cactus en el que los ciclos tienen una longitud impar también es geodésico. Estos gráficos de cactus son exactamente los gráficos conectados en los que todos los ciclos tienen una longitud impar. Más claramente, un gráfico plano es geodésico si y sólo si todos sus componentes biconectados son ciclos de longitud impar o subdivisiones geodésicas de una camarilla de cuatro vértices. [4]
Los gráficos geodésicos se pueden reconocer en tiempo polinómico , mediante el uso de una variación de búsqueda de amplitud que puede detectar múltiples caminos más cortos, comenzando desde cada vértice del gráfico. Los gráficos geodésicos no pueden contener un gráfico de ciclo inducido de cuatro vértices, ni un gráfico de diamante inducido , porque estos dos gráficos no son geodésicos. [3] En particular, como subconjunto de gráficos sin diamantes, los gráficos geodésicos tienen la propiedad de que cada arista pertenece a una camarilla máxima única ; en este contexto, las camarillas máximas también han sido llamadas líneas . [8] De ello se deduce que el problema de encontrar camarillas máximas , o camarillas máximas ponderadas, se puede resolver en tiempo polinomial para gráficos geodésicos, enumerando todas las camarillas máximas. La clase más amplia de gráficos que no tienen 4 ciclos inducidos ni diamantes se denominan "débilmente geodésicos"; estos son los gráficos donde los vértices a una distancia exactamente de dos entre sí tienen un camino más corto único. [3]
Para gráficos de diámetro dos (es decir, gráficos en los que todos los vértices están a una distancia máxima de dos entre sí), los gráficos geodésicos y los gráficos débilmente geodésicos coinciden. Todo gráfico geodésico de diámetro dos es de uno de tres tipos:
Los gráficos geodésicos fuertemente regulares incluyen el gráfico de ciclo de 5 vértices, el gráfico de Petersen y el gráfico de Hoffman-Singleton . A pesar de investigaciones adicionales sobre las propiedades que debe tener un gráfico de este tipo, [9] [10] no se sabe si hay más de estos gráficos, o si hay un número infinito de estos gráficos. [8]
¿Existen infinitos gráficos geodésicos fuertemente regulares?
Los grafos geodésicos de diámetro dos y dos grados diferentes no pueden tener un triángulo compuesto por vértices de ambos grados. Se pueden construir a partir de cualquier plano afín finito agregando al gráfico de incidencia de líneas de puntos del plano bordes adicionales entre los vértices correspondientes a cada dos líneas paralelas. Para el plano afín binario con cuatro puntos y seis líneas de dos puntos en tres pares paralelos, el resultado de esta construcción es el gráfico de Petersen, pero para planos afines finitos de orden superior produce gráficos con dos grados diferentes. También se conocen otras construcciones relacionadas de gráficos geodésicos a partir de geometrías finitas, pero no se sabe si agotan todos los gráficos geodésicos posibles con un diámetro de dos y dos grados diferentes. [8]
