Petri ağı

**Petri ağları** (yer/geçiş ağları, Y/G ağları olarak da bilinir), sistemlerin analizi ve modellenmesi için kullanılan güçlü bir araçtır. Petri ağları, bir sistemin matematiksel bir modelle temsil edilmesine olanak tanır ve süreçlerin grafiksel bir notasyon ile ifade edilmesini sağlar. Bu ağlar, geçiş (transition) ve yerleşim (place) düğümlerinden oluşan, tek yönlü iki parçalı bir grafik yapısına sahiptir.

Oklarla gösterilen yönlü kenarlar, bir geçişten önce ve sonra hangi konumların bulunduğunu tanımlar. Bu yapı, süreçlerin akışını ve eşzamanlı işlemleri görselleştirmenin yanı sıra matematiksel olarak analiz etmeye de olanak tanır.

Petri ağlarının, 1939 yılında henüz 13 yaşında olan Carl Adam Petri tarafından kimyasal süreçleri tanımlamak amacıyla geliştirildiği belirtilir. Ancak, bu model 1960'larda daha kapsamlı bir matematiksel temel üzerine oturtulmuş ve sistem analizi için önemli bir araç haline gelmiştir.

Petri ağları, endüstride yaygın olarak kullanılan UML (Unified Modeling Language), BPMN (Business Process Model and Notation) ve EPC (Event-driven Process Chain) gibi standart grafiksel modelleme yöntemlerine benzer şekilde süreçlerin seçim, tekrarlama ve eşzamanlılık gibi özelliklerini temsil eder. Bununla birlikte, Petri ağlarının ayırt edici özelliği, bu standartların ötesine geçerek:

* Matematiksel kesinlikte modelleme yeteneği sunması,
* Süreçlerin analizi için geliştirilmiş matematiksel bir teoriye sahip olmasıdır.

Bu özellikleri sayesinde Petri ağları, özellikle karmaşık ve adımlı süreçlerin analizi ve simülasyonunda benzersiz bir avantaj sağlar.

## Petri ağ temelleri
Bir Petri ağı, yerler (places), geçişler (transitions) ve eğriler (arcs) olmak üzere üç temel bileşenden oluşur. Bu bileşenler, graf teorisinde düğümler ve kenarlar kavramlarıyla eşdeğerdir.

### Petri Ağ Yapısı Elemanları

#### Yerler ve Geçişler
Yerler ve geçişler düğümlerdir, ancak aralarındaki eğriler (kenarlar) yalnızca bir yerden bir geçişe veya bir geçişten bir yere doğru yönlendirilmiş olabilir.

İki yer arasında veya iki geçiş arasında doğrudan bir eğri olamaz.

Bir geçişe bağlanan eğri, hangi yerden geliyorsa bu yer geçişin giriş yeri olarak adlandırılır.

Geçişten çıkan eğrinin bağlandığı yer ise geçişin çıkış yeridir.

#### Jetonlar (Tokens)
Grafiksel olarak, bir Petri ağındaki bir yer ayrık sayıda jeton (token) içerebilir. Jetonlar, sistemin mevcut durumunu temsil eder.

### Temel Kavramlar

#### İşaretleme, Konfigürasyon (Marking)
Jetonların yerler üzerindeki dağılımı, işaretleme veya konfigürasyon olarak adlandırılır. Bu dağılım, sistemin herhangi bir andaki durumunu gösterir

#### Geçişlerin Tetiklenmesi

##### Etkinleştirme (Enabling)
Bir geçiş, giriş yerlerinde yeterli sayıda jeton bulunduğunda etkinleştirilir veya tetiklenebilir hale gelir.

##### Tetikleme (Firing)
Etkinleştirilmiş bir geçiş tetiklendiğinde giriş yerlerinden belirli sayıda jeton tüketilir ve çıkış yerlerine belirli sayıda jeton üretilir.

##### Ağırlıklar (Weights)
Tetikleme sırasında tüketilen ve üretilen jeton miktarları, geçişlerin üzerindeki ağırlıklarla belirlenir. Bu, ayrık sistemlerde her geçişin farklı gereksinimlerini modellemek için kullanılır.

##### Deterministik Olmama Durumu
Tetikleme işlemi anlıktır, yani bir geçiş tamamen gerçekleşir ve yarıda bırakılamaz. Ancak Petri ağları, belirli bir çalışma kuralı belirtilmedikçe deterministik değildir. Aynı anda birden fazla geçiş tetiklenebilir durumda olduğunda, hangisinin tetikleneceği bilinemez. Bu durum, sistemin rastlantısallığını veya kararsızlığını modellemek için kullanışlıdır.

### Eşzamanlılık ve Dağıtılmış Sistemler
Petri ağları, eşzamanlı davranışı ve dağıtılmış sistemleri modellemek için uygundur. Bunun nedenleri:

* **Tetikleme Sırası:** Aynı anda birden fazla geçiş tetiklenebilir. Bu durum, birden fazla olayın eşzamanlı olarak gerçekleşebileceği sistemleri modellemek için idealdir.
* **Dağıtılmış Yapı:** Bir ağdaki yerlerin her birinde farklı sayıda jeton bulunabilmesi, **dağıtılmış sistemlerin** karmaşıklığını ve dinamiklerini simüle etmeyi mümkün kılar.

## Resmi tanım ve temel terminoloji

### Petri Ağları: Tanım ve Çalışma Prensipleri

#### Tanım 1: Ağ Yapısı
Bir Petri ağı, N=(P, T,F) olarak tanımlanan üç parametreli bir ağdır:

* P: Yerler kümesi (places) — ayrık ve sonlu.
* T: Geçişler kümesi (transitions) — ayrık ve sonlu.
* F: Akış ilişkilerinin (flow) kümesi, F⊆(P×T)∪(T×P). Bu, eğrilerin yönlerini ifade eder.

#### Tanım 2: Konfigürasyon
Bir konfigürasyon, N=(P, T,F) ağı üzerindeki bir yerler alt kümesi C⊆P ile gösterilir. Konfigürasyon, jetonların sistem üzerindeki anlık dağılımını temsil eder.

#### Tanım 3: Basit Ağ
Bir basit ağ, EN=(N, C) formundadır:

* N=(P, T,F), bir ağ yapısıdır.
* C, C⊆P olan bir konfigürasyondur. Bu durumda, her yer en fazla bir jeton içerebilir.

#### Tanım 4: Petri Ağı
Bir Petri ağı, aşağıdaki üçlüyle tanımlanır: PN=(N, M,W)

# **Ağ Yapısı (N=(P, T,F)):**
#* P: Yerler kümesi.
#* T: Geçişler kümesi.
#* F: Yönlü eğrilerden oluşan akış kümesi.
# **İşaretleme Fonksiyonu (M):**
#* M:P→Z, yerlerdeki jetonların (tokens) sayısını belirler.
#* Z, sayılabilir tam sayılar kümesidir.
#* M, işaretleme (marking) olarak adlandırılır ve sistemin mevcut durumunu ifade eder.
# **Ağırlık Fonksiyonu (W):**
#* W:F→Z, eğriler üzerindeki ağırlıkları (çarpan katsayıları) belirler.
#* Ağırlık, bir geçiş sırasında kaç jetonun tüketileceği veya üretileceğini gösterir.

### Basit Ağlar ve Petri Ağları Arasındaki Farklar
**Basit Ağlar:** Her yer yalnızca bir jeton içerebilir (Z={0,1}). Jetonların durumu sadece "var" veya "yok" olarak ifade edilir.

**Petri Ağlarıː** Her yer birden fazla jeton içerebilir. Jeton dağılımı M, çoklu kümelerle ifade edilir ve daha genel bir modelleme kapasitesine sahiptir.

Bu farklılık, Petri ağlarını karmaşık sistemlerin ve eşzamanlı işlemlerin modellemesi için uygun hale getirir.

### Petri Ağı Diyagramları
Petri ağları genellikle şu grafiksel gösterimle temsil edilir:

* **Yerler:** Çemberlerle gösterilir.
* **Geçişler:** Uzun ve dar dikdörtgenlerle gösterilir.
* **Eğriler:** Yerlerden geçişlere veya geçişlerden yerlere yönlendirilmiş oklarla ifade edilir.

**Basit ağlarda**, her çember yalnızca bir jeton içerebilir. Ancak Petri ağlarında, çemberler birden fazla jeton içerebilir ve bu jetonların ağ üzerindeki dağılımına işaretleme (marking) denir.

