Fuerza de un gráfico

Parámetro de conectividad de la teoría de grafos

En teoría de grafos , la fuerza de un grafo no dirigido corresponde a la proporción mínima de aristas eliminadas / componentes creados en una descomposición del grafo en cuestión. Es un método para calcular particiones del conjunto de vértices y detectar zonas de alta concentración de aristas, y es análogo a la tenacidad de un grafo, que se define de manera similar para la eliminación de vértices.

Definiciones

La fuerza de un grafo simple no dirigido G  = ( V ,  E ) admite las tres definiciones siguientes: ${\displaystyle \sigma (G)}$

• Sea el conjunto de todas las particiones de , y el conjunto de aristas que cruzan los conjuntos de la partición , entonces . ${\displaystyle \Pi }$ ${\displaystyle V}$ ${\displaystyle \partial \pi }$ ${\displaystyle \pi \in \Pi }$ ${\displaystyle \displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}}$
• Además, si es el conjunto de todos los árboles de expansión de G , entonces ${\displaystyle {\mathcal {T}}}$

${\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}$

• Y por dualidad de programación lineal,

${\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}$

Complejidad

El cálculo de la fuerza de un grafo se puede realizar en tiempo polinómico, y el primer algoritmo de este tipo fue descubierto por Cunningham (1985). El algoritmo con la mejor complejidad para calcular exactamente la fuerza se debe a Trubin (1993), que utiliza la descomposición del flujo de Goldberg y Rao (1998), en tiempo . ${\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}$

Propiedades

• Si es una partición que maximiza, y para , es la restricción de G al conjunto , entonces . ${\displaystyle \pi =\{V_{1},\dots ,V_{k}\}}$ ${\displaystyle i\in \{1,\dots ,k\}}$ ${\displaystyle G_{i}=G/V_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle \sigma (G_{k})\geq \sigma (G)}$
• El teorema de Tutte-Nash-Williams: es el número máximo de árboles de expansión sin aristas juntas que pueden estar contenidos en G. ${\displaystyle \lfloor \sigma (G)\rfloor }$
• A diferencia del problema de partición del gráfico , las particiones obtenidas al calcular la fuerza no están necesariamente equilibradas (es decir, no tienen un tamaño casi igual).

Referencias

• WH Cunningham. Ataque óptimo y refuerzo de una red, J of ACM, 32:549–561, 1985.
• A. Schrijver . Capítulo 51. Optimización combinatoria, Springer, 2003.
• VA Trubin. Fuerza de un gráfico y empaquetamiento de árboles y ramificaciones, Cybernetics and Systems Analysis, 29:379–384, 1993.