05 Abril, 2020, 01:50 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Coloreo de grafos.  (Leído 91 veces)
0 Usuarios y 1 Visitante están viendo este tema.
murkillerx
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 26


Ver Perfil
« : 16 Marzo, 2020, 14:03 »

Necesito ayuda con un ejercicio sobre     Título corregido

El "queen graph"  [texx] Q_n [/texx] es el grafo cuyos vértices son los  [texx] n^2 [/texx] casilleros de un tablero cuadrado con  [texx] n [/texx] filas y  [texx] n [/texx] columnas. Dos vértices son vecinos si poniendo una reina de ajedrez en cada uno de los casilleros las reinas se atacan mutuamente. (es decir, si los casilleros están en una misma fila, columna o diagonal, donde diagonal no es necesariamente una de las diagonales principales).
Probar que si  [texx] n [/texx] es coprimo con 6, entonces  [texx] \varkappa(G) = n [/texx].

Lo que tengo hasta ahora es que dado que todos los casilleros de una misma fila, una misma columna o una misma diagonal son vecinos entre sí, el grafo completo [texx] K_n [/texx] está incluido en [texx] Q_n [/texx] por lo que [texx] \varkappa(G) >= n [/texx]. Ahora bien, desconozco alguna cota superior lo suficientemente cercana a [texx] n [/texx].
En línea
geómetracat
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.011



Ver Perfil
« Respuesta #1 : 17 Marzo, 2020, 09:43 »

Echa un vistazo por aquí:

   http://users.encs.concordia.ca/~chvatal/queengraphs.html   
En línea

La ecuación más bonita de las matemáticas: [texx]d^2=0[/texx]
murkillerx
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 26


Ver Perfil
« Respuesta #2 : 18 Marzo, 2020, 02:56 »

Muchas gracias me sirvio bastante.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!