Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición

Deseo calcular el número mínimo de particiones de un conjunto necesario dada una lista de pares de números que no pueden aparecer juntos en la misma partición.

Ejemplo 1:

S = [ 1 , 2 , 3 , 4 , 5 , 6 ] Parejas exclusivas = ( 1 , 2 ) , ( 3 , 4 ) , ( 5 , 6 ) , ( 1 , 6 ) , ( 4 , 6 )

Puedo crear dos particiones tales que pag 1 = ( 1 , 4 , 5 ) y pag 2 = ( 2 , 3 , 6 )

Ejemplo 2:

S = [ 1 , 2 , 3 , 4 , 5 , 6 ] Parejas exclusivas = ( 1 , 2 ) , ( 4 , 5 ) , ( 5 , 6 ) , ( 1 , 6 ) , ( 4 , 6 )

Eso requiere más de dos particiones. Parece ser porque se ha creado un "bucle": ( 4 , 5 ) → ( 5 , 6 ) → ( 6 , 4 ) y de vuelta al principio de nuevo.

Parece que el número mínimo de particiones podría ser # bucles + 1 , aunque no estoy seguro. En cualquier caso, no conozco una forma eficiente de detectar tales bucles.

¿Estoy en el camino correcto aquí, y puede aconsejarme alguna técnica/algoritmo que pueda ayudarme?

Esto es en realidad un problema del mundo real. A la esposa se le ha encomendado la tarea de dividir un grupo de año escolar en clases, pero hay alumnos que no quieren que estén juntos en las mismas clases. Me gustaría poder probar cuántas clases necesitarían dada su lista de excepciones (o, alternativamente, que físicamente no pueden tener N clases dada su lista de excepciones).

Respuestas (1)

Esto suena como el tipo de problema combinatorio que puede ser NP-difícil en el caso general, pero en realidad es fácil en el mundo real. Un ciclo con un número impar de miembros fuerza tres clases, pero un ciclo con un número par no. Si tuvieras ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 1 ) podrías hacer { 1 , 3 } , { 2 , 4 } La cantidad de bucles no importa, digamos que sus pares excluidos fueron ( 3 k + 1 , 3 k + 2 ) , ( 3 k + 2 , 3 k + 3 ) , ( 3 k + 3 , 3 k + 1 ) . Puedes tener muchos de estos y tener solo tres clases.

Puedes imaginar tu grupo como los vértices de un gráfico, los pares excluidos como bordes, y tienes un ejemplo del problema de coloreado de gráficos donde buscas el número cromático de tu gráfico. Parece probable que su gráfico se divida en muchos componentes desconectados, ya que probablemente tenga grupos de estudiantes que tienen restricciones entre ellos, pero no se preocupan por el resto de los estudiantes. Puedes trabajar en cada componente por separado, y el que requiera más clases será tu respuesta. También puede tener algunos estudiantes muy impopulares. Agrúpelos en la menor cantidad de clases posible, luego coloque el resto donde pueda. A menos que tengas muchosde exclusiones, será bastante fácil obtener una tarea óptima y demostrar que es óptima al mostrar algún subconjunto de los estudiantes que requiere tantas clases.

¡No solo fue una respuesta realmente útil, sino que me introdujo a un área de matemáticas realmente interesante! Me tomó un par de intentos averiguar cómo lo graficaría, pero llegué allí.
Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición
RespuestasAquíPolítica de privacidad1y, 0v