Focus

Grafi, diamanti e parole. Riconoscere grafi bilanciati e privi di diamanti attraverso parole di Dyck.

Talvolta, in certi casi e per certi dati di ingresso, sappiamo che problemi altrimenti difficili in generale diventano di facile soluzione. Naturalmente, dobbiamo essere in grado di riconoscere tali "casi fortunati" e di caratterizzare le "fortunate proprietà" al fine di sfruttarle per elaborare efficienti algoritmi di riconoscimento. In altre parole, dobbiamo essere in grado di rispondere "efficientemente" alla seguente domanda: "è questo un caso fortunato?"; se la risposta è sì, allora siamo parimenti fortunati giacché sapendo che il problema è di facile soluzione basta risolverlo. Se la risposta è no.... ebbene, inquesto caso, non possiamo dirci fortunati e siamo costretti a battere altre strade. Possiamo legittimamente lamentarci e rammaricarci per la cattiva sorte, tuttavia non possiamo certo rimpiangere il tempo perduto per aver frainteso la complessità del problema. In un recente lavoro [Nicola Apollonio, Anna Galluccio. Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths. SIAM J. Discrete Math. 29(4): 1837-1863 (2015)] abbiamo caratterizzato una classe speciale di "grafi bilanciati" (i"grafi bilanciati privi di diamanti"),ovvero una classe di casi fortunati per molti interessanti problemi di programmazione lineare intera. Cerchiamo di capire il significato delle "misteriose" frasi precedenti. Consideriamo a tal fine una comunità di persone (ad esempio, un social network). Supponiamo di avere un foglio di carta grande abbastanza per poterci scrivere il nome di ogni membro della comunità. Tracciamo ora una linea, di forma arbitraria, che unisca due membri della comunità quando questi si conoscano. Ebbene, ciò che si ottiene in questo modo è una rappresentazione di un oggetto matematico noto come"grafo". Chiaramente, cambiando le entità in gioco, i grafi possono essere usati per modellare una grande varietà di relazioni mentre la matematica soggiacente è sempre la stessa. Guardiamo un po' più approfonditamente al nostro grafo. Supponiamoper esempio di essere interessati a quei membri della comunità la cui età anagrafica non superi i trent'anni (o a coloro i quali abbiano cittadinanza italiana o anche a quelli che bevano di solito un succo specifico e così via). Possiamo quindi formare una sottorete eliminando dal nostro disegno tutti i membri salvo quelli che ci interessano e conservando le linee che li collegano. Ciò che otteniamo in questo modo è la rappresentazione di un"sottografo indotto" del grafo originale. Inoltre, i membri della comunità possono formare sottocomunità, vale a dire gruppi di membri che si conoscono a vicenda all'interno del gruppo e tali che qualsiasi altro membro esterno ai gruppi non conosca almeno un membro all'interno del gruppo. Ebbene ogni siffatta sottocomunità è nota come "clique massimale" del grafo. Cerchiamo dicapire che cosa è un grafo bilanciato. Immaginiamo dunque di essere in grado di offrire due tipi di servizi ai membri del social network (diciamo, l'accesso gratuito a due libri di testo differenti--- che regalo delizioso per la rete ..) in modo tale che: 1) a nessuna comunità venga offerto un solo tipo di servizio (a meno che la sottocomunità non si riduca ad un solo membro) e 2) la proprietà del punto 1) valga per ogni sottorete; bene, in questo caso si dice che la rete è bilanciata. Infine, supponiamo di voler selezionare membri della rete sociale per renderli responsabili di qualche aspetto relativo alle sottocomunità cui appartengono (per esempio,per la raccolta di osservazioni sui due libri di testo ad accesso libero) in modo tale che ogni sottocomunità della rete abbia almeno un responsabile. Un tale gruppo di responsabili è un esempio di ciò che è chiamato "trasversale delle clique" del grafo. Ebbene, se la rete è bilanciata, la matematica dell'ottimizzazione combinatoria ci garantisce che il problema di trovare un "trasversale delle clique" con il minor numero possibile di membri, è un problema facile essendo tuttavia difficile in generale. Quindi, ciò che rimane da fare in questo caso è solamente "il rispondere" alla domanda "è la rete sociale in esame una rete bilanciata?". Sotto alcune ulteriori restrizioni sul grafo, studiando la combinatoria di certe parole (stringhe di lettere) note come parole di Dyck, siamo stati in grado di rispondere all'ultima domanda posta.