4 votos

El problema del dinitz.

Me gustaría preguntar si alguien sabe de buenos libros o artículos en internet sobre El Dinitz problema o tal vez alguien pueda explicar el problema un poco.

Considere la posibilidad de $n^2$ células dispuestas en un $( n \times n)$-cuadrado, y deje $(i,j)$ el valor de la celda en la fila $i$ y columnas $j$. Supongamos que para cada celda $(i,j)$ nos da un conjunto $C(i,j)$ $n$ colores.
Es, entonces, siempre es posible el color de toda la matriz escogiendo para cada celda $(i,j)$ una puerta de entrada de su conjunto $C(i,j)$ tal de que los colores de cada fila y de cada columna son distintos?

2voto

Alex Bolotov Puntos 249

Puede consultar el capítulo sobre el problema de Dinitz en Pruebas del Libro.

2voto

Erick Wong Puntos 12209

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X