[DUS | Prednáška] 3 - Strom pokrytia, Živosť PS

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúci výklad o grafe dosiahnuteľnosti Petriho siete a rieši problém, ako rozhodnúť, či má daná sieť konečný alebo nekonečný počet dosiahnuteľných značkovaní. Vysvetľuje sa, že ak sa v postupnosti spustiteľných prechodov nájdu dve značkovania M1 a M2, kde M2 je väčšie alebo rovné M1 (nikde nemá menej značiek a aspoň niekde viac), potom je sekvenciu prechodov možné opakovať neobmedzene a vzniká nekonečne veľa dosiahnuteľných značkovaní, keďže zmena spôsobená spustením prechodov je vždy konštantná a daná príslušnými stĺpcami incidenčnej matice. Táto podmienka je nielen postačujúca, ale aj nutná, čo vyplýva z Dicksonovej lemy — tvrdí, že v každej nekonečnej postupnosti nezáporných celočíselných vektorov (značkovaní) sa nutne nájde dvojica, kde neskoršie značkovanie je väčšie alebo rovné skoršiemu. Princíp dôkazu je ilustrovaný na jednoduchom príklade trojrozmerných vektorov, kde počet vzájomne neporovnateľných vektorov je vždy konečný.

• - Nadviazanie na graf dosiahnuteľnosti Petriho siete z predchádzajúcej prednášky
• - Cieľ: nájsť podmienku na rozhodnutie konečnosti/nekonečnosti počtu dosiahnuteľných značkovaní
• - Definícia usporiadania značkovaní: M2 ≥ M1, ak M2 nikde nemá menej a aspoň niekde viac značiek
• - Ak je prechod spustiteľný v M1, je spustiteľný aj v M2 (a rovnako pre celé postupnosti prechodov)
• - Zmena značkovania spôsobená prechodom je konštantná, daná stĺpcom incidenčnej matice
• - Nájdenie dvojice M1, M2 (M2≥M1) v dosiahnuteľnej postupnosti implikuje nekonečný počet značkovaní
• - Dicksonova lema ako nutná podmienka: v každej nekonečnej postupnosti nezáporných celočíselných vektorov existuje dvojica, kde neskorší vektor je väčší alebo rovný skoršiemu

Zhrnutie pripravené s pomocou AI z prepisu videa.