### Örnek: Geçişlerin Tetiklenmesi

# **Geçiş Aktivasyonu:**
#* Bir geçiş, yalnızca giriş yerleri gerekli sayıda jeton içerdiğinde etkinleştirilir.
#* Bir yerin "yeterli jeton" içermesi, o yerden geçişe giden eğrinin ağırlığı kadar veya daha fazla jeton bulunması anlamına gelir.
# **Geçişin Tetiklenmesi:**
#* Etkinleştirilmiş bir geçiş tetiklendiğinde giriş yerlerinden belirli sayıda jeton tüketilir. Çıkış yerlerine belirli sayıda jeton eklenir.
#* Bu işlem, ağın mevcut konfigürasyonunu değiştirir.

### Örnek Senaryo

* **PN₀ Petri Ağı:** M0 işaretlemesiyle, p1 yerindeki jetonlar **t** geçişini etkinleştirir.
* **Tetikleme:** t'nin tetiklenmesi, M0'dan M1'e geçiş yapılmasını sağlar.
* **PN₁ Petri Ağı:** M1 işaretlemesi, t'nin tetiklenmesiyle elde edilen yeni konfigürasyonu temsil eder.

### Sentaks
Bir **Petri ağı grafı** (bazı kaynaklarda Petri ağı olarak da adlandırılır), aşağıdaki şekilde üç elemanlı bir yapı (S, T,W) olarak tanımlanır:

# **S:** Yerlerin (places) sonlu kümesidir.
# **T:** Geçişlerin (transitions) sonlu kümesidir.
# **S ve T:**
#* Ayrıktır, yani herhangi bir nesne hem bir yer hem de geçiş olamaz. Bir nesne ya bir yer (S) ya da bir geçiş (T) olmak zorundadır.
# **W:(S×T)∪(T×S)→N:**
#* Eğriler kümesidir (weights).
#* Her eğriye negatif olmayan bir tam sayı atanır, bu sayı eğrinin **ağırlığını** temsil eder.

#### Akış İlişkisi

* Akış ilişkisi, eğrilerin kümesiyle tanımlanır: F={(x, y)∣W(x, y)>0} Yani W(x, y)>0 koşulunu sağlayan tüm eğriler bu ilişkiye dahildir.
* Bazı kaynaklarda, eğrilerin ağırlığının yalnızca 1 olduğu varsayılır. Bu durumda, Petri ağı genellikle W yerine F ile ifade edilir ve ağ bir **iki parçalı multigraf** (S∪T, F) haline gelir.

### Girdi ve Çıktı Kümeleri

# **Bir Geçişin Girdi ve Çıktı Kümeleri:**
#* **Girdi Kümesi (⋅t):** ⋅t={s∈S∣W(s, t)>0} Bu, t geçişine bağlanan tüm giriş yerlerini temsil eder.
#* **Çıktı Kümesi (t⋅):** t⋅={s∈S∣W(t, s)>0} Bu, t geçişine bağlanan tüm çıkış yerlerini temsil eder.
# **Bir Yer İçin Girdi ve Çıktı Kümeleri:**
#* Aynı mantıkla, bir yerin girdi ve çıktı kümeleri, geçişler üzerinden tanımlanabilir.

### İşaretleme (Marking)
Bir Petri ağı grafının işaretlemesi, yerlerin bir **çoklu kümesi** ile ifade edilir:

M:S→N

Bu, her bir yere belirli bir sayıda **jeton (token)** atar. Jetonların dağılımı, ağın mevcut durumunu temsil eder ve buna **işaretleme (marking)** denir.

### Petri Ağı
Bir **Petri ağı** (bazı kaynaklarda işaretli Petri ağı olarak da adlandırılır), dört elemanlı bir yapı (S, T,W, M0) ile tanımlanır:

# (S, T,W): Bir Petri ağı grafıdır.
# M0: İlk işaretlemedir. Bu, ağın başlangıçtaki jeton dağılımını temsil eder.

### Çalışma Mantığı

#### Geçişin Ateşlenmesi (Tetiklenmesi)
Bir geçişin ateşlenmesi: Geçişin giriş yerlerinden (s), W(s, t) kadar jeton tüketilir. Geçişin çıkış yerlerine (s), W(t, s) kadar jeton eklenir.

