Cuadrado de un gráfico

Question

Alguien me podría decir ¿qué es el "cuadrado de un gráfico" $G^2$? Gracias.

Answer 1

La Plaza de un gráfico $G$ se obtiene a partir de $G$, y agregando los bordes entre cualquier dos vértices cuya distancia en $G$ es $2$.

Answer 2

Yo habría pensado que $G^2$ podría significar el cuadro de producto de $G$ con sí mismo, o el producto cruzado de $G$ con sí mismo.

Las definiciones de estos son como sigue: Si $G$ $H$ son gráficos con vértice conjuntos de $V_G$$V_H$, entonces el producto de a $G$ $H$ tiene el vértice set $V_G \times V_H$ y tiene un borde de $(g_1, h_1)$ $(g_2, h_2)$si y sólo si o bien (1) $g_1=g_2$ y hay un borde de $h_1$ $h_2$ $H$o (2) $h_1=h_2$ y hay un borde de$g_1$$g_2$$G$.

El producto cruzado de $G$ $H$ tiene el vértice set $V_G \times V_H$ y tiene un borde de $(g_1, h_1)$ $(g_2, h_2)$si y sólo si hay un borde de $g_1$ $g_2$ $G$y un borde de$h_1$$h_2$$H$.

Desde TonyK ha encontrado otra definición, yo diría que hay más de una cosa a $G^2$ puede denotar.

Answer 3

Una orientada al gráfico de $G$ es un grafo dirigido sin bordes paralelos. El cuadrado de una orientada gráfico es un gráfico de $G'$ cuyo conjunto de vértices $V(G')$ es el mismo que el conjunto de vértices $V(G)$$G$. Un par ordenado de vértices $(u,w)$ es en el arco $A(G')$ $G'$ si y sólo si existe un vértice $v$ $G$ (y, en consecuencia, en $G'$) tal que $(u,v)$ $(v,w)$ son arcos en $G$.

Una definición similar para gráficas simples pueden ser desechadas de la anterior, mediante la sustitución de los arcos con los bordes y los pares ordenados de vértices con 2 elementos de los subconjuntos de a $V(G)$.