Producto en zig-zag

En la teoría de grafos, el producto en zigzag de gráficos regulares (denotado ) toma un gráfico grande y un gráfico pequeño y crea un gráfico aproximadamente del tamaño del gráfico grande pero con la potencia del pequeño. Una propiedad importante del producto en zigzag es que, para un buen expansor , la dispersión del gráfico resultante es sólo ligeramente peor que la dispersión del gráfico . ${\ estilo de visualización G, H}$ $G\circ H$ $GRAMO$ $H$ $H$ $GRAMO$

En términos generales, el producto en zigzag reemplaza cada vértice del gráfico con una copia (nube) del gráfico y conecta los vértices dando un pequeño paso (zig) dentro de la nube, y luego un gran paso (zag) entre las dos nubes, y otro pequeño paso dentro de la nube final. $G\circ H$ $GRAMO$ $H$

El producto en zigzag fue introducido por Reingold, Wadhan y Wigderson [1] . El producto en zigzag se usó originalmente para construir explícitamente expansores y extractores de grado constante. Posteriormente, el producto en zigzag se utilizó en la teoría de la complejidad computacional para demostrar la igualdad de SL y L [2] .

Definición

Sea un gráfico regular sobre c rotación , y sea un gráfico regular sobre c rotación mapeo . $GRAMO$ $D$ ${\ estilo de visualización [N]}$ ${\ Displaystyle \ mathrm {Rot} _ {G}}$ $H$ $d$ ${\ estilo de visualización [D]}$ ${\ Displaystyle \ mathrm {Rot} _ {H}}$

Un producto en zigzag se define como un gráfico regular sobre , cuya rotación se define de la siguiente manera : $G\circ H$ ${\ estilo de visualización d ^ {2}}$ ${\ estilo de visualización [N] \ veces [D]}$ $\mathrm {Rot}_{G\circ H}$
$\mathrm {Rot}_{G\circ H}((v,a),(i,j))$

$(a',i')=\mathrm {Rot} _{H}(a,i)$ .
$(w,b')=\mathrm {Rot} _{G}(v,a')$ .
$(b,j')=\mathrm {Rot} _{H}(b',j)$ .
$>\mathrm {Rot}_{G\circ H}((v,a),(i,j))=((w,b),(j',i'))$ .

Propiedades

Grado decreciente

De la definición del producto en zigzag se sigue directamente que el gráfico se transforma en un nuevo gráfico regular. Por lo tanto, si es sustancialmente mayor que , el producto en zigzag disminuye el grado de . $GRAMO$ ${\ estilo de visualización d ^ {2}}$ $GRAMO$ $H$ $GRAMO$

En términos generales, el producto en zigzag convierte cada vértice del gráfico en una nube del tamaño del gráfico y distribuye los arcos de cada vértice original a los vértices de la nube que lo reemplazó. $GRAMO$ $H$

Conservación de la brecha espectral

La dispersión de un gráfico se puede medir por su brecha espectral. Una propiedad importante del producto en zigzag es la conservación de la brecha espectral . Por lo tanto, si el expansor es "suficientemente bueno" (tiene una gran brecha espectral), entonces la dispersión del producto en zigzag está cerca de la dispersión original del gráfico . $H$ $GRAMO$

Formalmente: definido como cualquier gráfico de vértice -regular cuyo segundo valor propio más grande tiene un valor absoluto de al menos . ${\ estilo de visualización (N, D, \ lambda)}$ $D$ $norte$ $\lambda$

Sean — y — dos gráficas, entonces es una gráfica , donde . ${\ Displaystyle G_ {1}}$ ${\ estilo de visualización (N_ {1}, D_ {1}, \ lambda _ {1})}$ ${\ Displaystyle G_ {2}}$ ${\ estilo de visualización (D_{1}, D_ {2}, \ lambda _ {2})}$ $G\circ{z}H$ $(N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))$ $f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2})$

Preservación de la conectividad

El producto en zigzag funciona por separado para cada componente conectado del gráfico . $G\circ H$ $GRAMO$

Formalmente: sean dos gráficos dados: — -gráfico regular sobre y — -gráfico regular sobre . Si es un componente conexo del gráfico , entonces , donde es un subgráfico del gráfico formado por vértices (es decir, un gráfico sobre , que contiene todos los arcos entre los vértices de ). $GRAMO$ $D$ ${\ estilo de visualización [N]}$ $H$ $d$ ${\ estilo de visualización [D]}$ $S\subseteq [N]$ $GRAMO$ ${\displaystyle G|_{S}\circ H=G\circ H|_{S\times D))$ ${\ estilo de visualización G|_{S}}$ $GRAMO$ $S$ $S$ $GRAMO$ $S$

Aplicaciones

Construcción de expansores de grado constante

En 2002, Omer Reingold, Salil Wadhan y Avi Widgerson [3] mostraron una construcción combinatoria explícita simple de expansores de grado constante. La construcción se realiza iterativamente y requiere un expansor de grado constante como base. En cada iteración, el producto en zigzag se usa para crear otro gráfico cuyo tamaño aumenta, pero el grado y la distribución siguen siendo los mismos. Al repetir el proceso, se pueden crear expansores arbitrariamente grandes.

Resolviendo el problema de conectividad st no dirigida en un espacio de memoria logarítmica

En 2005, Ömer Reingold introdujo un algoritmo para resolver el problema de conectividad st , utilizando un espacio de memoria logarítmica. El problema es comprobar si existe un camino entre dos vértices dados de un grafo no dirigido. El algoritmo se basa en gran medida en el producto en zigzag.

En términos generales, para resolver el problema de conectividad no dirigida st en un espacio de memoria logarítmica, el gráfico original se transforma utilizando una combinación de un producto y un producto en zigzag en un gráfico regular de grado constante con un diámetro logarítmico. El producto aumenta la extensión (aumentando el diámetro) al aumentar el grado, y el producto en zigzag se usa para disminuir el grado mientras se mantiene la extensión.

Véase también

Operaciones en gráficos

Notas

↑ Reingold, Vadhan, Wigderson, 2000 , pág. 3-13.
↑ Omer Reingold. Conectividad no dirigida en log-space // Journal of the ACM . - 2008. - T. 55 , núm. 4 . - S. 24 . -doi : 10.1145/ 1391289.1391291 .
↑ Reingold, Vadhan, Wigderson, 2000 .

Literatura

Omer Reingold, Salil Vadhan, Avi Wigderson. proc. 41º Simposio IEEE sobre fundamentos de la informática (FOCS). - 2000. - S. 3-13 . -doi : 10.1109/ SFCS.2000.892006 .
Omer Reingold, Luca Trevisan, Salil Vadhan. proc. 38º Simposio ACM sobre Teoría de la Computación (STOC) . - 2006. - S. 457-466 . -doi : 10.1145/ 1132516.1132583 .