Gráfico k-conectado de borde

Un grafo conectado por k aristas es un grafo que permanece conectado después de eliminar la mayoría de las aristas. $k-1$

A menudo, en lugar de un gráfico conexo por k bordes , se dice un gráfico conexo por k .

Formal definición

Sea cualquier gráfico. Si está conectado para todos , entonces se llama k -borde conectado. $G=(V,E)$ $G^\prime = (V, E \setminus X)$ $X \subseteq E$ $|X| <k$ $GRAMO$

Notas

Si un gráfico es conexo por los aristas k , entonces también es conexo por los aristas m para todo m < k .
Un grafo conexo es lo mismo que un grafo conexo de 1 arista.

Propiedades

El grado mínimo de vértices de un gráfico conectado por k aristas es al menos k .
Un grafo crítico con número cromático > k es k -borde- conectado.

Cálculo

Existe un algoritmo de polinomio de tiempo para determinar el k más grande para el cual el gráfico G es k -conexo por aristas. Como algoritmo simple, podemos usar lo siguiente: para cualquier par de vértices (u, v) , determinamos el flujo máximo de u a v con la capacidad de todos los bordes igual a uno en ambas direcciones. Un grafo es k -borde-conectado si y solo si el flujo máximo de u a v es al menos k para cualquier par (u, v) . Por lo tanto, k es el flujo uv más pequeño entre todos los pares (u, v) .

Si n es el número de vértices en el gráfico, este algoritmo simple se ejecuta en iteraciones del algoritmo de flujo máximo, que a su vez resuelve el problema de encontrar el flujo en el tiempo . Por lo tanto, la complejidad general del algoritmo es . $O(n^{2})$ $O(n^{3})$ $O(n^5)$

El algoritmo mejorado resuelve el problema de flujo máximo para cualquier par (u, v) donde u es un vértice fijo arbitrario y v pasa por todos los vértices restantes. Este algoritmo reduce la complejidad a . Si hay un corte más pequeño que k , separa a u de algún otro vértice. Puedes mejorar el algoritmo si aplicas el algoritmo Gabov , corriendo en el tiempo [1] . $O(n^{4})$ $O(n^{3})$

Un problema relacionado, encontrar un subgrafo mínimo k conectado por aristas de un grafo G (es decir, elegir la menor cantidad posible de aristas de G que formen un subgrafo k conectado por aristas) es NP-difícil para [2] . $k\geq 2$

Véase también

Notas

↑ Harold N. Gabow. Un enfoque matroide para encontrar conectividad perimetral y empaquetar arborescencias. Cómputo J. sist. ciencia , 50(2):259–273, 1995.
↑ MR Garey y DS Johnson. Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Freeman, San Francisco, CA, 1979.