Parámetro de conectividad teórica de grafos
En teoría de grafos , la fuerza de un gráfico no dirigido corresponde a la relación mínima de aristas eliminadas / componentes creados en una descomposición del gráfico 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 al gráfico de tenacidad que se define de manera similar para la eliminación de vértices.
Definiciones
La fuerza de un gráfico simple no dirigido G = ( V , E ) admite las tres definiciones siguientes:
- Sea el conjunto de todas las particiones de , y sea el conjunto de aristas que cruzan los conjuntos de la partición , entonces .
![{\displaystyle \Pi }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle V}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \partial \pi }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \pi \en \Pi }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Además, si es el conjunto de todos los árboles generadores de G , entonces
![{\displaystyle {\mathcal {T}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T} }\ \lambda _{T}\geq 0{\mbox{ y }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Y por la 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{ y }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Complejidad
El cálculo de la fuerza de un gráfico se puede realizar en tiempo polinómico, y el primer algoritmo de este tipo fue descubierto por Cunningham (1985). El algoritmo con mejor complejidad para calcular exactamente la fuerza se debe a Trubin (1993), utiliza la descomposición de flujo de Goldberg y Rao (1998), en el tiempo .![{\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Propiedades
- Si hay una partición que maximiza, y para , es la restricción de G al conjunto , entonces .
![{\displaystyle \pi =\{V_{1},\dots,V_{k}\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle i\in \{1,\dots ,k\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle G_{i}=G/V_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle V_{i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \sigma (G_ {k})\geq \sigma (G)}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- El teorema de Tutte-Nash-Williams: es el número máximo de árboles generadores de aristas disjuntas que pueden estar contenidos en G .
![{\displaystyle \lfloor \sigma (G)\rfloor }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Al contrario del problema de partición del gráfico , las particiones generadas al calcular la fuerza no están necesariamente equilibradas (es decir, son de 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 empaquetado de árboles y ramificaciones, Cybernetics and Systems Analysis, 29:379–384, 1993.