A Petri-gráf olyan hálózat, amely csomópontokból, átmenetekből és ezeket összekötő nyilakból áll. A csomópontokban (jelölésük: doboz) lehetnek úgynevezett bigyók (jelölésük: o), tetszőleges számban. A csomópontokból nyilak indulnak ki, amelyek átmenetekhez (jelölésük: dupla vonal) vezetnek. Az átmenetekből újabb nyilak indulnak ki, amelyek csomópontokba vezetnek stb. A hálózat működése a következő:
Egy átmenet aktivizálódásának az a feltétele, hogy az őt közvetlenül megelőző csomópontokban legyen bigyó. Ha az átmenet aktivizálódik, minden befelé vezető nyílon elszív egy-egy bigyót a szomszédos csomópontokból, majd a belőle kivezető nyilakon (a számuk eltérhet a befelé mutató nyilak számától) elküld egy-egy bigyót az őt követő csomópontokba. Az átmenetekben a bigyók száma változhat: ha a bejövő nyilak vannak többen, a felesleges bigyók eltűnnek; ha a kifelé vezető nyilak száma a nagyobb, új bigyók keletkeznek. Ha egyidejűleg több átmenet is aktivizálódhat, azaz versenyhelyzet alakul ki, akkor véletlenszerűen egy átmenet aktivizálódik közülük.
Ha a hálózat kezdőállapotát (azaz a bigyók kezdeti eloszlását) ismerjük, meghatározhatjuk azokat az állapotsorozatokat, amelyek a hálózat működését jellemzik. (Több ilyen sorozat is lehet, hiszen a versenyhelyzetben lévő átmenetek véletlenszerűen aktivizálódnak.)
Egy adott állapotból egy másik állapot elérhető, ha van olyan átmenet-aktivizálási sorrend, amelynek eredményeképpen a másik állapot bekövetkezik.
Előfordulhat olyan állapot, amelyben egyetlen átmenet sem aktivizálható. Ekkor a hálózat holtpontba került.
A hálózat ciklusba esett, ha
- egy állapot megegyezik valamely korábbi állapottal;
- egy állapot csak abban tér el egy korábbi állapottól, hogy egy vagy több csomópontban több bigyó van, mint korábban volt (ugyanis ilyenkor végtelen számú bigyó halmozódik fel).
- Készíts programot Petri-gráf tárolására! A program kezelője adja meg, hogy hány csomópontja és hány átmenete van a gráfnak, és hogy honnan hová vezetnek a nyilak. Csomópontot számjeggyel, átmenetet betűvel jelölünk. A program legyen képes a tárolt gráf szöveges kiírására, de grafikus megjelenítése nem szükséges. Korlátozások: a csomópontok és az átmenetek száma legfeljebb 8-8; nincsenek párhuzamos nyilak (azaz minden átmenet a működése során egy adott csomópontból legfeljebb egy bigyót szív el, illetve egy adott csomópontba legfeljebb egy bigyót küld); a kezdőállapotban egyetlen csomópontban sem lehet egynél több bigyó. (23 pont)
- A kezdőállapot beolvasása után a program írjon ki egy maximum 8 elemű állapotsorozatot (egyet a lehetségesek közül), amelyen a hálózat működése során áthalad! A program vegye észre, ha a hálózat holtpontba kerül! (27 pont)
- A kezdőállapot beolvasása és egy másik állapot megadása után a program döntse el, hogy a másik állapot elérhető-e legfeljebb 8 lépésben! Ezt úgy állapítsa meg, hogy az adott kezdőállapotból kiindulva állítsa elő és írja ki az összes elérhető állapotot, és vizsgálja meg, hogy ezek között szerepel-e a keresett állapot. (30 pont)
A program szerkezetére, olvashatóságára, áttekinthetőségére maximum
20 pont kapható.
1. példa:
|
|
|
 |
 |
2. példa:
|
|
|
 |
 |
3. példa: (kielégíti az 1. részfeladat feltételeit)
 |
Feltéve, hogy kezdetben az "1" csomópontban vagy egy bigyó, az "a" vagy a "b" átmenet aktivizálódhat (versenyhelyzet). Ha az egyik aktivizálódik, akkor a másik már nem tud, tehát egy bigyó kerül az "2" vagy a "3" csomópontba. Így vagy a "c" vagy a "d" átmenet válhat aktívvá a következő lépésben. A "c" vagy a "d" aktivizálódása visszaviszi a bigyót az "1" csomópontba, és minden kezdődik elölről. A "4" és az "5" csomópontokban a bigyók csak gyűlnek-gyűlnek, és azt számlálják, hogy hányszor volt aktív az "a", illetve a "b" átmenet.