Los niños desagrado en la plaza de

Question

$n^2\geq 4$ de los niños se colocarán en un $n\times n$ plaza. Algunos de los pares de los niños odian entre sí y no quiero ser uno junto a otro. Gustar es mutuo, y junto a cada uno de los otros medios está directamente arriba/abajo/izquierda/derecha de cada uno de los otros. ¿Cuál es el máximo de $k$ tal que si cada niño disgustos no más de $k$ otros niños, luego de la colocación es siempre posible?

Si un niño no quiere a $n^2-2$ otros niños, una colocación obviamente no es posible porque no podemos encontrar a dos niños al lado de este niño, incluso si hemos de colocar al niño en un rincón. Hacer mejor que esto, podemos dividir a los niños en dos grupos de aproximadamente el mismo tamaño, y deje que cada niño aversión a todos los niños del otro grupo. A continuación, cada niño disgustos de $n^2/2$ otros niños, y claramente no podemos colocarlos en la plaza de la manera deseada.

Answer 1

(Sólo una entrada inicial. No se trata de una solución) Para empezar, al menos podemos demostrar que k=2 debe ser un límite inferior para n>2, incluso a pesar de que probablemente era bastante esperado.

Si a los niños les disgusta a la mayoría de los otros 2 niños, a continuación, los niños pueden ser agrupados en discontinuo "cadenas de aversión", "ciclos de aversión", o "los niños solos". Esencialmente los componentes conectados de la gráfica en los bordes denotar aversión son lone vértices, cadenas o ciclos.

En ese caso, el siguiente esquema puede ser adoptado (en el caso en que n es impar)

1. Lista de los componentes conectados
2. Enumerar los niños de cada componente en la forma natural y accedió a la siguiente componente.
3. Coloque al niño 1 en la esquina superior izquierda
4. Coloque el siguiente niño de dos pasos a la derecha de la anterior niño y la vuelta a la fila siguiente si es necesario. (Y repetir)

Si n es incluso reemplazar 4 con

4. Si n es colocar la siguiente niño de tres pasos a la derecha de la anterior niño y la vuelta a la fila siguiente si es necesario. (Y repetir)

Implementar el algoritmo para n=3 el caso de carreras como:

Lo que al menos podría ser un buen paso siguiente sería, tal vez, e investigar si k=3 parece no tener asientos soluciones para algunos n y así avanzar hacia la determinación de si o no la máxima k es general o depende de n.