El aumento de conectividad fuerte es un problema computacional en el estudio matemático de algoritmos de gráficos , en el que la entrada es un gráfico dirigido y el objetivo del problema es agregar una pequeña cantidad de aristas, o un conjunto de aristas con un peso total pequeño, de modo que las aristas agregadas conviertan el gráfico en un gráfico fuertemente conectado .
El problema de aumento de conectividad fuerte fue formulado por Kapali Eswaran y Robert Tarjan (1976). Demostraron que una versión ponderada del problema es NP-completa, pero el problema no ponderado puede resolverse en tiempo lineal . [1] Investigaciones posteriores han considerado la relación de aproximación y la complejidad parametrizada del problema ponderado. [2] [3]
En el problema de aumento de conectividad fuerte no ponderado, la entrada es un grafo dirigido y el objetivo es agregarle la menor cantidad posible de aristas para convertir el resultado en un grafo fuertemente conectado. El algoritmo para el caso no ponderado de Eswaran y Tarjan considera la condensación del grafo dirigido dado, un grafo acíclico dirigido que tiene un vértice por componente fuertemente conectado del grafo dado. Dejando denotar el número de vértices de origen en la condensación (componentes fuertemente conectados con al menos una arista saliente pero sin aristas entrantes), denotar el número de vértices sumideros en la condensación (componentes fuertemente conectados con aristas entrantes pero sin aristas salientes) y denotar el número de vértices aislados en la condensación (componentes fuertemente conectados sin aristas entrantes ni salientes), observan que la cantidad de aristas que se deben agregar es necesariamente al menos . Esto se deduce porque es necesario agregar aristas para proporcionar una arista entrante para cada vértice de origen o aislado, y simétricamente es necesario agregar al menos aristas para proporcionar una arista saliente para cada sumidero o vértice aislado. Su algoritmo para el problema encuentra un conjunto de aristas exactas para agregar al gráfico para hacerlo fuertemente conectado. [1]
Su algoritmo utiliza una búsqueda en profundidad en la condensación para encontrar una colección de pares de fuentes y sumideros, con las siguientes propiedades: [1]
Posteriormente se encontró y corrigió un error menor en la parte de su algoritmo que encuentra los pares de fuentes y sumideros. [4]
Una vez encontrados estos pares, se puede obtener un fuerte aumento de la conectividad añadiendo tres conjuntos de aristas: [1]
El número total de aristas en estos tres conjuntos es . [1]
La versión ponderada del problema, en la que cada arista que se puede agregar tiene un peso dado y el objetivo es elegir un conjunto de aristas agregadas de peso mínimo que haga que el gráfico dado sea fuertemente conectado, es NP-completo. [1] Frederickson y Ja'Ja' (1981) proporcionaron un algoritmo de aproximación con una razón de aproximación de 2. [2] Una versión parametrizada y ponderada del problema, en la que uno debe agregar como máximo aristas de peso total mínimo para hacer que el gráfico dado sea fuertemente conectado, es manejable con parámetros fijos . [3]
Si una cuadrícula cuadrada está formada por barras rígidas (los bordes de la cuadrícula) conectadas entre sí por juntas flexibles en los bordes de la cuadrícula, entonces la estructura general puede doblarse de muchas maneras en lugar de permanecer cuadrada. El problema del arriostramiento de la cuadrícula plantea la cuestión de cómo estabilizar dicha estructura añadiendo arriostramientos transversales adicionales dentro de algunos de sus cuadrados. Este problema se puede modelar utilizando la teoría de grafos, haciendo un grafo bipartito con un vértice para cada fila o columna de cuadrados en la cuadrícula, y una arista entre dos de estos vértices cuando un cuadrado en una fila y columna dadas está arriostrado transversalmente. Si el arriostramiento transversal dentro de cada cuadrado hace que éste sea completamente rígido, entonces este grafo no está dirigido y representa una estructura rígida si y solo si es un grafo conexo . [5] Sin embargo, si los cuadrados están arriostrados solo parcialmente (por ejemplo, conectando dos esquinas opuestas mediante una cuerda o alambre que evita el movimiento expansivo pero no evita el movimiento contractivo), entonces el grafo está dirigido y representa una estructura rígida si y solo si es un grafo fuertemente conexo. [6]
Un problema de aumento de conectividad fuerte asociado plantea la pregunta de cómo agregar más arriostramientos parciales a una cuadrícula que ya tiene arriostramientos parciales en algunos de sus cuadrados. Los arriostramientos parciales existentes se pueden representar como un gráfico dirigido, y los arriostramientos parciales adicionales que se agreguen deben formar un aumento de conectividad fuerte de ese gráfico. Para poder traducir una solución al problema de aumento de conectividad fuerte de nuevo a una solución del problema de arriostramiento original, se requiere una restricción adicional: cada borde agregado debe respetar la bipartición del gráfico original y solo conectar vértices de fila con vértices de columna en lugar de intentar conectar filas con filas o columnas con columnas. Esta versión restringida del problema de aumento de conectividad fuerte se puede resolver nuevamente en tiempo lineal. [7]
