Producto directo de grafos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2021; las comprobaciones requieren 2 ediciones .

Un producto cartesiano o directo [1] G H de las gráficas G y H es una gráfica tal que

El producto cartesiano puede reconocerse eficientemente en tiempo lineal [2] . La operación es conmutativa como operación en clases de isomorfismo de grafos , y más estrictamente, los grafos G H y H G son naturalmente isomorfos , pero la operación no es conmutativa como operación en grafos etiquetados. La operación también es asociativa , ya que las gráficas ( F G ) H y F ( G H ) son naturalmente isomorfas.

La notación G × H también se usa ocasionalmente para el producto cartesiano de gráficos, pero más a menudo se usa para otra construcción conocida como el producto tensorial de gráficos . El símbolo cuadrado se usa más comúnmente y no es ambiguo para el producto cartesiano de gráficos. Muestra visualmente las cuatro aristas resultantes del producto cartesiano de dos aristas [3]

Ejemplos

Por lo tanto, el producto cartesiano de dos gráficos de hipercubo es otro hipercubo: Q i Q j =Q i+j .

Propiedades

Si un gráfico conexo es un producto cartesiano, se puede descomponer únicamente en un producto de factores primos, gráficos que no se pueden descomponer en un producto de gráficos [4] [5] . Sin embargo, Imrich y Klavzhar [6] describieron un gráfico desconectado, que se puede representar de dos maneras diferentes como un producto cartesiano de gráficos simples:

(K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 ) = (K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),

donde el signo más significa una unión disjunta y el superíndice significa un producto cartesiano múltiple.

Un producto cartesiano es un gráfico de vértice transitivo si y solo si cada uno de sus factores es de vértice transitivo [7] .

Un producto cartesiano es bipartito si y solo si cada uno de sus factores es bipartito. Más generalmente, el número cromático de un producto cartesiano satisface la ecuación

χ(G H)=max {χ(G), χ(H)} [8] .

La conjetura de Hedetniemi establece una igualdad relacionada para el producto tensorial de grafos . El número de independencia de los productos cartesianos no es fácil de calcular, pero como mostró Vizing [5] , el número de independencia satisface las desigualdades

α( G )α( H ) + min{|V( G )|-α( G ),|V( H )|-α( H )} ≤ α( G H ) ≤ min{α( G ) |V ( H )|, α( H ) |V( G )|}.

La conjetura de Vizing establece que el número de dominancia de un producto cartesiano satisface la desigualdad

γ( G H ) ≥ γ( G )γ( H ).

Teoría de grafos algebraicos

La teoría algebraica de gráficos se puede utilizar para analizar el producto cartesiano de gráficos. Si un gráfico tiene vértices y una matriz de adyacencia , y un gráfico tiene vértices y una matriz de adyacencia , entonces la matriz de adyacencia del producto cartesiano de dos gráficos está dada por

,

donde denota el producto de matrices de Kronecker y denota la matriz identidad [9] .

Historia

Según Imrich y Klavzhar [6] , los productos cartesianos de grafos fueron definidos en 1912 por Whitehead y Russell . El producto de los gráficos fue redescubierto repetidamente más tarde, en particular por Gert Sabidoussi [4] .

Notas

  1. ↑ Vizing usó el término "Producto cartesiano", en el artículo " Producto directo " se llama directo al mismo producto.
  2. ↑ ( Imrich y Peterin 2007 ). Para algoritmos de tiempo polinomial anteriores, consulte Feigenbaum, Hershberger , Schäffer 1985 y Aurenhammer, Hagauer, Imrich 1992 .
  3. ↑ Hahn, Sabidussi, 1997 .
  4. ↑ 1 2 Sabidussi, 1960 .
  5. ↑ 1 2 Vising, 1963 .
  6. ↑ 1 2 Imrich, Klavžar, 2000 .
  7. ↑ Imrich, Klavžar, 2000 , p. Teorema 4.19.
  8. ↑ Sabidussi, 1957 .
  9. ↑ Kaveh, Rahami, 2005 .

Literatura

Enlaces