Docente: Franca Rinaldi

L’idea di proporre una attività centrata sulla teoria dei grafi nasce dall’interesse suscitato negli studenti da un seminario sullo stesso argomento presentato nell’ambito di una precedente edizione del PLS.

Si prevede che l’attività comprenda due seminari introduttivi ed almeno tre lezioni in laboratorio. Nei seminari verranno presentati i concetti di base della teoria dei grafi ed in particolare cammini e circuiti, tagli, alberi di supporto, accoppiamenti, insiemi indipendenti, ricoprimenti di nodi e di lati, colorature ed i problemi di ottimizzazione e/o decisione ad essi associati. Per ciascun problema teorico verrà illustrata una semplice applicazione ad un problema reale. Gli argomenti presentati durante i seminari verranno ripresi e approfonditi durante le lezioni in laboratorio in cui insieme agli studenti verrà discussa la formalizzazione di alcuni problemi reali come problemi su grafi.

Verranno inoltre descritte e commentate le procedure risolutive per alcuni problemi più semplici, quali il problema del cammino minimo ed il problema dell’albero di supporto di costo minimo. Alcune istanze dei problemi descritti verranno risolte dagli studenti utilizzando software disponibile in laboratorio o implementato, se le competenze informatiche lo consentono, dagli studenti stessi.

Si sottolinea che la proposta introduce argomenti di matematica discreta di facile comprensione, che non richiedono conoscenze propedeutiche particolari e che tuttavia presentano un ampio spettro di applicazioni interessanti e di grande rilievo nell’organizzazione di sistemi complessi. Pertanto tale proposta offre da un lato un ampliamento delle conoscenze matematiche degli studenti e dall’altro un esempio di come la matematica costituisca uno strumento indispensabile per la risoluzione di diverse problematiche della vita reale.

• Enti e persone collegate