Gráfico geodésico
En la teoría de grafos, un grafo geodésico es un grafo no dirigido de modo que existe una ruta más corta única (no ponderada) 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 es aún difícil de alcanzar". [2]
Si es un gráfico geodésico, entonces reemplazar cada borde de por una ruta 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 rutas: elija un número entero no negativo para cada vértice y subdivida cada borde agregando vértices. Entonces, el gráfico completo subdividido resultante es geodésico, y cada gráfico completo subdividido geodésico 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, cada 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 fuertemente, un gráfico plano es geodésico si y solo 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 polinomial , mediante el uso de una variación de la primera búsqueda de amplitud que puede detectar múltiples rutas más cortas, comenzando desde cada vértice del gráfico. Los gráficos geodésicos no pueden contener un gráfico de ciclo de cuatro vértices inducido, ni un gráfico de diamante inducido , porque estos dos gráficos no son geodésicos. [3] En particular, como un subconjunto de gráficos sin diamantes, los gráficos geodésicos tienen la propiedad de que cada borde pertenece a una camarilla máxima única ; en este contexto, las camarillas máximas también se han llamado líneas . [8] De ello se deduce que el problema de encontrar camarillas máximas, o camarillas ponderadas máximas, se pueden 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 o diamantes inducidos se denominan "geodésicos débiles"; Estos son los gráficos en los que los vértices a una distancia de exactamente dos entre sí tienen una ruta más corta única. [3]
Para gráficas de diámetro dos (es decir, gráficas en las que todos los vértices están a una distancia máxima de dos entre sí), las gráficas geodésicas y las gráficas geodésicas débilmente coinciden. Cada gráfico geodésico de diámetro dos es de uno de tres tipos:
