Un algoritmo euristico per il problema del vertex coloring

Un processo stocastico è una famiglia di variabili aleatorie che dipendono da un parametro t. Una variabile aleatoria è una corrispendenza tra una funzione reale e lo spazio campione , detto anche degli eventi elementari. Tali processi si indicano con X(t; x), ove t è solitamente il tempo tramite il quale indicizziamo l’estrazione della variabile aleatoria; x 2 un possibile evento, dato dalla combinazione tra gli elementi di . A seconda della numerabilità degli insieme di appartenenza di t ed x i processi aleatori si classificano in: – processi aleatori tempo continuo a valori continui; – processi aleatori tempo continuo a valori discreti; – processi aleatori tempo discreto a valori continui; – processi aleatori tempo discreto a valori discreti. Nel seguito verrà analizzata l’ultima classe. Questi processi sono di uso comune in moltissime applicazioni, e vi è una letteratura praticamente sconfinata a riguardo. Si fornisce una trattazione solo in visione di ciò che servirà nel seguito. Per i processi trattati una delle proprietà più importanti è la propietà di Markov al punto che i processi che la posseggono sono detti Markoviani. Tra questi troviamo poi le catene di Markov, o Markov Chain(MC).