He podido encontrar un par de simples gráficos cuyo producto cartesiano es plano, excepto cuando al menos uno de la pareja un gráfico de la ruta. ¿Existen ejemplos? ¿Si no es un ejemplo imposible?
Respuesta
¿Demasiados anuncios?
El gráfico que buscas no existe: el producto Cartesiano de dos gráficos que son a la vez no la ruta de los gráficos no es planar. Para ver esto, observe que la conexión de un no-ruta gráfica es un ciclo o tiene un vértice con grado de al menos 3, por lo que el producto Cartesiano de dos no-ruta de los gráficos debe tener al menos uno de los siguientes productos Cartesianos como subdiagramas:
- Ciclo □ ciclo. Estos son toroidal de la cuadrícula de gráficos, que son todos los no-planar porque contienen $K_5$ como un menor de edad, como se muestra en la siguiente imagen:
![]()
- Ciclo □ garra. Estos son también todos los que no son planas. Que contiene como subgrafo el producto de una garra con tres vértices camino, que en sí mismo contiene un $K_{3,3}$ menor.
![]()
- Garra □ garra. Este es un fijo de 16 vértice de la gráfica, pero contiene el mismo producto de garra y $P_3$ se mostró anteriormente no planas. Por lo tanto, este gráfico no es planar así.
Ya que el producto Cartesiano de dos no-ruta de los gráficos debe contener al menos uno de los anteriores no grafos planares, todos estos productos deben ser no planas.
