Producto fuerte de grafos
El producto fuerte de los gráficos G y H es un gráfico tal que [1] :
- el conjunto de vértices es un producto directo
- vértices distintos ( u,u' ) y ( v,v' ) están conectados por una arista si y sólo si
- u = v y u' es adyacente a v' , o
- u' = v' y u es adyacente a v , o
- u es adyacente a v y u' es adyacente a v' .
El producto fuerte es la unión del producto directo y el producto tensorial .
El producto fuerte también se llama producto normal o producto AND . El producto fue introducido por primera vez por Sabidussi en 1960 [2] . El producto fuerte contrasta con el producto débil , pero los dos productos difieren solo cuando se aplican a gráficos infinitos.
Por ejemplo, el gráfico de jugadas del rey , un gráfico en el que los vértices son las celdas del tablero de ajedrez y las aristas representan las posibles jugadas del rey, es un producto fuerte de dos caminos [3] .
Se debe tener cuidado cuando el término aparece en la literatura, ya que el producto fuerte también se usa para referirse al producto tensorial [4] .
Véase también
Notas
- ↑ Imrich, Klavžar, Rall, 2008 .
- ↑ Sabidussi, 1960 , pág. 446–457.
- ↑ Berend, Korach, Zucker, 2005 , pág. 335–341.
- ↑ Lovász, 1979 , pág. 2.
Literatura
- Wilfried Imrich, Sandi Klavzar, Douglas F. Rall. Grafos y su Producto Cartesiano. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
- Sabidussi, G. Multiplicación de gráficos // Matemáticas. Z.. - 1960. - T. 72 . — S. 446–457 . -doi : 10.1007/ BF01162967.
- Daniel Berend, Ephraim Korach, Shira Zucker. Dos anticoloración de gráficos planos y relacionados // 2005 Conferencia internacional sobre análisis de algoritmos. - Nancy: Asociación de Matemáticas Discretas y Ciencias de la Computación Teórica, 2005. - P. 335–341. — (Procedimientos de Matemáticas Discretas y Ciencias de la Computación Teórica).
- Laszlo Lovasz. Sobre la capacidad de Shannon de un gráfico // Transacciones IEEE sobre teoría de la información. - 1979. - T. IT-25 , núm. 1 . -doi : 10.1109/ TIT.1979.1055985 .