En teoría de grafos, un grafo geodésico es un grafo no dirigido tal que existe una ruta más corta única (no ponderada) entre cada dos vértices.
Los grafos geodésicos fueron introducidos en 1962 por Øystein Ore , quien observó que generalizaban 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 grafos pueden reconocerse en tiempo polinomial , "más de sesenta años después una caracterización completa sigue siendo difícil de alcanzar". [2]
Todo árbol , [1] todo grafo completo , [3] y todo grafo de ciclo de longitud impar es geodésico. [4]
Si es un grafo geodésico, entonces reemplazar cada borde de por un camino de la misma longitud impar producirá otro grafo geodésico. [5] En el caso de un grafo completo , es posible un patrón más general de reemplazo por caminos: elegir un entero no negativo para cada vértice y subdividir cada borde añadiéndole vértices. Entonces, el grafo completo subdividido resultante es geodésico, y cada grafo completo subdividido geodésico se puede obtener de esta manera. [6] [7]
Si cada componente biconexo de un grafo es geodésico, entonces el grafo mismo es geodésico. En particular, cada grafo de bloques (grafos en los que los componentes biconexos son completos ) es geodésico. [3] De manera similar, debido a que un grafo de ciclo es geodésico cuando tiene una longitud impar, cada grafo de cactus en el que los ciclos tienen una longitud impar también es geodésico. Estos grafos de cactus son exactamente los grafos conexos en los que todos los ciclos tienen una longitud impar. Más fuertemente, un grafo plano es geodésico si y solo si todos sus componentes biconexos son ciclos de longitud impar o subdivisiones geodésicas de una camarilla de cuatro vértices. [4]
Los grafos geodésicos pueden reconocerse en tiempo polinomial , utilizando una variación de la búsqueda en amplitud que puede detectar múltiples caminos más cortos, comenzando desde cada vértice del grafo. Los grafos geodésicos no pueden contener un grafo de ciclo de cuatro vértices inducido, ni un grafo de diamante inducido , porque estos dos grafos no son geodésicos. [3] En particular, como un subconjunto de grafos sin diamante, los grafos geodésicos tienen la propiedad de que cada borde pertenece a un único clique maximal ; en este contexto, los cliques maximal también se han llamado líneas . [8] De ello se deduce que el problema de encontrar cliques máximos , o cliques ponderados máximos, se puede resolver en tiempo polinomial para grafos geodésicos, enumerando todos los cliques maximal. La clase más amplia de grafos que no tienen 4 ciclos inducidos o diamante se denominan "débilmente geodésicos"; estos son los grafos donde los vértices a una distancia exactamente dos entre sí tienen un camino más corto único. [3]
En el caso de los grafos de diámetro dos (es decir, grafos en los que todos los vértices están a una distancia de dos como máximo entre sí), los grafos geodésicos y los grafos débilmente geodésicos coinciden. Todo grafo geodésico de diámetro dos es de uno de tres tipos:
Los grafos geodésicos fuertemente regulares incluyen el grafo de ciclo de 5 vértices, el grafo de Petersen y el grafo de Hoffman-Singleton . A pesar de la investigación adicional sobre las propiedades que debe tener un grafo de este tipo, [9] [10] no se sabe si hay más de estos grafos o si hay un número infinito de ellos. [8]
Los grafos geodésicos con diámetro dos y dos grados diferentes no pueden tener un triángulo compuesto por vértices de ambos grados. Pueden construirse a partir de cualquier plano afín finito añadiendo al grafo de incidencia punto-línea del plano aristas 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 grafo de Petersen, pero para planos afines finitos de orden superior produce grafos con dos grados diferentes. También se conocen otras construcciones relacionadas de grafos geodésicos a partir de geometrías finitas, pero no se sabe si éstas agotan todos los grafos geodésicos posibles con diámetro dos y dos grados diferentes. [8]
