Tengo un set S={a,c,d,e,f,j,m,q,s,t} con una restricción C={am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}. xy en C significa que x e y no pueden estar en el mismo subconjunto. Me gustaría un algoritmo para dividir el conjunto S en subconjuntos Sj de manera que:
1.El número de Sj se minimiza
2. La diferencia entre el tamaño de cada subconjunto es lo más grande posible
Por ejemplo, en este caso, tanto {{q,a,c,d,j,t},{m,s},{f},{e}} y {{a,c,e,j},{m,s,q,t},{d},{f}} Son satisfactorios 1, pero el primero es óptimo.
Con antecedentes en informática, me pregunto si los matemáticos han ideado un algoritmo para este problema.
Respuestas
1 para la respuesta № 1Según tengo entendido, su tarea se puede reescribir como: encuentre el mayor subconjunto independiente de vértices S "del gráfico G = (S, C); repita el paso para el gráfico G" = GS ".
Es bien sabido (también señalado por @tobias_k en su comentario) que El conjunto independiente más grande de la gráfica. Es un problema difícil de NP (ya que es equivalente al famoso problema de camarilla).
0 para la respuesta № 2
Creo que este es un problema muy difícil, y eso espor qué. Para encontrar el número mínimo de subconjuntos, debe resolver el problema sobre el número cromático mínimo de la gráfica. Este problema se resuelve generalmente por la fuerza bruta.