#### Geçişin Etkinleştirilmesi
Bir geçişin etkinleştirilmesi (t):

∀s∈⋅t:M(s)≥W(s, t)

Yani, geçişin giriş yerlerinde tüketim için yeterli jeton bulunmalıdır.

#### Tetikleme Sonrası Durum
Bir geçiş tetiklendiğinde, sistem yeni bir işaretleme (M′) durumuna geçer. Bu, mevcut işaretlemenin güncellenmiş halidir.

### Rastgele Tetiklenmeler
Genellikle, geçişlerin rastgele zamanlarda tetiklendiği durumlar incelenir. Bu, Petri ağlarının deterministik olmayan süreçlerin ve eşzamanlı davranışların modellenmesinde kullanılmasını sağlar.

### Bir adımda ulaşılabilirlik
Eğer M \to_G M' ise, *M* işaretlemesinden bir adımda M' işaretlemesine *ulaşılabilir* deriz*. (Ya da* M' *, M*'den *bir adımda ulaşılabilirdir)*

### Ulaşılabilirlik

#### Temel Kavramlar

##### Reflexive İlişki
Bir ilişki R, her elemanın kendisiyle ilişkili olduğu durumlarda reflexive'dir. Yani: x∈A⟹(x, x)∈R Örneğin, bir grafın her düğümü kendisiyle bağlantılıdır.

##### Transitive İlişki
Bir ilişki R, x→y ve y→z varsa x→z sonucunu içeriyorsa transitive'dir. Yani: (x, y)∈R∧(y, z)∈R⟹(x, z)∈R

##### Closure
Bir ilişkiyi, belirli bir özelliği sağlamak için genişletme işlemine closure denir. Reflexive transitive closure, başlangıçtaki ilişkinin hem reflexive hem de transitive hale getirilmesidir.

##### Reflexive Transitive Closure
Eğer →G bir temel ilişki ise, →G∗, bu ilişkinin reflexive transitive closure'udur. Bu şu anlama gelir:

* **Reflexive:** Her M işaretlemesi için, M→G∗M geçerlidir. Yani bir durum her zaman kendine ulaşabilir.
* **Transitive:** Eğer M1→GM2 ve M2→GM3 varsa, M1→G∗M3 geçerlidir. Bu, dolaylı yolların da ilişkiye dahil olduğu anlamına gelir.

#### Petri Ağı Bağlamında Reflexive Transative Closure
Petri ağlarında →G, bir geçişin tetiklenmesiyle bir işaretlemeden başka bir işaretlemeye geçişi ifade eder. →G∗, bir başlangıç işaretlemesinden herhangi bir adım sayısında başka bir işaretlemeye ulaşılabilirliği ifade eder.

Özetle:

