Fuerza de un gráfico

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.

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 .${\estilo de visualización \Pi}$${\estilo de visualización V}$${\displaystyle \parcial \pi }$${\displaystyle \pi \en \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}\ :\ \para todo T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ y }}\para todo 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}\ :\ \para todo e\in E\ y_{e}\geq 0{\mbox{ y }}\para todo T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}$

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))}$

• Si es una partición que maximiza, y para , es la restricción de G al conjunto , entonces .${\displaystyle \pi =\{V_{1},\puntos ,V_{k}\}}$${\displaystyle i\en \{1,\puntos ,k\}}$${\displaystyle G_{i}=G/V_{i}}$$Estilo de visualización 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).

• 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.