Potencia gráfica

La cardinalidad de un gráfico no dirigido es una característica del gráfico igual a la relación mínima entre el número de aristas eliminadas del gráfico y el número de componentes obtenidos como resultado de dicha eliminación (reducido en 1). Este método le permite identificar áreas de alta concentración de bordes. La cardinalidad de un gráfico es similar al concepto de rigidez del gráfico , que, sin embargo, se determina a través del procedimiento para eliminar vértices, no bordes.

Definiciones

La cardinalidad de un gráfico simple no dirigido se puede definir de tres formas equivalentes: ${\ estilo de visualización \ sigma (G)}$ $G=(V,E)$

Sea el conjunto de todas las particiones del conjunto . Para dividir , denotar como un conjunto de aristas que conectan vértices de diferentes componentes . entonces _ $\Pi$ $V$ ${\ estilo de visualización \ pi \ en \ Pi}$ ${\ estilo de visualización \ parcial \ pi}$ $\Pi$ $\displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\parcial \pi |}{|\pi |-1))$
Sea el conjunto de todos los árboles generadores del grafo . Después ${\mathcal {T}}$ $GRAMO$

\sigma (G)=\max \left\{\sum _{T\in {\mathcal {T))}\lambda _{T}\ :\ \forall T\in {\mathcal {T} }\ \lambda _{T}\geqslant 0;\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leqslant 1\right\}.

Según la dualidad de la programación lineal ,

\sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geqslant 0;\forall T\ en {\mathcal {T}}\ \sum _{e\in E}y_{e}\geqslant 1\right\}.

Dificultad

El cálculo de la cardinalidad de un gráfico se puede hacer en tiempo polinomial. El primer algoritmo polinomial fue descubierto por Cunningham (1985). Un algoritmo para calcular la potencia con la mejor complejidad, debido a Trubin (1993), utiliza la descomposición de flujo de Goldberg y Rao (1998) y corre en el tiempo . $O(\min({\sqrt {m)),n^{2/3})mn\log(n^{2}/m+2))$

Propiedades

Si es una partición maximizadora de razón y for es la restricción del grafo G al conjunto , entonces . ${\ estilo de visualización \ pi = \ {V_ {1}, \ puntos, V_ {k} \}}$ $i\in \{1,\dots,k\}$ $G_{i}=G/V_{i}$ $V_i$ ${\ estilo de visualización \ sigma (G_{k}) \ geqslant \ sigma (G)}$
El teorema de Tutt-Nash-Williams: es el número máximo de árboles de expansión disjuntos por aristas que pueden estar contenidos en G . $\lpiso \sigma (G)\rpiso$
A diferencia del problema de partición de gráficos , los cálculos de cardinalidad de partición resultantes no están necesariamente equilibrados (es decir, tienen casi el mismo tamaño).

Literatura

Cunningham WH Ataque óptimo y refuerzo de una red // J de ACM. - 1985. - Edición. 32 . - S. 549-561 .
Alejandro Schrijver. Capítulo 51 // Optimización combinatoria. Poliedros y Eficiencia . - Springer, 2003. - ISBN 978-3-540-44389-6 .
Trubin VA Fuerza de un grafo y empaquetamiento de árboles y ramificaciones // Cibernética y Análisis de Sistemas. - 1993. - Edición. 29 . - S. 379-384 .