Hispanopedia Wiki
En teoría de grafos , un grafo reticular , grafo de malla o grafo de cuadrícula es un grafo cuyo dibujo , incrustado en algún espacio euclidiano , forma un teselado regular . Esto implica que el grupo de transformaciones biyectivas que envían el grafo a 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 grafo en el sentido más abstracto de la teoría de grafos y su representación en el espacio (a menudo el plano o el espacio tridimensional). Este tipo de grafo puede denominarse simplemente retículo , malla o cuadrícula . Además, estos términos también se utilizan comúnmente para referirse a una sección finita del grafo infinito, como en "una cuadrícula cuadrada de 8 × 8".
El término grafo reticular también se ha utilizado en la literatura para referirse a otros tipos de grafos con cierta estructura regular, como el producto cartesiano de varios grafos completos . [ 1 ]
Gráfico de cuadrícula cuadrada
Un tipo común de grafo reticular (conocido con diferentes nombres, como grafo de cuadrícula o grafo de cuadrícula cuadrada ) es aquel cuyos vértices corresponden a los puntos del plano con coordenadas enteras , donde las coordenadas x están en el rango 1, ..., n , las coordenadas y están en el rango 1, ..., m , y dos vértices están conectados por una arista cuando los puntos correspondientes se encuentran a una distancia de uno. En otras palabras, es el grafo de distancia unitaria para los puntos enteros en un rectángulo con lados paralelos a los ejes. [ 2 ]
Propiedades
Un grafo de cuadrícula cuadrada es un producto cartesiano de grafos , concretamente, de dos grafos de caminos con n − 1 y m − 1 aristas. [ 2 ] Dado que un grafo de caminos es un grafo mediano , este hecho implica que el grafo de cuadrícula cuadrada también lo es. Todos los grafos de cuadrícula cuadrada son bipartitos , lo cual se verifica fácilmente al poder colorear los vértices como en un tablero de ajedrez.
Un grafo de ruta es un grafo de cuadrícula en elcuadrícula. AEl gráfico de cuadrícula es un ciclo de 4. [ 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 menores de grafos debido al teorema de exclusión de cuadrícula . Juegan un papel importante en la teoría de la bidimensionalidad .
Otros tipos
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 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 torre en un tablero ) 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 hada, el visir, forman un gráfico reticular cuadrado.
Véase también
Referencias
- ↑ Weisstein, Eric W. "Grafo reticular" . MathWorld .
- ^ Weisstein , Eric W. "Gráfico de cuadrícula " . MundoMatemático .
- ↑ Robertson, N.; Seymour, P.; Thomas, R. (noviembre de 1994). "Exclusión rápida de un grafo planar" . Journal of Combinatorial Theory, Serie B. 62 ( 2): 323– 348. doi : 10.1006/jctb.1994.1073 .
- Grafos planares
- Familias de grafos
