Petrijev graf

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Petrijev graf je grafična ponazoritev Petrijeve mreže z biparitetnim usmerjenim grafom.

Za dano Petrijevo mrežo

C = (P, T, I, O)

definiramo Petrijev graf kot:

$G = (V, A)$
$V = P \cup T$
$\forall a_i \in A , a_i = (v_j , v_k): (v_j \in P \land v_k \in T) \oplus (v_j \in T \land v_k \in P)$
$\forall p_i \in P, t_j \in T: ( \#((p_i, t_j), A) = \#(p_i, I(t_j)) ) \land ( \#((t_j, p_i), A) = \#(p_i, O(t_j)) )$

Opomba: množica usmerjenih povezav A je posplošena množica, zato lahko vsebuje več povezav z enakimi spojišči.

Elementi

Elementi Petrijevega grafa so:

mesta: ustrezajo mestom p v Petrijevi mreži; označimo jih s krogom: $\circ$
prehajanja: ustrezajo prehodom t v Petrijevi mreži; označimo jih s črto: |
usmerjene povezave: ustrezajo vhodnim in izhodnim funkcijam Petrijeve mreže; označimo jih s puščico: $\uparrow$

Primer

MIS 1-12.png

Petrijeva mreža:
P = {p₁,p₂,p₃,p₄,p₅}
T = {t₁,t₂,t₃}

I(t₁) = {p₁}	O(t₁) = {p₂,p₃,p₅}
I(t₂) = {p₂,p₃,p₅}	O(t₂) = {p₅,p₅}
I(t₃) = {p₃,p₅}	O(t₃₎ = {p₄}

Matematična definicija

Petrijev graf $G$ je biparitetni usmerjen multigraf

G = (V, A)

,

kjer je

V = {v 1, v 2,..., v s}

množica spojišč in

a = {a 1, a 2,..., a r}

posplošena množica usmerjenih povezav

$a_i=(v_j,v_k) \in V$ .

Množica $V$ je

$V=P \cup T$

in za vsako usmerjeno povezavo $a_i \in A$ velja:

a i = (v j, v k)

,

kjer je

$v_j \in P$ in $v_k \in T$

ali

$v_j \in T$ in $v_k \in P$ .

Definirajmo $V=P \cup T$ . $A$ je posplošena množica usmerjenih povezav, tako da za vsak $p_i \in P$ in $t_j \in T$ velja:

$\#((p_i,t_j),A)=\#(p_i,I(t_j))$
$\#((t_j,p_i),A)=\#(p_i,O(t_j))$

V tem primeru je Petrijev graf $G = (V, A)$ ekvivalenten Petrijevi mreži $C = (P, T, I, O)$ .

Vzpostavljeno iz »http://www.e-studij.si/Petrijev_graf«

Kategoriji: UL/FRI/UNI-RI/MIS | UL/FRI/VSP-RI/OMIS

Osebna orodja

Tiskanje/izvoz

orodja