{{Short description|Specific type of Petri net}} {{Refimprove|date=May 2025}} {{about|Petri nets|vertex-signed graphs|signed graph}} A '''marked graph''' is a Petri net in which every place has exactly one incoming arc, and exactly one outgoing arc.<ref>{{cite journal |last1=Johnsonbaugh |first1=Richard |last2=Murata |first2=Tadao |title=Petri Nets and Marked Graphs–Mathematical Models of Concurrent Computation |journal=The American Mathematical Monthly |date=October 1982 |volume=89 |issue=8 |pages=552–566 |doi=10.1080/00029890.1982.11995494 |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d71b0c7948883fdece0c6d17f635e90a01aef8a4|url-access=subscription }}</ref>{{rp|p=561}} This means, that there can ''not'' be ''conflict'', but there can be ''concurrency''. Mathematically: <math>\forall p\in P: |p\bullet|=|\bullet p|=1</math>. Marked graphs are used mostly to mathematically represent concurrently running operations, such as a multiprocessor machine's internal process state. This class of Petri nets gets the name from a popular way of representing them: as a graph where each place is an edge and each transition is a node.
==Uses== Marked graphs are mainly used to mathematically represent concurrent mechanisms, in order to be able to mathematically derive certain characteristics of the design.
==Example== 400px|right|Marked Graph example This example presents a Marked Graph, where a process is forked at transition T1 and synchronised at T4. In between, two operations take place in non-deterministic fashion, T2 and T3. In fact, Petri nets are so much non-deterministic, that they may not take place at all. But the reason for having this non-deterministic property is not this, but to mimic real-life experiences which shows that parallel computing always means that it is impossible to determine which process/thread will finish first i.e. which operation(s) will execute faster. This can be due to waiting for I/O in real world, or just the different parameters given to the processes/threads.
==See also== * History monoid * Trace monoid
== References == {{reflist}}
{{DEFAULTSORT:Marked Graph}} Category:Petri nets