Алгоритъм за разделяне на набор от символи с ограничения в минимален брой подгрупи - алгоритъм, комбинации

Имам набор S={a,c,d,e,f,j,m,q,s,t} с ограничения C={am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}, xy в C означава, че x и y не могат да бъдат в една и съща подгрупа. Бих искал алгоритъм да разделя комплекта S на подгрупи Sj, така че:

1.Броят на Sj е сведен до минимум

2. Разликата между размера на всяка подгрупа е колкото е възможно по-голяма

Например в този случай, и двете {{q,a,c,d,j,t},{m,s},{f},{e}} и {{a,c,e,j},{m,s,q,t},{d},{f}} отговарят на 1, но първата е оптимална.

Идвайки от компютърна наука, се чудя дали математиците са измислили алгоритъм за този проблем.

Отговори:

Както разбирам, задачата ви може да бъде пренаписана като: намерите най-голямата независима подгрупа от върховете S "на графика G = (S, C), повторете стъпката за графика G" = GS ".

Той е добре известен (също посочен от @tobias_k в неговия коментар), че най-големият независим набор от графиката е NP-твърд проблем (тъй като това е еквивалентно на известния проблем на клика).

Мисля, че това е много труден проблем, и това е таказащо. За да намерите минимален брой подмножества, трябва да решите проблема за минималния хроматичен брой графики. Този проблем обикновено се решава от груба сила.