En matemáticas y ciencias de la computación , 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 relacionada con la teoría de problemas de flujo de red . La conectividad de un grafo es una medida importante de su resiliencia como red.
En un grafo no dirigido G , dos vértices u y v se denominan conexos si G contiene un camino desde u hasta v . De lo 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 una única arista), los vértices se denominan adyacentes .
Se dice que un grafo es conexo si cada par de vértices en el grafo es conexo. Esto significa que hay un camino entre cada par de vértices. Un grafo no dirigido que no es conexo se llama desconectado . Por lo tanto, un grafo no dirigido G está desconectado si existen dos vértices en G tales que ningún camino en G tiene estos vértices como puntos finales. Un grafo con un solo vértice es conexo. Un grafo sin aristas con dos o más vértices está desconectado.
Un grafo dirigido se denomina débilmente conexo si al reemplazar todas sus aristas dirigidas por aristas no dirigidas se obtiene un grafo conexo (no dirigido). Es unilateralmente conexo o unilateral (también llamado semiconexo ) 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 conexo es un subgrafo conexo máximo de un grafo no dirigido. Cada vértice pertenece a exactamente un componente conexo, al igual que cada arista. Un grafo es conexo si y solo si tiene exactamente un componente conexo.
Los componentes fuertes son los subgrafos fuertemente conectados máximos de un gráfico dirigido.
Un corte de vértice o conjunto separador de un grafo conexo G es un conjunto de vértices cuya eliminación hace que G quede desconectado. La conectividad de vértices κ ( G ) (donde G no es un grafo completo ) es el tamaño de un corte de vértice mínimo. Un grafo se denomina k -conexo por vértices o k -conexo si su conectividad de vértices es k o mayor.
Más precisamente, se dice que cualquier grafo G (completo o no) es k -conexo por vértices si contiene al menos k + 1 vértices, pero no contiene un conjunto de k − 1 vértices cuya eliminación desconecte el grafo; y κ ( G ) se define como el k más grande tal que G es k -conexo. En particular, un grafo completo con n vértices, denotado K n , no tiene cortes de vértices en absoluto, 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 grafo desconecta u y v . La conectividad local κ ( u , v ) es el tamaño de un corte de vértice más pequeño que separa u y v . La conectividad local es simétrica para grafos no dirigidos; es decir, κ ( u , v ) = κ ( v , u ) . Además, excepto para grafos completos, κ ( G ) es igual al mínimo de κ ( u , v ) sobre todos los pares no adyacentes de vértices u , v .
La 2 -conectividad también se denomina biconectividad y la 3 -conectividad también se denomina triconectividad . Un grafo G que está conectado pero no es 2 -conexo a veces se denomina separable .
Se pueden definir conceptos análogos para las aristas. En el caso simple en el que cortar una única arista específica desconectaría el grafo, esa arista se llama puente . De manera más general, un corte de arista de G es un conjunto de aristas cuya eliminación hace que el grafo quede desconectado. La conectividad de aristas λ ( G ) es el tamaño de un corte de arista más pequeño, y la conectividad de aristas local λ ( u , v ) de dos vértices u , v es el tamaño de un corte de arista más pequeño que desconecta u de v . Nuevamente, la conectividad de aristas local es simétrica. Un grafo se llama k -aristas conexas si su conectividad de aristas es k o mayor.
Se dice que un grafo está máximamente conectado si su conectividad es igual a su grado mínimo . Se dice que un grafo está máximamente conectado por sus aristas si su conectividad por sus aristas es igual a su grado mínimo. [3]
Se dice que un grafo es superconectado o super-κ si cada corte mínimo de vértice aísla un vértice. Se dice que un grafo 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 grafo es semihiperconectado o semihiper-κ si cualquier corte mínimo de vértice separa el grafo en exactamente dos componentes. [4]
Más precisamente: se dice que un grafo G conexo es superconexo o super-κ si todos los cortes de vértice mínimos consisten en los vértices adyacentes a un vértice (de grado mínimo). Se dice que un grafo G conexo es superconexo por aristas o super-λ si todos los cortes de aristas mínimos consisten en las aristas incidentes en algún vértice (de grado mínimo). [5]
Un conjunto de corte X de G se denomina conjunto de corte no trivial si X no contiene la vecindad N( u ) de ningún vértice u ∉ X . Entonces la superconectividad de G es
Un corte de arista no trivial y la superconectividad de aristas se definen de forma análoga. [6]
Uno de los hechos más importantes sobre la conectividad en grafos es el teorema de Menger , que caracteriza la conectividad y la conectividad de las aristas de un grafo en términos del número de caminos independientes entre vértices.
Si u y v son vértices de un grafo 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 (excepto u y v ). De manera similar, la colección es independiente de las aristas si no hay dos caminos en ella que compartan una arista. El número de caminos mutuamente independientes entre u y v se escribe como κ ′( u , v ) , y el número de caminos mutuamente independientes de las aristas entre u y v se escribe como λ ′( u , v ) .
El teorema de Menger afirma que para vértices distintos 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 flujo máximo y corte mínimo .
El problema de determinar si dos vértices de un grafo están conectados se puede resolver de manera eficiente utilizando un algoritmo de búsqueda , como la búsqueda en amplitud . En términos más generales, es fácil determinar computacionalmente si un grafo está conectado (por ejemplo, utilizando una estructura de datos de conjunto disjunto ) o contar el número de componentes conectados. Un algoritmo simple podría escribirse en pseudocódigo de la siguiente manera:
Por el teorema de Menger , para dos vértices cualesquiera u y v en un grafo conexo G , los números κ ( u , v ) y λ ( u , v ) se pueden determinar de manera eficiente utilizando el algoritmo de flujo máximo y corte mínimo . La conectividad y la conectividad de aristas de G se pueden calcular entonces 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 reducibles en el espacio logarítmico al problema de determinar si dos vértices en un gráfico están conectados, lo cual fue demostrado que era igual a L por Omer Reingold en 2004. [9] Por lo tanto, la conectividad de gráficos no dirigidos se puede resolver en el espacio O(log n ) .
El problema de calcular la probabilidad de que un grafo aleatorio de Bernoulli esté conectado se denomina confiabilidad de red y el problema de calcular si dos vértices dados están conectados se denomina problema de confiabilidad ST. Ambos son de nivel P -hard. [10]
El número de grafos etiquetados conectados distintos con n nodos se tabula en la Enciclopedia en línea de secuencias de enteros como secuencia A001187. Los primeros términos no triviales son
