Il problema del campionato - Parte 2

Una delle meraviglie (meravigliosa per me, s'intende) presenti nel mitico almanacco del calcio (vedi Parte 1 di questo multi-post) era che venivano riportati i risultati di tutte le partite di tutti i campionati italiani di serie A, dalle lontane ottocentesche origini fino alla stagione in corso; ma la vera meraviglia per i miei occhi era che queste informazioni erano pubblicate in un modo estremamente compatto: una paginetta per ogni campionato, cioè per ogni anno.
Com'è possibile? Venivano usati caratteri microscopici, da leggere con la lente d'ingrandimento? No, semplicemente avevano escogitato un semplice ma ingegnoso metodo per risparmiare molto spazio, che a me piacque molto.

Solitamente i risultati delle partite di un torneo vengono riportati in una forma come la seguente (tratta da Wikipedia):


Nell'almanacco, invece, per ogni stagione veniva presentata una matrice quadrata con un numero di righe (e di colonne) pari al numero di squadre partecipanti, e nelle caselle interne venivano riportati i risultati delle partite che avevano visto in campo le due squadre corrispondenti alla riga e alla colonna di riferimento.
Per convenzione, in ogni incontro la squadra di casa era quella corrispondente alla riga, e quella ospite era quella corrispondente alla colonna. In questo modo, la diagonale principale della matrice restava vuota per l'ovvio motivo che una squadra non può giocare contro se stessa.
Presa una qualsiasi casella (quindi una partita) in una o nell'altra delle sezioni triangolari divise dalla diagonale principale, la casella speculare rispetto alla diagonale stessa risulta corrispondere alla ripetizione della stessa partita nell'altro girone della stagione (se la prima partita appartiene al girone di andata, la seconda appartiene al girone di ritorno, e viceversa).
Se N è il numero di squadre del torneo (si ipotizza che N sia sempre pari), la matrice quadrata avrà lato N per costruzione; le partite complessivamente presenti sono quindi N² - N (occorre infatti togliere la diagonale principale vuota), quindi N(N-1).
In effetti le giornate del campionato sono N-1, perché ogni squadra deve giocare contro tutte le squadre tranne se stessa (d'altra parte, N-1 è il numero di caselle compilate in ogni riga e in ogni colonna); e in ogni giornata vengono disputate N/2 partite. Quindi le partite complessive in un girone di andata sono 1/2 N(N-1), numero che va raddoppiato per tener conto del girone di ritorno: viene così confermato il risultato N(N-1) ottenuto sopra.
(Nelle figure seguenti, per semplificare un po', ho posto N=4).


Il trucco della matrice per risparmiare spazio è piuttosto banale e ovvio, direte voi. Certo, ma all'undicenne che ero allora ingenuamente sembrò geniale.
Quando, anni dopo, mi cimentai nel problema della generazione del calendario, tema centrale di questi post, mi tornarono subito alla mente le magiche matrici dell'almanacco del calcio.
Immaginai che all'interno delle caselle, anziché i risultati degli incontri, fossero scritti i numeri delle giornate in cui tali incontri sono programmati (o già disputati).
Ad esempio, la partita tra la Squadra A e la Squadra B è programmata per la giornata n. 1, la partita tra la Squadra B e la Squadra C è programmata per la giornata n. 3, e così via.


Ora apportiamo una nuova leggera variazione alla matrice: trascuriamo la differenza tra andata e ritorno, e di conseguenza nelle due caselle corrispondenti all'andata e al ritorno di un certo incontro tra due squadre (due caselle speculari nel senso spiegato prima), mettiamo lo stesso numero, relativo, per convenzione, alla giornata del girone di andata in cui si disputa la prima delle due gare.
Otteniamo una matrice come quella seguente:


Osservando la matrice ottenuta, notiamo che essa gode di due interessanti proprietà:
1) è simmetrica rispetto alla diagonale principale;
2) tralasciando le caselle vuote sulla diagonale, su ogni riga e su ogni colonna sono presenti tutti i numeri da 1 a N-1, senza ripetizioni.
Per la verità, queste due condizioni sono necessarie e sufficienti affinché la matrice rappresenti un calendario valido per un campionato. Infatti, se su una stessa riga o colonna ci fossero due caselle con lo stesso numero, vorrebbe dire che una squadra dovrebbe giocare due partite nella stessa giornata (e, corrispondentemente, un'altra squadra non giocherebbe alcuna partita): situazione questa ovviamente non ammessa.

Vi viene in mente qualche famoso rompicapo in cui accade qualcosa di simile?
Risposta esatta: il sudoku!


Anche il sudoku si gioca su una matrice quadrata, precisamente con N=9.
Su ogni riga e colonna devono essere posti tutti i numeri da 1 a 9, senza ripetizioni: lo stesso termine "sudoku", in giapponese, significa proprio qualcosa come "i numeri devono comparire una sola volta".
Le uniche due differenze, rispetto alla matrice del campionato, sono le seguenti:
1. anche le caselle sulla diagonale vanno riempite regolarmente, come le altre;
2. esiste un ulteriore vincolo, relativo ai 9 sotto-quadrati 3x3 evidenziati all'interno dello schema complessivo: anche in ciascuno di essi, tutti i numeri da 1 a 9 devono essere presenti senza ripetizioni.

Sia per giocare a sudoku sia per stilare il calendario del campionato, quindi, si tratta di risolvere un problema vincolato in cui occorre assegnare dei numeri ad alcune caselle.
Prendiamo in esame la matrice del campionato, di lato N, e trasformiamo ogni casella in un nodo di un grafo, mettendo in ogni casella l'indicazione della partita corrispondente.
Poi colleghiamo tra loro, mediante archi, gli N nodi che appartengono alla stessa riga, e poi facciamo lo stesso con i nodi che appartengono alla stessa colonna.
Usiamo però l'accortezza di accorpare tra loro i nodi che contengono una partita tra le stesse due squadre: andata e ritorno per noi, ora, sono la stessa cosa.
Il grafo che si ottiene alla fine di questo procedimento è il seguente:


Il nostro problema iniziale consisteva nell'assegnare un numero (da 1 a N) a ciascuna delle caselle della matrice. Il corrispondente problema sul grafo è assegnare un numero (da 1 a N) ad ogni nodo del grafo ottenuto.
In questo grafo, infatti, ogni nodo corrisponde a due caselle della matrice originaria. Sappiamo che queste due caselle conterranno lo stesso numero, corrispondente alla giornata in cui si disputerà la gara di andata tra le squadre in questione: per determinare la giornata della gara di ritorno basterà aggiungere N-1.

Se ci viene dato un grafo come quello della figura precedente, come possiamo procedere per assegnare un numero da 1 a N a ciascun nodo?
L'unico vincolo che dobbiamo rispettare è che a due nodi collegati tra loro non può essere assegnato lo stesso numero.
Spesso, per rendere il problema più... vivace, anziché assegnare un numero da 1 a N a ciascun nodo del grafo, si assegna un colore, preso da una gamma di N colori.
Il vincolo diventa allora che due nodi contigui non possono condividere lo stesso colore (a volte si descrive questo vincolo dicendo che "non possono esistere archi monocromatici").
E' chiaro che usando colori invece che numeri, il problema non muta minimamente la sua struttura matematica.
I matematici chiamano questo problema graph coloring, cioè colorazione dei grafi.
Si tratta di un problema molto noto nell'ambito della ricerca operativa, cioè di quella parte della matematica e dell'informatica che si occupa di formalizzare problemi complessi di ottimizzazione attraverso modelli matematici, allo scopo di trovare soluzioni ottime, se possibile, o approssimate.
Tornerò sull'argomento in altri post; qui mi limito a sottolineare che colorare i grafi (ovviamente rispettando la condizione degli archi monocromatici) non è per niente affare da poco, anzi il più delle volte rappresenta un problema molto difficile.
Nella prossima parte, quindi, vedremo come il problema del campionato convenga che sia risolto utilizzando altri metodi, molto più semplici.
Valeva la pena, però, fare questa deviazione: anche se non fruttuosa sul piano della ricerca di tecniche risolutive, per lo meno interessante e, spero, divertente.