gráfico con conexión de k aristas

Gráfico que permanece conectado cuando se eliminan menos de k aristas

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

La conectividad de los bordes de un gráfico es el k más grande para el cual el gráfico está k -conectado por los bordes.

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

Definición formal

Un gráfico con dos aristas conectadas

Sea un grafo arbitrario. Si el subgrafo es conexo para todos los elementos donde , entonces se dice que G es k -arista conexo. La conectividad de arista de es el valor máximo k tal que G es k -arista conexo. El conjunto más pequeño X cuya eliminación desconecta a G es un corte mínimo en G . ${\displaystyle G=(V,E)}$ ${\displaystyle G'=(V,E\setminus X)}$ ${\displaystyle X\subseteq E}$ ${\displaystyle |X|<k}$ ${\displaystyle 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 en las aristas del grafo. Si y solo si cada dos vértices de G forman los puntos finales de k caminos, ninguno de los cuales comparte una arista con el otro, entonces G está k -conectado en las aristas. En una dirección esto es fácil: si existe un sistema de caminos como este, 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 que se elimine X. En la otra dirección, la existencia de un sistema de caminos para cada par de vértices en un grafo que no se puede desconectar mediante la eliminación de algunas aristas se puede demostrar utilizando el teorema de flujo máximo-corte mínimo de la teoría de flujos de red .

Conceptos relacionados

El grado mínimo de vértice proporciona un límite superior trivial para la conectividad de aristas. Es decir, si un grafo es k -conexo por aristas, 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. ${\displaystyle G=(V,E)}$

La conectividad de borde 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 plano es la conectividad de borde de su grafo dual , y viceversa. Estos conceptos están unificados en la teoría de matroides por 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 borde. ^[2]

Los grafos conexos por dos aristas 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 son precisamente estos los grafos que tienen una orientación fuerte . ^[3]

Aspectos computacionales

Existe un algoritmo de tiempo polinomial para determinar el k más grande para el cual un grafo G está k -conectado por aristas. 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 está k -conectado por aristas 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 del grafo, este algoritmo simple realizaría iteraciones del problema de flujo máximo, que se pueden resolver en el tiempo. Por lo tanto, la complejidad del algoritmo simple descrito anteriormente es total. ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{5})}$

Un algoritmo mejorado resolverá el problema de 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 y es sólido ya que, si existe un corte de capacidad menor que k , es inevitable que separe a u de algún otro vértice. Se puede mejorar aún más con un algoritmo de Gabow que se ejecuta en el peor de los casos . ^[4] ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

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 . ^[5] ${\displaystyle O(n^{2}\log ^{3}n)}$

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

Véase también

• grafo conexo con k vértices
• Conectividad (teoría de grafos)
• Preclusión coincidente

Referencias

1. Jordania, Camille (1869). "Sobre los ensamblajes de líneas". Journal für die reine und angewandte Mathematik (en francés). 70 (2): 185-190.
2. Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "Sobre la (co)circunferencia de un matroide conectado", Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR  2365057.
3. Robbins, HE (1939). "Un teorema sobre grafos, con una aplicación a un problema de control de tráfico". American Mathematical Monthly . 46 (5): 281–283. doi :10.2307/2303897. JSTOR  2303897.
4. Harold N. Gabow . Un enfoque matroide para encontrar conectividad de bordes y empaquetamiento de arborescencias. J. Comput. Syst. Sci. , 50(2):259–273, 1995.
5. Karger, David R. ; Stein, Clifford (1996). "Un nuevo enfoque para el problema del corte mínimo" (PDF) . Revista de la ACM . 43 (4): 601. doi :10.1145/234533.234534.
6. MR Garey y DS Johnson. Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Freeman, San Francisco, CA, 1979.