Professoressa di italiano

Alla professoressa di italiano più brava del mondo è stata affidata una nuova classe di prima media con $n$ alunni. Per favorire la socializzazione e abituare gli alunni al lavoro in gruppo la professoressa vuole avviare una ricerca formando varie squadre. Alcuni alunni si conoscevano prima di arrivare nella nuova classe. Sia $A$ l'insieme di coppie di alunni che si conoscono ( $A=\{(i,j): i \mbox{ e } j \mbox{ si cononoscono}\}$). La regola che segue la professoressa è quella di partizionare l'insieme degli alunni gruppi in modo che in uno stesso gruppo non via siano amici. L'obiettivo è quello di minimizzare il numero di gruppi.

Leggi i suggerimenti <>

Variante

La professoressa vuole anche che la composizione dei gruppi sia bilanciata tra maschi e femmine, quindi vuole minimizzare la massima differenza tra maschi e femmine L'insieme degli alunni $N$ è partizionato in due sottoinsiemi $M$ (maschi) e $F$ (femmine). Come modificare la formulazione?

Leggi i suggerimenti <>