Algorithme pour diviser un ensemble de symboles avec des contraintes en nombre minimum de sous-ensembles - algorithme, combinaisons

J'ai un set S={a,c,d,e,f,j,m,q,s,t} avec une contrainte C={am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}. xy en C signifie que x et y ne peuvent pas être dans le même sous-ensemble. Je voudrais un algorithme pour diviser l'ensemble S en sous-ensembles Sj tels que:

1.Le nombre de Sj est minimisé

2. La différence entre la taille de chaque sous-ensemble est aussi grande que possible

Par exemple, dans ce cas, les deux {{q,a,c,d,j,t},{m,s},{f},{e}} et {{a,c,e,j},{m,s,q,t},{d},{f}} sont satisfaisants 1, mais le premier est optimal.

Venant d’une formation en informatique, je me demande si les mathématiciens ont mis au point un algorithme pour résoudre ce problème.

Réponses:

Si je comprends bien, votre tâche peut être réécrite comme suit: recherchez le plus grand sous-ensemble indépendant de sommets S "du graphe G = (S, C); répétez l’étape pour le graphe G" = GS ".

Il est bien connu (également souligné par @tobias_k dans son commentaire) que plus grand ensemble indépendant du graphique est un problème NP-difficile (car il est équivalent au fameux problème de la clique).

Je pense que c'est un problème très difficile, et c'estPourquoi. Pour trouver le nombre minimum de sous-ensembles, vous devez résoudre le problème du nombre minimum de graphes chromatiques. Ce problème est généralement résolu par la force brute.