* →G: Bir adımda tetiklenebilen geçiş.
* →G∗: Birden fazla adımda (veya sıfır adımda, çünkü reflexive'dir) ulaşılabilen geçiş.

### Örnek
Eğer:

M1 →G M2 ve M2 →G M3

ise,

M1→G∗ M3

Ayrıca, reflexive özelliği nedeniyle M1→G∗ M1 da geçerlidir.

#### Ulaşılabilirlik Tanımı
Bir **Petri ağı** için ulaşılabilirlik, bir işaretleme (M) durumundan başka bir işaretleme (M′) durumuna, geçişlerin bir dizisi aracılığıyla ulaşıp ulaşılamayacağını ifade eder.

Matematiksel olarak ulaşılabilirlik şu şekilde tanımlanır:

Eğer →G∗, →G ilişkisinin **reflexive transitive closure**'u ise ve M→G∗M′ koşulu sağlanıyorsa, M′ işaretlemesi, M işaretlemesinden ulaşılabilirdir (reachable). Bu, M′'e M'den herhangi bir adım sayısında ulaşılabileceği anlamına gelir.

#### Ulaşılabilirlik Kümesi
Bir Petri ağı için ulaşılabilir işaretlemeler kümesi şu şekilde tanımlanır:

Bir Petri ağı için ulaşılabilir işaretlemeler kümesi şu şekilde tanımlanır:
R(N)={M′ ∣ M0 →G∗ M′}

Burada:

* M0: Başlangıç işaretlemesi.
* M′: Ulaşılabilir bir işaretleme.
* R(N): Petri ağı N'de M0'dan başlayarak tüm olası geçiş dizileriyle ulaşılabilecek işaretlemeler kümesi.

Burada:

* M0: Başlangıç işaretlemesi.
* M′: Ulaşılabilir bir işaretleme.
* R(N): Petri ağı N'de M0'dan başlayarak tüm olası geçiş dizileriyle ulaşılabilecek işaretlemeler kümesi.

### Ulaşılabilirlik grafı
N'nin *ulaşılabilirlik graf*ı, onun ulaşılabilir işaretlemeleriR(N) ile sınırlanmış geçiş ilişkileridir \to_G . Bu, ağın alabileceği tüm durumları gösteren durum uzayı kümesidir.

*G *grafına ve**' <math>M_0</math> **'ilk durumuna sahip bir Petri ağındaki ateşleme sekansı (ya da sıralı ateşleme kümesi)**' <math>\vec \sigma = \langle t_{i_1} \ldots t_{i_n} \rangle</math> **'ile gösterilir. Öyle ki;**'<math>M_0 \to_{G,t_{i_1}} M_1 \wedge \ldots \wedge M_{n-1} \to_{G,t_{i_n}} M_n</math>. Burada tetikleme sekanslarının kümesi  <math>L(N)</math> ile gösterilmiştir.**

## Tanımlardaki farklılıklar

Daha önce de belirtildiği gibi, tanım farklılıklarının en genel olanı, eğri ağırlıklarını göz ardı etmek ve *W* ile gösterilen eğriler multisetini, F \subseteq (S \times T) \cup (T \times S) ile gösterilen ve *akış ilişkisi* olarak adlandırılan bir basit küme ile değiştirmektir. Bu ifade gücünü (*expressive power*) sınırlandırmaz, her ikisi de birbirleri yerine kullanılabilir.

Genel olarak kullanılan bir diğer farklılık da, Desel ve Juhás (2001)'ın da kullandığı üzere, *kapasite*lerin yerler üzerinde tanımlanmış olmasına izin verilmesidir. Aşağıda *ekler* bölümünde bu konu tartışılmıştır.

## Vektör ve matris şeklinde formulasyon - vektörleştirme

Bir Petri ağına ilişkin işaretlemeler(jeton dağılımları)  (S,T,W,M_0)\!, negatif olmayan tam sayıların |S| boyutlu vektörleri olarak ifade edilebilir.

Vektörün geçiş ilişkisi, |S| * |T| boyutundaki bir çift matrisle gösterilebilir:
* W^-, öyle ki \forall s,t: W^-[s,t] = W(s,t)
* W^+, öyle ki \forall s,t: W^+[s,t] = W(t,s).
Ardından farkları olan
*  W^T = W^+ - W^-
ifadesi, ulaşılabilir jeton dağılımlarını matris çarpımı şeklinde göstermek için aşağıdaki şekilde kullanılabilir.

Herhangi bir *w* ateşleme (geçiş/tetikleme) sekansı için, her geçişe kendi ağırlığını *w* atayan bir o(w) yazalım. Bu durumda
* R(N) = \{ M \mid \exists w: M = M_0 + W^T \cdot o(w) \wedge w \!, N'ye ait bir ateşleme sekansı'dır. \}\!.

*w*'nin bir ateşleme sekansı olması gerektiğine dikkat edin; geçişlerin rastgele tetiklenmesine izin vermek, genellikle daha büyük bir küme oluşturur.

 W^{+}=\begin{bmatrix} * & t1 & t2 \\ p1 & 0  & 1 \\ p2 & 1 & 0 \\ p3 & 1& 0 \\ p4 & 0 & 1 \end{bmatrix} 

 W^{-}=\begin{bmatrix} * & t1 & t2 \\ p1 & 1  & 0 \\ p2 & 0 & 1 \\ p3 & 0 & 1 \\ p4 & 0 & 0 \end{bmatrix} 

W^T=\begin{bmatrix} * & t1 & t2 \\ p1 & -1  & 1 \\ p2 & 1 & -1 \\ p3 & 1 & -1 \\ p4 & 0 & 1 \end{bmatrix}

M_{0}=\begin{bmatrix} 1 & 0 & 2 & 1 \end{bmatrix}

## Kaynakça