Conectividad (teoría de grafos)

En matemáticas e informática , la conectividad es uno de los conceptos básicos de la teoría de grafos : busca 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 en redes . 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 consideran conectados si G contiene un camino de u a v . En caso contrario, se consideran desconectados . Si además los dos vértices están conectados por un camino de longitud 1 (es decir, son los extremos de una misma arista), se consideran adyacentes .

Se dice que un grafo es conexo si cada par de vértices está conectado. Esto significa que existe un camino entre cada par de vértices. Un grafo no dirigido que no es conexo se denomina desconectado . Por lo tanto, un grafo no dirigido G es desconectado si existen dos vértices en G tales que ningún camino en G tiene estos vértices como extremos. Un grafo con un solo vértice es conexo. Un grafo sin aristas con dos o más vértices es desconectado.

Un grafo dirigido se denomina débilmente conectado si al reemplazar todas sus aristas dirigidas por aristas no dirigidas se obtiene un grafo conectado (no dirigido). Es unilateralmente conectado 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 conectado , 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 maximal de un grafo no dirigido. Cada vértice pertenece a un único componente conexo, al igual que cada arista. Un grafo es conexo si y solo si tiene un único componente conexo.

Los componentes fuertes son los subgrafos fuertemente conectados máximos de un grafo dirigido.

Un corte de vértices o conjunto separador de un grafo conexo G es un conjunto de vértices cuya eliminación hace que G se desconecte. La conectividad de vértices κ ( G ) (donde G no es un grafo completo ) es el tamaño del corte de vértices más pequeño. Un grafo se denomina k -conexo 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 mayor k tal que G es k- conexo. En particular, un grafo completo con n vértices, denotado K _n , no tiene cortes de vértices, 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 a u y v . La conectividad local κ ( u , v ) es el tamaño del corte de vértice más pequeño que separa a 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 conectividad 2 también se denomina biconectividad y la conectividad 3 también se denomina triconectividad . Un grafo G que es conexo pero no 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 denomina puente . De forma más general, un corte de arista de G es un conjunto de aristas cuya eliminación hace que el grafo se desconecte. La conectividad de aristas λ ( G ) es el tamaño del 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 del corte de aristas más pequeño que desconecta u de v . Nuevamente, la conectividad de aristas local es simétrica. Un grafo se denomina k -conexo por aristas si su conectividad de aristas 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 grafo es máximamente conexo por aristas si su conectividad por aristas es igual a su grado mínimo. ^{[ 3 ]}

Uno de los hechos más importantes sobre la conectividad en los grafos es el teorema de Menger , que caracteriza la conectividad y la conectividad de 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 un conjunto de caminos entre u y v se denomina independiente si ningún par de ellos comparte un vértice (aparte de u y v mismos). De manera similar, el conjunto es independiente de aristas si ningún par de caminos en él comparte 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 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 del corte mínimo de flujo máximo .

El problema de determinar si dos vértices de un grafo están conectados se puede resolver de manera eficiente mediante un algoritmo de búsqueda , como la búsqueda en anchura . De forma más general, es fácil determinar computacionalmente si un grafo está conectado (por ejemplo, utilizando una estructura de datos de conjuntos disjuntos ) o contar el número de componentes conectados. Un algoritmo sencillo podría escribirse en pseudocódigo de la siguiente manera:

1. Comience en cualquier nodo arbitrario del grafo G.
2. A partir de ese nodo, proceda utilizando una búsqueda en profundidad o en amplitud, contando todos los nodos alcanzados.
3. Una vez que se ha recorrido completamente el grafo, si el número de nodos contados es igual al número de nodos de G , el grafo está conectado; de lo contrario, está desconectado.

Según el teorema de Menger , para cualesquiera dos vértices u y v en un grafo conexo G , los valores κ ( u , v ) y λ ( u , v ) pueden determinarse eficientemente mediante el algoritmo de flujo máximo y corte mínimo . La conectividad y la conectividad de aristas de G pueden 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 reducibles en espacio logarítmico al problema de determinar si dos vértices en un grafo están conectados, que Omer Reingold demostró que es igual a L en 2004. [ ^{9 ] Por} lo tanto, la conectividad de grafos no dirigidos puede resolverse en un espacio O(log n ) .

El problema de calcular la probabilidad de que un grafo aleatorio de Bernoulli esté conectado se denomina fiabilidad de la red, y el problema de calcular si dos vértices dados están conectados se denomina problema de fiabilidad ST. Ambos son problemas #P -difíciles. ^{[ 10 ]}

Número de grafos 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 la secuencia A001187 . Los primeros términos no triviales son:

• Las conectividades de vértices y aristas de un grafo desconectado son ambas 0 .
• 1 - La conectividad es equivalente a la conectividad para grafos de al menos dos vértices.
• El grafo completo con n vértices tiene una conectividad de aristas igual a n − 1. Cualquier otro grafo simple con n vértices tiene una conectividad de aristas estrictamente menor.
• En un árbol , la conectividad de aristas local entre dos vértices distintos cualesquiera es 1 .

• La conectividad de vértices de un grafo es menor o igual que su conectividad de aristas. Es decir, κ ( G ) ≤ λ ( G ) .
• La conectividad de aristas para un grafo con al menos 2 vértices es menor o igual al grado mínimo del grafo porque eliminar todas las aristas incidentes a un vértice de grado mínimo desconectará ese vértice del resto del grafo. ^{[ 1 ]}
• Para un grafo transitivo de vértices de grado d , tenemos: 2( d + 1)/3 ≤ κ ( G ) ≤ λ ( G ) = d . ^{[ 11 ]}
• Para un grafo transitivo de vértices de grado d ≤ 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 ]}

• La conectividad se preserva mediante homomorfismos de grafos .
• Si G es conexo, entonces su gráfica lineal L ( G ) también es conexa.
• Un grafo G es 2- arista-conexo si y solo si tiene una orientación que es fuertemente conexa.
• El teorema de Balinski establece que el grafo politópico ( 1 - esqueleto ) de un politopo convexo k -dimensional es un grafo k -conexo por vértices. ^{[ 13 ]} El teorema anterior de Steinitz que establece que cualquier grafo planar 3-conexo por vértices es un grafo politópico ( teorema de Steinitz ) proporciona un recíproco parcial .
• Según un teorema de GA Dirac , si un grafo es k -conexo para k ≥ 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 .

• Conectividad algebraica
• Constante de Cheeger (teoría de grafos)
• Conectividad dinámica , estructura de datos de conjuntos disjuntos
• Gráfico expansor
• Fuerza de un gráfico