En teoría de grafos , un conjunto dominante conectado y un árbol de máxima extensión de hojas son dos estructuras estrechamente relacionadas definidas en un gráfico no dirigido .
Un conjunto dominante conexo de un gráfico G es un conjunto D de vértices con dos propiedades:
Un conjunto dominante mínimo conectado de un gráfico G es un conjunto dominante conectado con la cardinalidad más pequeña posible entre todos los conjuntos dominantes conectados de G. El número de dominación conectado de G es el número de vértices en el conjunto dominante mínimo conectado. [1]
Cualquier árbol de expansión T de un gráfico G tiene al menos dos hojas, vértices que tienen solo un borde de T incidente sobre ellos. Un árbol de máxima extensión de hojas es un árbol de expansión que tiene el mayor número posible de hojas entre todos los árboles de expansión de G. El número máximo de hojas de G es el número de hojas en el árbol de máxima extensión de hojas. [2]
Si d es el número de dominación conectado de un gráfico de n -vértices G , donde n > 2 , y l es su número máximo de hojas, entonces las tres cantidades d , l y n obedecen a la ecuación simple
Si D es un conjunto dominante conexo, entonces existe un árbol generador en G cuyas hojas incluyen todos los vértices que no están en D : forma un árbol generador del subgrafo inducido por D , junto con los bordes que conectan cada vértice restante v que no está en D a un vecino de v en D . Esto muestra que l ≥ n − d .
En la otra dirección, si T es cualquier árbol generador en G , entonces los vértices de T que no son hojas forman un conjunto dominante conectado de G. Esto muestra que n − l ≥ d . Al juntar estas dos desigualdades se demuestra la igualdad n = d + l .
Por lo tanto, en cualquier gráfico, la suma del número de dominación conectado y el número máximo de hojas es igual al número total de vértices. Computacionalmente, esto implica que determinar el número de dominación conectado es tan difícil como encontrar el número máximo de hojas.
Es NP-completo probar si existe un conjunto dominante conectado con un tamaño menor que un umbral determinado, o de manera equivalente probar si existe un árbol de expansión con al menos un número determinado de hojas. Por lo tanto, se cree que el problema del conjunto dominante mínimo conectado y el problema del árbol de máxima extensión de hojas no pueden resolverse en tiempo polinomial.
Cuando se ven en términos de algoritmos de aproximación, los árboles de dominancia conectada y de máxima extensión de hojas no son lo mismo: aproximar uno dentro de una relación de aproximación dada no es lo mismo que aproximar el otro a la misma relación. Existe una aproximación para el conjunto dominante mínimo conectado que logra un factor de 2 ln Δ + O(1) , donde Δ es el grado máximo de un vértice en G. [4] El problema del árbol de máxima extensión de hojas es MAX-SNP difícil , lo que implica que no es probable que exista ningún esquema de aproximación de tiempo polinomial . [5] Sin embargo, se puede aproximar dentro de un factor de 2 en tiempo polinómico. [6]
Ambos problemas pueden resolverse, en gráficos de n -vértices, en el tiempo O (1,9 n ) . [7] El problema de la hoja máxima es manejable de parámetros fijos , lo que significa que se puede resolver en el tiempo exponencial en el número de hojas pero solo polinomial en el tamaño del gráfico de entrada. El valor klam de estos algoritmos (intuitivamente, un número de hojas hasta el cual el problema puede resolverse dentro de un período de tiempo razonable) ha aumentado gradualmente, a medida que los algoritmos para el problema han mejorado, hasta aproximadamente 37, [8] y ha Se ha sugerido que al menos 50 deberían ser alcanzables. [9]
En gráficos de grado máximo tres, el conjunto dominante conectado y su problema de árbol de expansión de hojas máximo complementario se pueden resolver en tiempo polinomial , transformándolos en una instancia del problema de paridad matroide para matroides lineales . [10]
Los conjuntos dominantes conectados son útiles en el cálculo del enrutamiento para redes móviles ad hoc . En esta aplicación, se utiliza un pequeño conjunto dominante conectado como columna vertebral para las comunicaciones, y los nodos que no están en este conjunto se comunican pasando mensajes a través de vecinos que están en el conjunto. [11]
El número máximo de hojas se ha empleado en el desarrollo de algoritmos manejables de parámetros fijos : varios problemas de optimización NP-hard pueden resolverse en tiempo polinomial para gráficos de número máximo de hojas acotado. [2]
