Un graphe de fluence, du fait de sa constitution en noeuds et arcs, peut ètre représenté par une seule matrice. Les noeuds repèrent les lignes de la matrice, les arcs les colonnes. Pour le bigraphe qu'est le RdP, il nous faut utiliser deux matrices:
- La matrice définissant les arcs entrants des transitions ou matrice PRE (précédent).
- La matrice définissant les arcs sortants des transitions ou matrice POST.
Matrices PRE et POST du réseau ci-contre sont données ci-après:
PRE
POST
|
|
notations :
POST(ti) : colonne ti de POST
POST(pj) : ligne pi de POST
Elément nij des matrices respectives PRE et POST : PRE(pj,ti) et POST(pi,tj)
Le marquage M d'un réseau se caractérise par l'application : M : P ----> N
On vérifie pour le réseau (
) et son marquage M0 que :
M0 => PRE(t1)
t1 est donc franchissable.
par contre : M0
< PRE(t2) soit t2 non
validé
Dans ces conditions, tout nouveau marquage M'(p) de la place p à partir d'un précédent marquage M(p) s'obtient en effectuant l'opération:
M'( p ) = M( p ) - PRE(p, t) + POST( t, p )
Cette opération n'est valide que si: M(p) - PRE(p, t) >= 0
La généralisation à l'ensemble des places du réseau consiste à écrire:
M' = M - PRE( t ) + POST( t )
Au vecteur de marquage M est retranchée la colonne PRE(t) (ce sont les retraits de jetons) tandis que la colonne POST(t) est additionnée (ce sont les rajouts).
Le franchissement d'une transition t n'est autorisée que si aprés exécution de la seule soustraction
M - PRE(t) = M"
on vérifie qu'aucun des éléments du marquage intermédiaire M" n'est négatif. Il faut tout naturellement :
M => PRE(t)
C'est la précondition de franchissement, relation notée:
M(t>
Au franchissement de t correspond une relation dans N x t x N notée:
M(t>M' ( m = | P | )
M, par le franchissement de t, amène M'.
MATRICE D'INCIDENCE
Pour un réseau de Petri pur, soit: (°t ^ t°) = vide, on observe que si
PRE(p, t) /= 0 alors POST(p, t) = 0
et vice versa.
Dans ces conditions, puisque le franchissement d'une transition t implique l'exécution de la soustration
POST( t ) - PRE( t )
Il est commode de disposer directement de la matrice d'incidence C, telle que:
C = POST - PRE
Pour le réseau ( ) on obtient par exemple:
2 0 1 0 0 1 0 3
2 -1 1 -3
0 4 0 0 1 0 0 0
-1 4 0 0
C = 0 1 0 0
- 0 0 2 0 =
0 1 -2 0
0 0 0 1 0 0 1 0
0 0 -1 1
0 0 1 0 0 0 0 1
0 0 1 -1
POST PRE
Alors, l'équation de calcul du marquage M(k+1) à partir de Mk pour le franchissement de la transition ti s'écrit:
M(k+1) = M(k) + C( ti )
Nota-Bene :
L'application directe de cette équation pour le calcul du marquage consécutif au
franchissement de la transition ti permet toujours le test de validation de la transition ti. Il suffit de vérifier qu'aucune
des valeurs de la colonne M(k+1) est négative (pas de jetons négatifs dans un RdP).
INVARIANCES dans un RdP
Preuves:
L'étude des bonnes ou mauvaises propriétés d'un réseau ou la mise en évidence de propriétés
par preuves formelles passe souvent par l'écriture des invariants du RdP. Les preuves formelles doivent permettre la mise en évidence
des caractéristiques d'un RdP annoncant telle ou telle qualité (ou défaut) du réseau.
- Invariant de PLACES :
Un vecteur I de longueur égale au nombre de places du réseau (nombre de rangées de la matrice d'incidence) est un invariant de places pour ce réseau si il est solution du système :
0
0
C * I = .
.
0
- Invariant de TRANSITIONS :
Un vecteur J de longueur égale au nombre de transitions du réseaux (nombre de colonnes de la matrice d'incidence
C ) est un invariant de transitions pour ce réseau si il est solution du système :
0
0
CT * J = .
.
0