En teoría de grafos , el gráfico de una torre es un gráfico que representa todos los movimientos legales de la pieza de ajedrez de la torre en un tablero de ajedrez . Cada vértice del gráfico de una torre representa un cuadrado en un tablero de ajedrez, y cada borde representa un movimiento legal de un cuadrado a otro. Las mismas gráficas se pueden definir matemáticamente como los productos cartesianos de dos gráficas completas o como las gráficas lineales de gráficas bipartitas completas .
Gráfico de Rook | |
---|---|
Vértices | Nuevo Méjico |
Bordes | nm ( n + m ) / 2 - nm |
Diámetro | 2 |
Circunferencia | 3 (si max ( n , m ) ≥ 3 ) |
Número cromático | máx. ( n , m ) |
Propiedades | regular , vértice-transitivo , perfecto bien cubierto |
Tabla de gráficos y parámetros |
Las gráficas de Rook son muy simétricas. Para tableros cuadrados son gráficos de distancia transitiva y gráficos distancia regular , mientras que para los tableros rectangulares con dimensiones relativamente primos son gráficos circulantes . Pueden caracterizarse en términos del número de triángulos a los que pertenece cada borde y por la existencia de un ciclo de 4 que conecta cada par de vértices no adyacentes.
Los gráficos de Rook son gráficos perfectos , lo que significa que sus subgráficos inducidos (los gráficos de líneas de los gráficos bipartitos) tienen todos un número cromático igual a su número de camarilla . Las subgrafias inducidas de las gráficas de rook forman uno de los componentes clave de una descomposición de gráficas perfectas que se utiliza para demostrar el teorema de la gráfica perfecta fuerte que caracteriza a todas las gráficas perfectas. El número de independencia y el número de dominación del gráfico de una torre son iguales a la menor de sus dos dimensiones, y estos son gráficos bien cubiertos, lo que significa que cada conjunto independiente puede extenderse a un conjunto máximo independiente .
Definición
Un n × m gráfico de Rook representa los movimientos de una torre en una n × m tablero de ajedrez. [1] coordenadas pueden ser administrados sus vértices ( x , Y ) , donde 1 ≤ x ≤ n y 1 ≤ y ≤ m . Dos vértices ( x 1 , y 1 ) y ( x 2 , y 2 ) son adyacentes si y solo si x 1 = x 2 o y 1 = y 2 ; es decir, si pertenecen al mismo rango o al mismo archivo del tablero de ajedrez. [1]
Para una gráfica de torre de n × m , el número total de vértices es simplemente nm y el número de aristas es nm (n + m) / 2 - nm . Para una gráfica de n × n torres, el número total de vértices es simplemente n 2 y el número total de aristas es n 3 - n 2 ; en este caso, la gráfica también se conoce como gráfica de Hamming bidimensional [2] o gráfica cuadrada latina . [3]
La gráfica de la torre para un tablero de ajedrez de n × m también se puede definir como el producto cartesiano de dos gráficas completas K n y K m , expresadas en una sola fórmula como K n ◻ K m . El gráfico de complemento de un gráfico de torre de 2 × n es un gráfico de corona .
Fuerte regularidad
Moon (1963) y Hoffman (1964) observan que el El gráfico de rook tiene todas las siguientes propiedades:
- Tiene vértices, cada uno de los cuales es adyacente a bordes.
- Cuándo , exactamente los bordes pertenecen a triángulos y el resto los bordes pertenecen a triangulos. Cuándo, cada borde pertenece a triangulos.
- Cada dos vértices que no son adyacentes pertenecen a un único -vertex ciclo .
Como muestran, excepto en el caso , estas propiedades caracterizan de forma única el gráfico de la torre. Es decir, las gráficas de la torre son las únicas gráficas que obedecen a todas estas propiedades. [4] [5]
Cuándo , estas condiciones pueden abreviarse indicando que un El gráfico de rook es un gráfico muy regular con parámetros. [1] Por el contrario, todo gráfico muy regular con estos parámetros debe ser un gráfico de torre, a menos que . [4] [5]
Cuándo , hay otro gráfico fuertemente regular, el gráfico de Shrikhande , con los mismos parámetros que elgráfico de torre. [6] El gráfico de Shrikhande obedece a las mismas propiedades enumeradas por Moon y Moser. Se puede distinguir delgrafo de torre en que la vecindad de cada vértice en el gráfico de Shrikhande está conectado para formar un-ciclo. Por el contrario, en elEn el gráfico de la torre, la vecindad de cada vértice forma dos triángulos, desconectados entre sí. [7] Alternativamente, se pueden distinguir por los números de portada de su camarilla :El gráfico de rook puede estar cubierto por cuatro grupos (las cuatro filas o las cuatro columnas del gráfico), mientras que se necesitan seis grupos para cubrir el gráfico de Shrikhande. [6]
Simetría
Los gráficos de Rook son transitivos a vértices y- regulares ; son los únicos gráficos regulares formados a partir de los movimientos de piezas de ajedrez estándar de esta manera. [8] Cuando, las simetrías del gráfico de la torre se forman permutando independientemente las filas y columnas del gráfico, por lo que el grupo de automorfismo del gráfico tieneelementos. Cuándo, el gráfico tiene simetrías adicionales que intercambian filas y columnas, por lo que el número de automorfismos es . [9]
Dos vértices cualesquiera en el gráfico de una torre están a una distancia uno o dos entre sí, según sean adyacentes o no adyacentes, respectivamente. Dos vértices no adyacentes cualesquiera se pueden transformar en otros dos vértices no adyacentes mediante una simetría del gráfico. Cuando el gráfico de la torre no es cuadrado, los pares de vértices adyacentes caen en dos órbitas del grupo de simetría según sean adyacentes horizontal o verticalmente, pero cuando el gráfico es cuadrado, dos vértices adyacentes cualesquiera también pueden mapearse entre sí mediante un simetría y, por lo tanto, el gráfico es transitivo a la distancia . [10]
Cuándo y son relativamente primos , el grupo de simetríadel gráfico de la torre contiene como subgrupo el grupo cíclico que actúa permutando cíclicamente lavértices por lo tanto, en este caso, la gráfica de la torre es una gráfica circulante . [11]
Los gráficos de Square Rook son homogéneos conectados , lo que significa que cada isomorfismo entre dos subgrafos inducidos conectados puede extenderse a un automorfismo de todo el gráfico. [12]
Perfección
La gráfica de una torre también se puede ver como la gráfica lineal de una gráfica bipartita completa K n , m , es decir, tiene un vértice para cada borde de K n , my dos vértices de la gráfica de la torre son adyacentes si y solo si los bordes correspondientes del gráfico bipartito completo comparten un punto final común. [13] En esta vista, una arista en el gráfico bipartito completo desde el i- ésimo vértice en un lado de la bipartición hasta el j- ésimo vértice en el otro lado corresponde a un cuadrado de tablero de ajedrez con coordenadas ( i , j ) . [1]
Cualquier grafo bipartito es un subgrafo de un grafo bipartito completo y, en consecuencia, cualquier grafo lineal de un grafo bipartito es un subgrafo inducido de un grafo de torre. [14] Los gráficos lineales de los gráficos bipartitos son perfectos : en ellos, y en cualquiera de sus subgrafos inducidos, el número de colores necesarios en cualquier coloración de vértice es el mismo que el número de vértices en el subgrafo completo más grande . Los gráficos lineales de gráficos bipartitos forman una familia importante de gráficos perfectos: son una de las pocas familias utilizadas por Chudnovsky et al. (2006) para caracterizar las gráficas perfectas y mostrar que todas las gráficas sin agujeros impares ni anti-agujeros impares son perfectas. [15] En particular, los gráficos de rook son perfectos en sí mismos.
Debido a que la gráfica de una torre es perfecta, la cantidad de colores necesarios en cualquier coloración de la gráfica es solo el tamaño de su camarilla más grande. Las camarillas del gráfico de una torre son los subconjuntos de sus filas y columnas, y el más grande de ellos tiene un tamaño máximo ( m , n ) , por lo que este es también el número cromático del gráfico. Un n -Coloreado de un n × n gráfico de Rook puede ser interpretado como un cuadrado latino : describe una manera de llenar las filas y columnas de una n × n cuadrícula con n valores diferentes de tal manera que no aparece el mismo valor dos veces en cualquier fila o columna. [16] Aunque encontrar una coloración óptima de la gráfica de una torre es sencillo, es NP-completo determinar si una coloración parcial puede extenderse a una coloración de toda la gráfica (este problema se llama extensión de precoloración ). De manera equivalente, es NP-completo determinar si un cuadrado latino parcial se puede completar en un cuadrado latino completo. [17]
Independencia
a | B | C | D | mi | F | gramo | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
Un conjunto independiente en el gráfico de una torre es un conjunto de vértices, de los cuales no hay dos que pertenezcan a la misma fila o columna del gráfico; en términos de ajedrez, corresponde a una colocación de torres de las cuales no hay dos que se ataquen entre sí. Los gráficos perfectos también pueden describirse como los gráficos en los que, en cada subgrafo inducido, el tamaño del conjunto independiente más grande es igual al número de camarillas en una partición de los vértices del gráfico en un número mínimo de camarillas. En el gráfico de una torre, los conjuntos de filas o los conjuntos de columnas (el que tenga menos conjuntos) forman una partición tan óptima. Por tanto, el tamaño del conjunto independiente más grande del gráfico es min ( m , n ) . [1] Cada clase de color en cada color óptimo de la gráfica de una torre es un conjunto máximo independiente.
Las gráficas de Rook son gráficas bien cubiertas : cada conjunto independiente en la gráfica de una torre puede extenderse a un conjunto independiente máximo, y cada conjunto independiente máximo en la gráfica de una torre tiene el mismo tamaño, min ( m , n ) . [18]
Dominación
El número de dominación de un gráfico es la cardinalidad mínima entre todos los conjuntos dominantes. En el gráfico de la torre, un conjunto de vértices es un conjunto dominante si y solo si sus casillas correspondientes ocupan, o están alejadas de una torre, todas las casillas del tablero m × n . Para el tablero m × n , el número de dominación es min ( m , n ) . [19]
En el gráfico de la torre, un conjunto que predomina en k es un conjunto de vértices cuyas casillas correspondientes atacan a todas las demás casillas (mediante el movimiento de una torre) al menos k veces. Un conjunto dominante de k -tupla en el gráfico de la torre es un conjunto de vértices cuyos cuadrados correspondientes atacan a todos los demás cuadrados al menos k veces y ellos mismos son atacados al menos k - 1 veces. La cardinalidad mínima entre todos los k -dominating y k conjuntos tupla que dominan son los k número -domination y el k número tupla dominación, respectivamente. En el tablero cuadrado, y para k par , el número de dominación k es nk / 2 cuando n ≥ ( k 2 - 2 k ) / 4 y k <2 n . De manera similar, el número de dominación k -tupla es n ( k + 1) / 2 cuando k es impar y menor que 2 n . [20]
Ver también
- 3-3 duoprisma , un politopo de 4 dimensiones que tiene el el gráfico de la torre como el gráfico de sus vértices y aristas
- Gráfico de King y gráfico de Caballero , otros dos gráficos definidos a partir de los movimientos de piezas de ajedrez
- Gráfico de celosía , el gráfico de adyacencias horizontales y verticales de cuadrados en un tablero de ajedrez
- Gráfico de sudoku , un supergráfico del gráfico de una torre que conecta cuadrados de un rompecabezas de Sudoku que debe tener valores desiguales
Referencias
- ^ a b c d e Laskar, Renu; Wallis, Charles (1999), "Gráficos de tablero de ajedrez, diseños relacionados y parámetros de dominación", Journal of Statistical Planning and Inference , 76 (1-2): 285-294, doi : 10.1016 / S0378-3758 (98) 00132-3 , MR 1673351.
- ^ Azizoğlu, M. Cemil; Eğecioğlu, Ömer (2003), "Conjuntos extremos que minimizan el límite de dimensión normalizada en gráficos de Hamming", SIAM Journal on Discrete Mathematics , 17 (2): 219-236, doi : 10.1137 / S0895480100375053 , MR 2032290.
- ^ Goethals, J.-M .; Seidel, JJ (1970), "Gráficos muy regulares derivados de diseños combinatorios", Canadian Journal of Mathematics , 22 (3): 597–614, doi : 10.4153 / CJM-1970-067-9 , MR 0282872.
- ^ a b Moon, JW (1963), "On the line-graph of the complete bigraph", Annals of Mathematical Statistics , 34 (2): 664–667, doi : 10.1214 / aoms / 1177704179.
- ^ a b Hoffman, AJ (1964), "On the line graph of the complete bipartite graph", Annals of Mathematical Statistics , 35 (2): 883–885, doi : 10.1214 / aoms / 1177703593 , MR 0161328.
- ^ a b Fiala, Nick C .; Haemers, Willem H. (2006), "Gráficos 5-cromáticos fuertemente regulares", Discrete Mathematics , 306 (23): 3083–3096, doi : 10.1016 / j.disc.2004.03.023 , MR 2273138.
- ^ Burichenko, vicepresidente; Makhnev, AA (2011), "Об автоморфизмах сильно регулярных локально циклических графов" [En automorfismos de gráficos localmente fuertemente cíclicos regulares], Doklady Akademii Nauk (en ruso), 441 (2): 151-155, MR 2953786. Traducido en Doklady Mathematics 84 (3): 778–782, 2011, doi : 10.1134 / S1064562411070076 . De la primera página de la traducción: "El gráfico de Shrikhande es el único gráfico localmente hexagonal fuertemente regular con parámetros (16, 6, 2, 2)".
- ^ Elkies, Noam , glosario de teoría de grafos.
- ^ Harary, Frank (1958), "Sobre el número de gráficos bicolores" , Pacific Journal of Mathematics , 8 (4): 743–755, doi : 10.2140 / pjm.1958.8.743 , MR 0103834. Ver en particular la ecuación (10), p. 748 para el grupo de automorfismo del grafica de rook, y la discusión sobre la ecuación para el orden de este grupo.
- ^ Biggs, Norman (1974), "La simetría de los gráficos lineales", Utilitas Mathematica , 5 : 113-121, MR 0347684.
- ^ Esto se sigue de la definición de la gráfica de la torre como una gráfica de producto cartesiano, junto con la Proposición 4 de Broere, Izak; Hattingh, Johannes H. (1990), "Productos de gráficos circulantes", Quaestiones Mathematicae , 13 (2): 191-216, doi : 10.1080 / 16073606.1990.9631612 , MR 1068710.
- ^ Gray, R .; Macpherson, D. (2010), "Gráficos homogéneos conectados contables", Journal of Combinatorial Theory , Serie B, 100 (2): 97-118, doi : 10.1016 / j.jctb.2009.04.002 , MR 2595694. Ver en particular el Teorema 1, que identifica estas gráficas como gráficas lineales de gráficas bipartitas completas.
- ^ Para conocer la equivalencia entre los productos cartesianos de gráficos completos y los gráficos lineales de gráficos bipartitos completos, consulte de Werra, D .; Hertz, A. (1999), "Sobre la perfección de las sumas de gráficos" (PDF) , Matemáticas discretas , 195 (1-3): 93-101, doi : 10.1016 / S0012-365X (98) 00168-X , MR 1663807.
- ↑ de Werra y Hertz (1999) .
- ^ Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "El teorema del gráfico fuerte perfecto" (PDF) , Annals of Mathematics , 164 (1): 51-229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , JSTOR 20159988.
- ^ Para conocer la equivalencia entre los gráficos bipartitos completos para colorear los bordes y los cuadrados latinos, consulte, por ejemplo, LeSaulnier, Timothy D .; Stocker, Christopher; Wenger, Paul S .; West, Douglas B. (2010), "Coincidencia de arco iris en gráficos de color de borde" , Electronic Journal of Combinatorics , 17 (1): Nota 26, 5, doi : 10.37236 / 475 , MR 2651735.
- ^ Colbourn, Charles J. (1984), "La complejidad de completar cuadrados latinos parciales", Matemáticas aplicadas discretas , 8 (1): 25-30, doi : 10.1016 / 0166-218X (84) 90075-1 , MR 0739595.
- ^ Para una declaración equivalente a la propiedad bien cubierta de los gráficos de torre, en términos de emparejamientos en gráficos bipartitos completos, vea Sumner, David P. (1979), "Gráficos emparejados aleatoriamente", Journal of Graph Theory , 3 (2): 183–186, doi : 10.1002 / jgt.3190030209 , hdl : 10338.dmlcz / 102236 , MR 0530304.
- ^ Yaglom, AM ; Yaglom, IM (1987), "Solución al problema 34b", Desafiando problemas matemáticos con soluciones elementales , Dover, p. 77, ISBN 9780486318578.
- ^ Burchett, Paul; Lane, David; Lachniet, Jason (2009), " K -domination y k -tuple domination en el gráfico de la torre y otros resultados", Congressus Numerantium , 199 : 187-204.
enlaces externos
- Weisstein, Eric W. "Gráfico de celosía" . MathWorld .