gráfico k-edge-connected
En la teoría de grafos , un grafo conexo tiene k aristas si permanece conectado siempre que se eliminen menos de k aristas.
Camille Jordan estudió la conectividad de bordes y la enumeración de k -grafos conectados por bordes en 1869. [1]
Sea un gráfico arbitrario. Si el subgrafo es conexo para todo donde , entonces G es k -conexo por arista. La conectividad de borde de es el valor máximo k tal que G es k -conectado al borde. El conjunto X más pequeño cuya eliminación desconecta G es un corte mínimo en 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 caminos, 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 caminos para cada par de vértices en un gráfico que no se puede desconectar mediante la eliminación de algunas aristas se puede demostrar utilizando el teorema de corte mínimo de flujo máximo de la teoría de flujos de red .
El grado de vértice mínimo da un límite superior trivial en la conectividad de borde. Es decir, si un grafo es k -conectado por aristas entonces es necesario que k ≤ δ( G ), donde δ( G ) es el grado mínimo de cualquier vértice v ∈ V . Obviamente, eliminar todas las aristas que inciden en un vértice, v , desconectaría v del gráfico.
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 de las matroides 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 del borde. [2]
