En teoría de grafos , el producto fuerte G ⊠ H de los gráficos G y H es un gráfico tal que [1]
- el conjunto de vértices de G ⊠ H es el producto cartesiano V ( G ) × V ( H ); y
- vértices distintos ( u, u ' ) y ( v, v' ) son adyacentes en G ⊠ H si y solo 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' .
Es la unión del producto cartesiano y el producto tensorial .
El producto fuerte también se denomina producto normal o producto AND . [ cita requerida ] Fue introducido por primera vez por Sabidussi en 1960. [2] En ese escenario, el producto fuerte se contrasta con un producto débil , pero los dos son diferentes solo cuando se aplican a una infinidad de factores.
Por ejemplo, el gráfico del rey , un gráfico cuyos vértices son cuadrados de un tablero de ajedrez y cuyos bordes representan posibles movimientos de un rey del ajedrez, es un producto fuerte de dos gráficos de trayectoria . [3]
Se debe tener cuidado al encontrar el término producto fuerte en la literatura, ya que también se ha utilizado para denotar el producto tensorial de los gráficos . [4]
Ver también
Referencias
- ^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Gráficos y su producto cartesiano , AK Peters, ISBN 978-1-56881-429-2.
- ^ Sabidussi, G. (1960). "Multiplicación de gráficos". Matemáticas. Z . 72 : 446–457. doi : 10.1007 / BF01162967 . hdl : 10338.dmlcz / 102459 . Señor 0209177 .
- ^ Berend, Daniel; Coré, Efraín; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF) , 2005 International Conference on Analysis of Algorithms , Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, págs. 335–341, MR 2193130.
- ^ Consulte la página 2 de Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109 / TIT.1979.1055985.