Conectividad (teoría de grafos)

Este gráfico se desconecta cuando se elimina el borde punteado.

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.

Vértices y gráficos conectados

Con vértice 0, este grafo está desconectado. El resto del grafo está conectado.

En un grafo no dirigido $G$ , dos vértices $u$ y $v$ se denominan conexos si $G$ contiene un camino de $u$ a $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$ .

Componentes y cortes

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 grafo 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 del corte de vértice más pequeño. 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 las aristas es igual a su grado mínimo. ^[3]

Superconectividad e hiperconectividad

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 \notin X$ . Entonces la superconectividad de $G$ es $estilo de visualización kappa _{1}$ $\kappa _{1}(G)=\min\{|X|:X{\text{ es un conjunto de corte no trivial}}\}.$

Un corte de arista no trivial y la superconectividad de aristas se definen de forma análoga. ^[6] $\lambda _ {1}(G)$

Teorema de Menger

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 .

Aspectos computacionales

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:

Comience en cualquier nodo arbitrario del gráfico $G.$
Proceda desde ese nodo utilizando una búsqueda en profundidad o en amplitud, contando todos los nodos alcanzados.
Una vez recorrido completamente el grafo, si el número de nodos contados es igual al número de nodos de $G$ , el grafo está conexo; en caso contrario, está desconectado.

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]

Número de gráficos conectados

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

Ejemplos

Las conectividades de vértices y aristas de un gráfico desconectado son ambas $0$ .
$1$ -La conectividad es equivalente a la conectividad para gráficos de al menos dos vértices.
El grafo completo sobre $n$ vértices tiene una conectividad de aristas igual a $n - 1.$ Cualquier otro grafo simple sobre $n$ vértices tiene una conectividad de aristas estrictamente menor.
En un árbol , la conectividad de aristas locales entre dos vértices distintos es $1$ .

Límites a la conectividad

La conectividad de vértices de un grafo es menor o igual que su conectividad de aristas. Es decir, $κ (G) \leq λ (G)$ .
La conectividad de los bordes de un gráfico con al menos 2 vértices es menor o igual al grado mínimo del gráfico porque eliminar todos los bordes que inciden en un vértice de grado mínimo desconectará ese vértice del resto del gráfico. ^[1]
Para un grafo transitivo de vértice de grado $d$ , tenemos: $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ . ^[11]
Para un grafo transitivo de vértice de grado $d \leq 4$ , o para cualquier grafo de Cayley mínimo (no dirigido) de grado $d$ , o para cualquier grafo simétrico de grado $d$ , ambos tipos de conectividad son iguales: $κ (G) = λ (G) = d$ . ^[12]

Otras propiedades

La conectividad se preserva mediante homomorfismos de grafos .
Si $G$ está conexo, entonces su gráfico lineal $L (G)$ también está conexo.
Un grafo $G$ es conexo por $2$ aristas si y sólo si tiene una orientación que está fuertemente conexa.
El teorema de Balinski establece que el grafo politópico ( $1$ - esqueleto ) de un politopo convexo de dimensión $k$ es un grafo conexo por vértices $k .$ ^[13] El teorema anterior de Steinitz de que cualquier grafo plano conexo por 3 vértices es un grafo politópico ( teorema de Steinitz ) da una inversa parcial .
Según un teorema de GA Dirac , si un grafo es $k$ -conexo para $k \geq 2$ , entonces para cada conjunto de $k$ vértices en el grafo hay un ciclo que pasa por todos los vértices del conjunto. ^[14]^[15] Lo contrario es cierto cuando $k = 2$ .

Véase también

Referencias

^ ab Diestel, R. (2005). "Teoría de grafos, edición electrónica". pág. 12.
^ Capítulo 11: Dígrafos: Principio de dualidad para dígrafos: Definición
^ Gross, Jonathan L.; Yellen, Jay (2004). Manual de teoría de grafos. CRC Press . p. 335. ISBN. 978-1-58488-090-5.
^ Liu, Qinghai; Zhang, Zhao (1 de marzo de 2010). "La existencia y el límite superior para dos tipos de conectividad restringida". Matemáticas Aplicadas Discretas . 158 (5): 516–521. doi : 10.1016/j.dam.2009.10.017 .
^ Gross, Jonathan L.; Yellen, Jay (2004). Manual de teoría de grafos. CRC Press . p. 338. ISBN. 978-1-58488-090-5.
^ Balbuena, Camino; Carmona, Angeles (1 de octubre de 2001). "Sobre la conectividad y superconectividad de dígrafos y grafos bipartitos". Ars Combinatorica . 61 : 3–22. CiteSeerX 10.1.1.101.1458 .
^ Gibbons, A. (1985). Teoría algorítmica de grafos . Cambridge University Press .
^ Nagamochi, H.; Ibaraki, T. (2008). Aspectos algorítmicos de la conectividad de grafos . Cambridge University Press.
^ Reingold, Omer (2008). "Conectividad no dirigida en el espacio logarítmico". Revista de la ACM . 55 (4): 1–24. doi :10.1145/1391289.1391291. S2CID 207168478.
^ Provan, J. Scott; Ball, Michael O. (1983). "La complejidad de contar cortes y de calcular la probabilidad de que un grafo esté conectado". Revista SIAM de Computación . 12 (4): 777–788. doi :10.1137/0212053. MR 0721012..
^ Godsil, C. ; Royle, G. (2001). Teoría de grafos algebraicos . Springer Verlag.
^ Babai, L. (1996). Grupos de automorfismos, isomorfismo, reconstrucción. Informe técnico TR-94-10. Universidad de Chicago. Archivado desde el original el 11 de junio de 2010.Capítulo 27 del Manual de Combinatoria .
^ Balinski, ML (1961). "Sobre la estructura gráfica de poliedros convexos en el espacio n". Revista del Pacífico de Matemáticas . 11 (2): 431–434. doi : 10.2140/pjm.1961.11.431 .
^ Dirac, Gabriel Andrés (1960). "En abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten . 22 (1–2): 61–85. doi :10.1002/mana.19600220107. SEÑOR 0121311..
^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). "Una generalización del teorema de Dirac sobre ciclos a través de k vértices en grafos k-conexos". Matemáticas discretas . 307 (7–8): 878–884. doi : 10.1016/j.disc.2005.11.052 . MR 2297171..