Conectividad (teoría de grafos)

En matemáticas y ciencias informáticas, conectividad es uno de los conceptos básicos de la teoría gráfica: pide el número mínimo de elementos (nodos o bordes) que necesitan ser eliminados para separar los nodos restantes en dos o más subgrafos aislados. Está estrechamente relacionada con la teoría de problemas de flujo de red. La conectividad de un gráfico es una medida importante de su resiliencia como red.

Vértices y gráficos conectados

En un gráfico no dirigido G, dos vértices estilo u y v se denominan conectados si G contiene una ruta desde u a v. De lo contrario, se denominan desconectados. Si los dos vértices están conectados adicionalmente por una ruta de longitud 1 (es decir, son los puntos finales de un solo borde), los vértices se llaman adyacentes.

Se dice que un gráfico está conexo si cada par de vértices del gráfico está conectado. Esto significa que existe un camino entre cada par de vértices. Un grafo no dirigido que no está conectado se llama desconectado. Por lo tanto, un gráfico no dirigido G está desconectado si existen dos vértices en G de modo que ninguna ruta 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 conectado si al reemplazar todos sus bordes dirigidos con bordes no dirigidos se produce un gráfico conectado (no dirigido). Está unilateralmente conectado o unilateral (también llamado semiconectado) si contiene una ruta dirigida desde u a v o una ruta dirigida desde v a u para cada par de vértices u, v. Está fuertemente conectado, o simplemente fuerte, si contiene una ruta dirigida desde u a v y una ruta dirigida desde v a u para cada par de vértices u,v.

Componentes y cortes

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értice o un conjunto separador de un gráfico conectado G es un conjunto de vértices cuya eliminación hace que G esté desconectado. La conectividad del 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-vertex-connected o k-conectado si su conectividad de vértice es k o mayor.

Más precisamente, cualquier gráfico G (completo o no) se dice que es k-vertex-connected 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 mayor k tal que G es k-conectado. En particular, un gráfico completo con n vértices, denotados como 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 estilo 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áficos completos, κ(G) es igual al mínimo de κ(u, v) sobre todos los pares de vértices no adyacentes u, v.

2 también se denomina biconectividad y la conectividad 3 también se denomina triconectividad. Un gráfico G que está conectado pero no 2 a veces se denomina separable.

Se pueden definir conceptos análogos para los bordes. En el caso simple en el que cortar un único borde específico desconectaría el gráfico, ese borde se llama puente. De manera más general, un corte de borde de G es un conjunto de bordes 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 del 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-edge-connected si su conectividad de borde 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 gráfico está máximamente conectado por los bordes si su conectividad de los bordes es igual a su grado mínimo.

Super e hiperconectividad

Se dice que un gráfico es superconectado 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-hiper-conectado o semi-hiper-κ si cualquier corte mínimo de vértice separa el gráfico en exactamente dos componentes.

Más precisamente: un gráfico conectado G se dice que está superconectado o super-κ si todos los cortes de vértices mínimos constan de vértices adyacentes a un vértice (de grado mínimo). Se dice que un gráfico G está super-edge-connected o super-λ si todos los cortes de borde mínimos consisten en los bordes incidentes en algún vértice (de grado mínimo).

Un corte X de G se denomina cutset no trivial si X no contiene la vecindad N (u) de cualquier vértice u ∉ X. Entonces la superconectividad κ1 de G es:

κ1(G) = min{ vidasX: X es un corte no-trivial}.

Un corte de borde no trivial y la superconectividad de borde λ1(G) se definen de manera análoga.

Teorema de Menger

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, luego una colección de rutas entre u y v se llaman independientes si no hay dos de ellos que compartan un vértice ( distintos de u y v ellos mismos). De manera similar, la colección es independiente de los bordes si no hay dos rutas que compartan un borde. El número de rutas mutuamente independientes entre u y v se escribe como κ′(u, v), y el número de rutas mutuamente independientes 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). Este hecho es en realidad un caso especial del teorema del corte mínimo del flujo máximo.

Aspectos computacionales

El problema de determinar si dos vértices en 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:

1. Comenzar en cualquier nodo arbitrario del gráfico, G
2. Procedido de ese nodo utilizando la primera o la primera búsqueda de profundidad, contando todos los nodos alcanzados.
3. Una vez que el gráfico ha sido completamente atravesado, si el número de nodos contados es igual al número de nodos de G, el gráfico está conectado; de lo contrario se desconecta.

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 puede determinar de manera eficiente utilizando el algoritmo de corte mínimo de flujo máximo. La conectividad y la conectividad de borde de G se pueden calcular 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, lo cual Omer Reingold demostró que es igual a L en 2004. Por lo tanto, el 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, el problema de confiabilidad ST. Ambos son #P-hard.

Número de gráficos conectados

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

Ejemplos

• Las conexiones de vértice y borde de un gráfico desconectado son ambas 0.
• 1-La conexión es equivalente a la conexión para gráficos de al menos 2 vértices.
• El gráfico completo en n vertices tiene la conectividad de borde igual a n − 1. Cada otro gráfico simple en n vertices tiene una conectividad de bordes estrictamente menor.
• En un árbol, la conectividad de borde local entre dos vértices distintos es 1.

Límites de la conectividad

• La conectividad del vértice de un gráfico es inferior o igual a su conectividad de borde. Eso es, κ()G≤ λ()G).
• La conectividad de borde para un gráfico con al menos 2 vértices es menor o igual al grado mínimo del gráfico porque la eliminación de todos los bordes que son incidentales a un vértice de grado mínimo desconectará ese vértice del resto del gráfico.
• Para un gráfico de grado de vertex-transitivo d, tenemos: 2(d + 1)/3 ≤ κ()G≤ λ()G) d.
• Para un gráfico de grado de vertex-transitivo d ≤ 4, o para cualquier (sin dirección) gráfico mínimo de Cayley de grado d, o para cualquier gráfico simétrico de grado d, ambos tipos de conectividad son iguales: κ()G) λ()G) d.

Otras propiedades

• La conexión se conserva por los homomorfismos graficos.
• Si G se conecta entonces su gráfico de línea L()G) también está conectado.
• Un gráfico G es 2-conectado por el aire si y sólo si tiene una orientación que está fuertemente conectada.
• El teorema de Balinski afirma que el gráfico politopal (1- esqueleto) de un k- politopa cónvex dimensional es un k- Gráfico conexion. El anterior teorema de Steinitz de que cualquier gráfico plano de 3 vértigos es un gráfico politopal (Teorema de Steinitz) da un converso parcial.
• Según un teorema de G. A. Dirac, si un gráfico es k- conectado para k ≥ 2, entonces para cada conjunto de k vertices en el gráfico hay un ciclo que pasa a través de todos los vértices en el conjunto. El contrario es cierto cuando k = 2.