Ho un set S={a,c,d,e,f,j,m,q,s,t} con un vincolo C={am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}. xy in C significa che xey non possono essere nello stesso sottoinsieme. Vorrei un algoritmo per dividere il set S in sottoinsiemi Sj in modo tale che:
1. Il numero di Sj è ridotto al minimo
2. La differenza tra le dimensioni di ciascun sottoinsieme è la più ampia possibile
Per esempio in questo caso, entrambi {{q,a,c,d,j,t},{m,s},{f},{e}} e {{a,c,e,j},{m,s,q,t},{d},{f}} sono soddisfacenti 1, ma il primo è ottimale.
Venendo da un background di informatica, mi chiedo se i matematici abbiano escogitato un algoritmo per questo problema.
risposte:
1 per risposta № 1Come ho capito, il tuo compito può essere riscritto come: trovare il più grande sottoinsieme indipendente di vertici S "del grafico G = (S, C), ripetere il passo per il grafico G" = GS ".
È ben noto (indicato anche da @tobias_k nel suo commento) più grande insieme indipendente del grafico è un problema NP-difficile (in quanto è equivalente al famoso clique-problem).
0 per risposta № 2
Penso che questo sia un problema molto difficile, e cioèperché. Per trovare il numero minimo di sottoinsiemi, è necessario risolvere il problema relativo al numero cromatico minimo del grafico. Questo problema è generalmente risolto dalla forza bruta.