gráfico conectado por aristas k

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

En teoría de grafos , un gráfico conexo está k conectado por aristas si permanece conectado siempre que se eliminen menos de k aristas.

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

Camille Jordan estudió la conectividad de borde y la enumeración de k gráficos conectados por borde en 1869. ^[1]

Definicion formal

Un gráfico conectado con 2 aristas

Sea un gráfico arbitrario. Si el subgrafo es conexo para todos los donde , entonces se dice que G es k -conexo por aristas. La conectividad de borde de es el valor máximo k tal que G está k conectado al borde. El conjunto más pequeño X cuya eliminación desconecta 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 bordes del teorema de Menger proporciona una caracterización alternativa y equivalente, en términos de caminos disjuntos de bordes en el gráfico. Si y solo si cada dos vértices de G forman los puntos finales de k caminos, ninguno de los cuales comparte un borde entre sí, entonces G está k conectado por bordes. 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 está separado 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 gráfico que no puede desconectarse mediante la eliminación de algunas aristas se puede probar utilizando el teorema de flujo máximo y 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 bordes. Es decir, si un gráfico está k conectado por aristas, entonces es necesario que k  ≤ δ( G ), donde δ( G ) es el grado mínimo de cualquier vértice v  ∈  V . Eliminar todos los bordes incidentes en un vértice v desconectaría v del gráfico. ${\displaystyle G=(V,E)}$

La conectividad de borde es el concepto dual de circunferencia , la longitud del ciclo más corto en un gráfico, en el sentido de que la circunferencia de un gráfico plano es la conectividad de borde de su gráfico dual , y viceversa. Estos conceptos están unificados en la teoría matroide por la circunferencia de una matroide , el tamaño del conjunto dependiente más pequeño de la matroide. Para una matroide gráfica , la circunferencia de la matroide es igual a la circunferencia del gráfico subyacente, mientras que para una matroide cográfica es igual a la conectividad de borde. ^[2]

Las gráficas de 2 aristas conectadas también se pueden caracterizar por la ausencia de puentes , por la existencia de una descomposición del oído o por el teorema de Robbins según el cual estas son exactamente las gráficas 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 gráfico G está k conectado por bordes. Un algoritmo simple determinaría, para cada par (u,v) , el flujo máximo de u a v con la capacidad de todos los bordes en G establecida en 1 para ambas direcciones. Un gráfico está k conectado por bordes 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 (u,v) .

Si n es el número de vértices del gráfico, este algoritmo simple realizaría iteraciones del problema de flujo máximo, que se puede resolver en el tiempo. De ahí que la complejidad del algoritmo simple descrito anteriormente sea 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 se fija arbitrariamente mientras que v varía en todos los vértices. Esto reduce la complejidad a y es sensato ya que, si existe un corte de capacidad menor que k , seguramente separará 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 . ^[4] ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

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

Un problema relacionado: encontrar el subgrafo de expansión k mínimo conectado a los bordes de G (es decir: seleccione la menor cantidad posible de bordes en G para los que su selección esté conectada a los bordes k ) es NP-difícil . ^[6] ${\displaystyle k\geq 2}$

Ver también

• gráfico conectado a 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 una matroide conectada", Matemáticas aplicadas discretas , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR  2365057.
3. Robbins, ÉL (1939). "Un teorema sobre gráficas, con aplicación a un problema de control de tráfico". Mensual Matemático Estadounidense . 46 : 281–283. doi :10.2307/2303897. JSTOR  2303897.
4. Harold N. Gabow . Un enfoque matroide para encontrar conectividad de bordes y empaquetar arborescencias. J. Computación. Sistema. Ciencia. , 50(2):259–273, 1995.
5. Karger, David R .; Stein, Clifford (1996). "Un nuevo enfoque al problema del recorte 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, California, 1979.