En teoría de grafos , un gráfico de celosía , de malla o de cuadrícula es un gráfico cuyo dibujo , incrustado en algún espacio euclidiano , forma un mosaico regular . Esto implica que el grupo de transformaciones biyectivas que envían el gráfico a sí mismo es una red en el sentido teórico de grupo .
Normalmente, no se hace una distinción clara entre dicho gráfico en el sentido más abstracto de la teoría de grafos y su dibujo en el espacio (a menudo el plano o el espacio 3D). Este tipo de gráfico puede denominarse más brevemente simplemente entramado , malla o cuadrícula . Además, estos términos también se usan comúnmente para una sección finita del gráfico infinito, como en "una cuadrícula cuadrada de 8 × 8".
El término gráfico reticular también se ha dado en la literatura a varios otros tipos de gráficos con alguna estructura regular, como el producto cartesiano de varios gráficos completos . [1]
Un tipo común de gráfico reticular (conocido con diferentes nombres, como gráfico de cuadrícula cuadrada ) es el gráfico cuyos vértices corresponden a los puntos en el plano con coordenadas enteras , estando las coordenadas x en el rango 1, ..., n , Las coordenadas y están en el rango 1, ..., m , y dos vértices están conectados por un borde siempre que los puntos correspondientes estén a una distancia 1. En otras palabras, es un gráfico de distancia unitaria para el conjunto de puntos descrito. [2]
Un gráfico de cuadrícula cuadrada es un producto cartesiano de gráficos , es decir, de dos gráficos de trayectoria con n - 1 y m - 1 aristas. [2] Dado que un gráfico de ruta es un gráfico de mediana , este último hecho implica que el gráfico de cuadrícula cuadrada también es un gráfico de mediana. Todos los gráficos de cuadrícula cuadrada son bipartitos , lo que se verifica fácilmente por el hecho de que se pueden colorear los vértices en forma de tablero de ajedrez.
Un gráfico de ruta también se puede considerar como un gráfico de cuadrícula en la cuadrícula n veces 1. Un gráfico de cuadrícula de 2 × 2 es un ciclo de 4 . [2]
Cada gráfico plano H es menor de la cuadrícula h × h , donde . [3]
Los gráficos de cuadrícula son objetos fundamentales en la teoría de grafos menores debido al teorema de exclusión de la cuadrícula . Desempeñan un papel importante en la teoría de la bidimensionalidad .
Un gráfico de cuadrícula triangular es un gráfico que corresponde a una cuadrícula triangular.
Un gráfico de cuadrícula de Hanan para un conjunto finito de puntos en el plano se produce a partir de la cuadrícula obtenida por las intersecciones de todas las líneas verticales y horizontales que pasan por cada punto del conjunto.
El gráfico de la torre (el gráfico que representa todos los movimientos legales de la pieza de ajedrez de la torre en un tablero de ajedrez ) también se denomina a veces gráfico de celosía , aunque este gráfico es estrictamente diferente al gráfico de celosía descrito en este artículo. Los movimientos válidos de la pieza de ajedrez de hadas wazir forman el gráfico de celosía cuadrada.
