Marked graph

---

title: "Marked graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["petri-nets"] description: "Specific type of Petri net" topic_path: "general/petri-nets" source: "https://en.wikipedia.org/wiki/Marked_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Specific type of Petri net ::

A marked graph is a Petri net in which every place has exactly one incoming arc, and exactly one outgoing arc. This means, that there can not be conflict, but there can be concurrency. Mathematically: \forall p\in P: |p\bullet|=|\bullet p|=1. 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

::figure[src="https://upload.wikimedia.org/wikipedia/commons/9/93/Marked_Graph_example1.png" caption="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.

References

References

1. (October 1982). "Petri Nets and Marked Graphs–Mathematical Models of Concurrent Computation". The American Mathematical Monthly.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::