En teoría de grafos , el producto en zig-zag de grafos regulares , denotado por , toma un gráfico grande () y un pequeño gráfico (), y produce un gráfico que hereda aproximadamente el tamaño del grande pero el grado del pequeño. Una propiedad importante del producto en zig-zag es que sies un buen expansor , entonces la expansión del gráfico resultante es solo un poco peor que la expansión de.
En términos generales, el producto en zig-zag reemplaza cada vértice de con una copia (nube) de , y conecta los vértices moviendo un pequeño paso (zig) dentro de una nube, seguido de un gran paso (zag) entre dos nubes, y finalmente realiza otro pequeño paso dentro de la nube de destino.
El producto en zigzag fue introducido por Reingold, Vadhan & Wigderson (2000) . Cuando se introdujo por primera vez el producto en zig-zag, se utilizó para la construcción explícita de expansores y extractores de grado constante. Más tarde, el producto en zig-zag se utilizó en la teoría de la complejidad computacional para demostrar que el espacio logarítmico y el espacio logarítmico simétrico son iguales ( Reingold 2008 ).
Definición
Dejar ser un -Gráfico regular en con mapa de rotacion y deja ser un -Gráfico regular en con mapa de rotacion . El producto zig-zag se define como el -Gráfico regular en cuyo mapa de rotación es como sigue:
:
- Dejar .
- Dejar .
- Dejar .
- Producción .
Propiedades
Reducción de la titulación
Es inmediato a partir de la definición del producto en zigzag que transforma un gráfico a un nuevo gráfico que es -regular. Así que si es significativamente mayor que , el producto en zigzag reducirá el grado de . En términos generales, amplificando cada vértice de en una nube del tamaño de de hecho, el producto divide los bordes de cada vértice original entre los vértices de la nube que lo reemplazan.
Preservación de la brecha espectral
La expansión de un gráfico se puede medir por su espacio espectral , con una propiedad importante del producto en zigzag la preservación del espacio espectral. Es decir, si es un expansor "suficientemente bueno" (tiene una gran brecha espectral), entonces la expansión del producto en zigzag está cerca de la expansión original de .
Formalmente: defina un -Gráfico como cualquier -Gráfico regular en vértices, cuyo segundo valor propio más grande (del paseo aleatorio asociado) tiene un valor absoluto como máximo .
Dejar ser un -grafo y ser un -Gráfico, luego es un -grafo, donde .
Preservación de la conectividad
El producto en zigzag opera por separado en cada componente conectado de .
Hablando formalmente, dados dos gráficos: , a -Gráfico regular en y , a -Gráfico regular en - Si es un componente conectado de luego , dónde es el subgrafo de Inducido por (es decir, el gráfico en que contiene todos los bordes en entre vértices en ).
Aplicaciones
Construcción de expansores de grado constante
En 2002, Omer Reingold, Salil Vadhan y Avi Wigderson dieron una construcción combinatoria simple y explícita de gráficos expansores de grado constante. La construcción es iterativa y necesita como bloque de construcción básico un solo expansor de tamaño constante. En cada iteración se utiliza el producto en zigzag para generar otro gráfico cuyo tamaño se incrementa pero su grado y expansión permanece sin cambios. Este proceso continúa, produciendo expansores arbitrariamente grandes.
De las propiedades del producto en zigzag mencionadas anteriormente, vemos que el producto de un gráfico grande con un gráfico pequeño, hereda un tamaño similar al gráfico grande y un grado similar al gráfico pequeño, conservando sus propiedades de expansión de ambos, por lo tanto permitiendo aumentar el tamaño del expansor sin efectos nocivos.
Resolviendo el problema de la conectividad st no dirigida en el espacio logarítmico
En 2005, Omer Reingold introdujo un algoritmo que resuelve el problema de la conectividad st no dirigida , el problema de probar si hay una ruta entre dos vértices dados en un gráfico no dirigido, utilizando solo espacio logarítmico. El algoritmo se basa en gran medida en el producto zigzag.
En términos generales, para resolver el problema de conectividad st no dirigido en el espacio logarítmico, el gráfico de entrada se transforma, utilizando una combinación de potencia y el producto en zigzag, en un gráfico regular de grado constante con un diámetro logarítmico. El producto de energía aumenta la expansión (por lo tanto, reduce el diámetro) al precio de aumentar el grado, y el producto en zigzag se usa para reducir el grado mientras se conserva la expansión.
Ver también
Referencias
- Reingold, O .; Vadhan, S .; Wigderson, A. (2000), "Ondas de entropía, el producto gráfico en zig-zag y nuevos expansores y extractores de grado constante", Proc. 41 ° Simposio de IEEE sobre Fundamentos de las Ciencias de la Computación (FOCS) , págs. 3-13, arXiv : math / 0406038 , doi : 10.1109 / SFCS.2000.892006.
- Reingold, O (2008), "Conectividad no dirigida en el espacio de registro", Journal of the ACM , 55 (4): Artículo 17, 24 páginas, doi : 10.1145 / 1391289.1391291.
- Reingold, O .; Trevisan, L .; Vadhan, S. (2006), "Pseudoaleatorio camina sobre dígrafos regulares y el problema RL vs. L", Proc. 38º Simposio ACM sobre Teoría de la Computación (STOC) , págs. 457–466, doi : 10.1145 / 1132516.1132583.