Insieme X invariante
L'insieme X invariante di una rete marcata <N,M0> è un insieme di tutti i vettori che soddisfano l'uguaglianza $$ X^T \cdot M = X^T \cdot M_0 $$
dove
- XT è la trasposta di una matrice contenente i vettori P-invarianti minimali della rete
- M0 è la marcatura iniziale
- M è il vettore con il numero di marche per ogni posto M(p1),M[p2], ... , M[pn]
A cosa serve?
L'insieme X invariante fornisce un'approssimazione della raggiungibilità di una rete marcata .
Tuttavia, si tratta di un'approssimazione per eccesso perché contiene al suo interno sia l'insieme di raggiungibilità R(N,M0) che l'insieme potenzialmente raggiungibile PR(N,M0) della rete
$$ R(N,M_0) ⊆ PR(N,M_0) ⊆ I_X(N,M_0) $$
Nota. Nel caso particolare dei grafi marcati se la rete è viva l'insieme X invariante coincide con l'insieme di raggiungibilità R.
Un esempio pratico
Ho una rete con 3 posti e 3 transizioni.
La marcatura iniziale è M0=[0 1 1 ].
La matrice di incidenza della rete è
$$ C = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} - \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{pmatrix} $$
$$ C = \begin{pmatrix} -1 & 1 & 0 \\ 1 & -1 & 0 \\ 0 & -1 & 1 \end{pmatrix} $$
Questa rete ha un solo vettore P-invariabile minimale x = [1 1 0]
$$ x^T \cdot C = 0 $$
$$ [ 1 \: 1 \: 0 ] \cdot \begin{pmatrix} -1 & 1 & 0 \\ 1 & -1 & 0 \\ 0 & -1 & 1 \end{pmatrix} = [ 0 \: 0 \: 0 ] $$
Pertanto, la matrice X è composta da una colonna
$$ X = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} $$
Ora posso usare la formula iniziale per calcolare l'insieme X-invariante della rete
$$ X^T \cdot M = X^T \cdot M_0 $$
Sostituisco XT con la trasposta della matrice X dei vettori P invarianti.
$$ [1 \: 1 \: 0 ] \cdot M = [1 \: 1 \: 0] \cdot M_0 $$
Sostituisco M0 con la marcatura iniziale della rete marcata ossia M0=[0 1 1 ].
$$ [1 \: 1 \: 0 ] \cdot M = [1 \: 1 \: 0] \cdot \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} $$
La rete ha 3 posti.
Quindi, una qualsiasi marcatura M è composta da un vettore con tre elementi M(p1), M(p2), M(p3)
$$ [1 \: 1 \: 0 ] \cdot \begin{pmatrix} M(p_1) \\ M(p_2) \\ M(p_3) \end{pmatrix} = [1 \: 1 \: 0] \cdot \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} $$
Svolgo il prodotto riga per colonna e ottengo
$$ M(p_1) + M(p_2) = 1 $$
Nota. Le variabili delle marche nei posti della rete M(p1), M(p2), M(p3) sono non negative, perché qualsiasi posto può avere zero, una o più marche.
Pertanto l'insieme X invariante è composto dai seguenti vettori
$$ I_X = \{ [1 \: 0 \: 0] \:,\: [0 \: 1 \: 0] \:,\: [1 \: 1 \: 0] \:,\: [1 \: 0 \: 1] \:,\: [1 \: 1 \: 1] \:,\: [0 \: 1 \: 1] \:,\: ... \} $$
Nell'insieme X invariante ci sono anche le marcature raggiungibili della rete ossia [0 1 1], [1,0,1] e [0 0 2].
Queste ultime sono ben evidenti osservando il grafo di copertura della rete.
Nota. L'insieme X invariante è soltanto una stima per eccesso dell'insieme di raggiungibilità della rete.
E così via.
