En teoría de grafos , un grafo reticular , un grafo de malla o un grafo de cuadrícula es un grafo cuyo dibujo , incrustado en algún espacio euclidiano , forma un mosaico regular . Esto implica que el grupo de transformaciones biyectivas que envían el grafo hacia sí mismo es un retículo en el sentido de la teoría de grupos .
Por lo general, no se hace una distinción clara entre un gráfico de este tipo 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 de forma más breve simplemente retícula , malla o cuadrícula . Además, estos términos también se utilizan comúnmente para una sección finita del gráfico infinito, como en "una cuadrícula 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 o 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 en el rango 1, ..., m , y dos vértices conectados por una arista siempre que los puntos correspondientes estén a una distancia de 1. En otras palabras, es el gráfico de distancia unitaria para los puntos enteros en un rectángulo con lados paralelos a los ejes. [2]
Un grafo de cuadrícula cuadrada es un producto cartesiano de grafos , es decir, de dos grafos de trayectoria con n − 1 y m − 1 aristas. [2] Dado que un grafo de trayectoria es un grafo de mediana , este último hecho implica que el grafo de cuadrícula cuadrada también es un grafo de mediana. Todos los grafos de cuadrícula cuadrada son bipartitos , lo que se verifica fácilmente por el hecho de que uno puede colorear los vértices en forma de tablero de ajedrez.
Un gráfico de ruta es un gráfico de cuadrícula sobre la cuadrícula. Un gráfico de cuadrícula es un gráfico de 4 ciclos . [2]
Cada grafo planar H es un menor de la cuadrícula h × h , donde . [3]
Los grafos de cuadrícula son objetos fundamentales en la teoría de grafos menores debido al teorema de exclusión de 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 mediante la cuadrícula obtenida por las intersecciones de todas las líneas verticales y horizontales a través de 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 torre en un tablero de ajedrez ) también se denomina a veces gráfico reticular , aunque este gráfico es diferente del gráfico reticular descrito aquí porque todos los puntos de una fila o columna son adyacentes. Los movimientos válidos de la pieza de ajedrez de hadas , el wazir, forman un gráfico reticular cuadrado.
