gráfico conectado por k -edge

En la teoría de grafos , un conectado gráfico es k conectado--Edge si permanece conectado cada vez menos que k se eliminan bordes.

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

La conectividad de los bordes y la enumeración de gráficos conectados por bordes k fue estudiada por Camille Jordan en 1869. ^[1]

Definicion formal

Un gráfico de 2 bordes conectados

Sea un gráfico arbitrario. Si el subgrafo está conectado para todos los donde , entonces G está conectado por k -borde. La conectividad de borde de es el valor máximo k tal que G está k conectado por 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 borde del teorema de Menger proporciona una caracterización alternativa y equivalente, en términos de caminos disjuntos de borde en el gráfico. Si y solo si cada dos vértices de G forman los puntos finales de k trayectos, ninguno de los cuales comparte un borde entre sí, entonces G está conectado por k 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 es disjunto de al menos uno de los caminos, y el par de vértices permanece conectado entre sí incluso después de Xesta borrado. En la otra dirección, la existencia de un sistema de trayectorias para cada par de vértices en un gráfico que no se puede desconectar mediante la eliminación de unos pocos bordes se puede probar utilizando el teorema de flujo máximo y corte mínimo de la teoría de los flujos de red .

Conceptos relacionados

El grado mínimo de vértice proporciona un límite superior trivial en la conectividad de borde. Es decir, si un gráfico es k -Edge conectado, entonces es necesario que k  ≤ δ ( G ), donde δ ( G ) es el grado mínimo de cualquier vértice v  ∈  V . Obviamente, eliminar todos los bordes incidentes a 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 co-gráfica es igual a la conectividad del borde. ^[2]

Los gráficos conectados por 2 bordes también pueden caracterizarse por la ausencia de puentes , por la existencia de una descomposición de la oreja o por el teorema de Robbins según el cual estos son exactamente los gráficos que tienen una fuerte orientación . ^[3]

Aspectos computacionales

Existe un algoritmo de tiempo polinomial para determinar el k más grande para el cual un gráfico G está conectado por k bordes. Un algoritmo simple, para cada par (u, v) , determinaría el flujo máximo de u a v con la capacidad de todos los bordes en G establecida en 1 para ambas direcciones. Una gráfica está conectada por k 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 flujo de uv mínimo entre todos (u, v) .

Si n es el número de vértices en el gráfico, este algoritmo simple realizaría iteraciones del problema de flujo máximo, que se puede resolver a 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 se fija arbitrariamente mientras que v varía en todos los vértices. Esto reduce la complejidad ay es sólido ya que, si existe un corte de capacidad menor que k , está obligado a 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 Karger-Stein del algoritmo de Karger proporciona un algoritmo aleatorio más rápido para determinar la conectividad, con tiempo de ejecución esperado . ^[5]${\displaystyle O(n^{2}\log ^{3}n)}$

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

Ver también

• gráfico conectado al vértice k
• Conectividad (teoría de grafos)
• Preclusión coincidente

Referencias

1. Jordan, Camille (1869). "Sur les 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 de gráficos, con aplicación a un problema de control de tráfico". American Mathematical Monthly . 46 : 281-283. doi : 10.2307 / 2303897 . JSTOR 2303897 . 
4. Harold N. Gabow . Un enfoque matroide para encontrar conectividad de borde y arborescencias de empaque. J. Comput. Syst. Sci. , 50 (2): 259-273, 1995.
5. Karger, David R .; Stein, Clifford (1996). "Un nuevo enfoque al problema de corte mínimo" (PDF) . Revista de la ACM . 43 (4): 601. doi : 10.1145 / 234533.234534 .
6. MR Garey y DS Johnson. Las computadoras y la intratabilidad: una guía para la teoría de NP-Completeness . Freeman, San Francisco, CA, 1979.