Conectividad de borde

En teoría de grafos , un grafo conexo es k -arista-conexo si permanece conexo siempre que se eliminen menos de k aristas.

La conectividad de aristas de un grafo es el mayor valor de k para el cual el grafo es k -conectado por aristas.

La conectividad de aristas y la enumeración de grafos k -conectados por aristas fueron estudiadas por Camille Jordan en 1869. ^{[ 1 ]}

Dejar${\displaystyle G=(V,E)}$sea ​​un grafo arbitrario. Si el subgrafo${\displaystyle G'=(V,E\setminus X)}$está conectado para todos${\displaystyle X\subseteq E}$dónde${\displaystyle |X|<k}$, entonces se dice que G es k -conectado por aristas. La conectividad de aristas de${\displaystyle G}$es el valor máximo k tal que G es k -arista-conectado. El conjunto más pequeño X cuya eliminación desconecta G es un corte mínimo en G.

La versión de conectividad de aristas del teorema de Menger proporciona una caracterización alternativa y equivalente, en términos de caminos disjuntos por aristas en el grafo. Si y solo si cada par de vértices de G forman los extremos de k caminos, ninguno de los cuales comparte una arista entre sí, entonces G es k -arista-conexo. En una dirección esto es fácil: si existe un sistema de caminos de este tipo, entonces cada conjunto X de menos de k aristas es disjunto de al menos uno de los caminos, y el par de vértices permanece conectado entre sí incluso después de eliminar X. En la otra dirección, la existencia de un sistema de caminos para cada par de vértices en un grafo que no puede desconectarse eliminando unas pocas aristas puede demostrarse utilizando el teorema de flujo máximo-corte mínimo de la teoría de flujos de red .

El grado mínimo de vértice proporciona una cota superior trivial para la conectividad de aristas. Es decir, si un grafo${\displaystyle G=(V,E)}$Si k es k -arista-conectado, entonces es necesario que k  ≤  δ( G ), donde δ( G ) es el grado mínimo de cualquier vértice v  ∈ V . Eliminar todas las aristas incidentes a un vértice v desconectaría a v del grafo. 

La conectividad de aristas es el concepto dual de circunferencia , la longitud del ciclo más corto en un grafo, en el sentido de que la circunferencia de un grafo planar es la conectividad de aristas de su grafo dual , y viceversa. Estos conceptos se unifican en la teoría de matroides mediante la circunferencia de un matroide , el tamaño del conjunto dependiente más pequeño en el matroide. Para un matroide gráfico , la circunferencia del matroide es igual a la circunferencia del grafo subyacente, mientras que para un matroide cográfico es igual a la conectividad de aristas. ^{[ 2 ]}

Los grafos 2-aristas-conectados también pueden caracterizarse por la ausencia de puentes , por la existencia de una descomposición en orejas o por el teorema de Robbins según el cual estos son precisamente los grafos que tienen una fuerte orientación . ^{[ 3 ]}

Como corolario del teorema de Nash-Williams , la conectividad de aristas de un grafo proporciona límites sobre cuántos árboles de expansión disjuntos en aristas se pueden encontrar dentro del grafo.

Existe un algoritmo de tiempo polinomial para determinar el mayor k para el cual un grafo G es k -arista-conexo. Un algoritmo simple determinaría, para cada par (u,v) , el flujo máximo de u a v con la capacidad de todas las aristas en G establecida en 1 para ambas direcciones. Un grafo es k -arista-conexo si y solo si el flujo máximo de u a v es al menos k para cualquier par (u,v) , por lo que k es el menor flujo uv entre todos los (u,v) .

Si n es el número de vértices en el grafo, este sencillo algoritmo realizaría${\displaystyle O(n^{2})}$iteraciones del problema del flujo máximo, que se pueden resolver en${\displaystyle O(n^{3})}$tiempo. Por lo tanto, la complejidad del algoritmo simple descrito anteriormente es${\displaystyle O(n^{5})}$en total.

Un algoritmo mejorado resolverá el problema del flujo máximo para cada par (u,v) donde u es arbitrariamente fijo mientras que v varía en todos los vértices. Esto reduce la complejidad a${\displaystyle O(n^{4})}$y es sólido ya que, si existe un corte de capacidad menor que k , necesariamente separará a u de algún otro vértice. Se puede mejorar aún más mediante un algoritmo de Gabow que se ejecuta en el peor de los casos.${\displaystyle O(n^{3})}$tiempo. ^{[ 4 ]}

La variante Karger-Stein del algoritmo de Karger proporciona un algoritmo aleatorio más rápido para determinar la conectividad, con un tiempo de ejecución esperado${\displaystyle O(n^{2}\log ^{3}n)}$. ^{[ 5 ]}

Un problema relacionado: encontrar el subgrafo generador k -conectado por aristas mínimo de G (es decir: seleccionar la menor cantidad posible de aristas en G de modo que su selección sea k -conectada por aristas) es NP-difícil para${\displaystyle k\geq 2}$. ^{[ 6 ]}

• grafo k-vértice-conectado
• Conectividad (teoría de grafos)
• Preclusión coincidente