En matemáticas e informática , la conectividad es uno de los conceptos básicos de la teoría de grafos : pide el número mínimo de elementos (nodos o aristas) que deben eliminarse para separar los nodos restantes en dos o más subgrafos aislados . [1] Está estrechamente relacionado con la teoría de los problemas de flujo de red . La conectividad de un gráfico es una medida importante de su resiliencia como red.
En un gráfico no dirigido G , dos vértices u y v se llaman conectados si G contiene un camino de u a v . En caso contrario, se denominan desconectados . Si los dos vértices están conectados adicionalmente por un camino de longitud 1 (es decir, son los puntos finales de un solo borde), los vértices se llaman adyacentes .
Se dice que un grafo es conexo si cada par de vértices del grafo es conexo. Esto significa que existe un camino entre cada par de vértices. Un grafo no dirigido que no está conexo se llama desconectado . Por lo tanto, un gráfico no dirigido G está desconectado si existen dos vértices en G tales que ningún camino en G tenga estos vértices como puntos finales. Un gráfico con un solo vértice es conexo. Un gráfico sin aristas con dos o más vértices está desconectado.
Un gráfico dirigido se llama débilmente conexo si al reemplazar todas sus aristas dirigidas con aristas no dirigidas se produce un gráfico conexo (no dirigido). Es unilateralmente conexo o unilateral (también llamado semiconectado ) si contiene un camino dirigido de u a v o un camino dirigido de v a u para cada par de vértices u, v . [2] Es fuertemente conexo , o simplemente fuerte, si contiene un camino dirigido de u a v y un camino dirigido de v a u para cada par de vértices u, v .
Un componente conectado es un subgrafo conectado máximo de un gráfico no dirigido. Cada vértice pertenece exactamente a un componente conectado, al igual que cada arista. Un grafo es conexo si y sólo si tiene exactamente un componente conexo.
Los componentes fuertes son los subgrafos máximos fuertemente conectados de un gráfico dirigido.
Un corte de vértices o un conjunto de separación de un gráfico conectado G es un conjunto de vértices cuya eliminación hace que G sea desconectado. La conectividad de vértice κ ( G ) (donde G no es un gráfico completo ) es el tamaño de un corte de vértice mínimo. Un gráfico se llama k -conectado a vértice o k -conectado si su conectividad de vértice es k o mayor.
Más precisamente, se dice que cualquier gráfico G (completo o no) está k -conectado por vértices si contiene al menos k +1 vértices, pero no contiene un conjunto de k − 1 vértices cuya eliminación desconecta el gráfico; y κ ( G ) se define como el k más grande tal que G está k -conectado. En particular, un gráfico completo con n vértices, denotado K n , no tiene ningún corte de vértice, pero κ ( K n ) = n − 1 .
Un corte de vértice para dos vértices u y v es un conjunto de vértices cuya eliminación del gráfico desconecta u y v . La conectividad local κ ( u , v ) es el tamaño del corte de vértice más pequeño que separa u y v . La conectividad local es simétrica para gráficos no dirigidos; es decir, κ ( u , v ) = κ ( v , u ) . Además, excepto en el caso de gráficas completas, κ ( G ) es igual al mínimo de κ ( u , v ) sobre todos los pares de vértices no adyacentes u, v .
La 2 -conectividad también se llama biconectividad y la 3 -conectividad también se llama triconectividad . Un gráfico G que es conexo pero no conexo por 2 a veces se llama separable .
Se pueden definir conceptos análogos para las aristas. En el caso simple en el que cortar un solo borde específico desconectaría el gráfico, ese borde se llama puente . De manera más general, un corte de aristas de G es un conjunto de aristas cuya eliminación desconecta el gráfico. La conectividad de borde λ ( G ) es el tamaño de un corte de borde más pequeño, y la conectividad de borde local λ ( u , v ) de dos vértices u, v es el tamaño de un corte de borde más pequeño que desconecta u de v . Nuevamente, la conectividad de borde local es simétrica. Un gráfico se llama k -conectado por bordes si su conectividad de bordes es k o mayor.
Se dice que un grafo es máximamente conexo si su conectividad es igual a su grado mínimo. Se dice que un gráfico tiene máxima conexión de bordes si su conectividad de bordes es igual a su grado mínimo. [3]
Se dice que un gráfico es superconexo o super-κ si cada corte mínimo de vértice aísla un vértice. Se dice que un gráfico es hiperconectado o hiper-κ si la eliminación de cada corte mínimo de vértice crea exactamente dos componentes, uno de los cuales es un vértice aislado. Un gráfico es semi-hiperconectado o semi-hiper-κ si cualquier corte mínimo de vértice separa el gráfico en exactamente dos componentes. [4]
Más precisamente: un gráfico G conectado se dice que es superconectado o super-κ si todos los cortes de vértices mínimos consisten en vértices adyacentes a un vértice (de grado mínimo). Se dice que un gráfico conectado G está súper conectado por aristas o súper λ si todos los cortes de aristas mínimos consisten en aristas incidentes en algún vértice (de grado mínimo). [5]
Un conjunto de cortes X de G se denomina conjunto de cortes no trivial si X no contiene la vecindad N(u) de cualquier vértice u ∉ X . Entonces la superconectividad κ1 de G es:
Un corte de borde no trivial y la superconectividad de borde λ1(G) se definen de manera análoga. [6]
Uno de los hechos más importantes sobre la conectividad en gráficos es el teorema de Menger , que caracteriza la conectividad y la conectividad de bordes de un gráfico en términos del número de caminos independientes entre los vértices.
Si u y v son vértices de un gráfico G , entonces una colección de caminos entre u y v se llama independiente si no hay dos de ellos que compartan un vértice (aparte de u y v ). De manera similar, la colección es independiente de los bordes si no hay dos rutas que compartan un borde. El número de caminos mutuamente independientes entre u y v se escribe como κ′ ( u , v ) , y el número de caminos mutuamente independientes entre u y v se escribe como λ′ ( u , v ) .
El teorema de Menger afirma que para distintos vértices u , v , λ ( u , v ) es igual a λ′ ( u , v ) , y si u tampoco es adyacente a v entonces κ ( u , v ) es igual a κ′ ( u , v ) . [7] [8] Este hecho es en realidad un caso especial del teorema de corte mínimo de flujo máximo .
El problema de determinar si dos vértices de un gráfico están conectados se puede resolver de manera eficiente utilizando un algoritmo de búsqueda , como la búsqueda en amplitud . De manera más general, es fácil determinar computacionalmente si un gráfico es conexo (por ejemplo, usando una estructura de datos de conjuntos disjuntos ) o contar el número de componentes conectados. Un algoritmo simple podría escribirse en pseudocódigo de la siguiente manera:
Según el teorema de Menger, para dos vértices cualesquiera u y v en un gráfico conectado G , los números κ ( u , v ) y λ ( u , v ) se pueden determinar de manera eficiente utilizando el algoritmo de corte mínimo de flujo máximo . La conectividad y la conectividad de borde de G pueden entonces calcularse como los valores mínimos de κ ( u , v ) y λ ( u , v ) , respectivamente.
En la teoría de la complejidad computacional , SL es la clase de problemas de espacio logarítmico reducible al problema de determinar si dos vértices en un gráfico están conectados, que Omer Reingold demostró que es igual a L en 2004. [9] Por lo tanto, gráfico no dirigido La conectividad se puede resolver en el espacio O (log n ) .
El problema de calcular la probabilidad de que un gráfico aleatorio de Bernoulli esté conectado se llama confiabilidad de la red y el problema de calcular si dos vértices dados están conectados se llama problema de confiabilidad ST. Ambos son #P -hard. [10]
El número de gráficos etiquetados conectados distintos con n nodos se tabula en la Enciclopedia en línea de secuencias enteras como secuencia A001187. Los primeros términos no triviales son
