A labeled multigraph G is a multigraph with labeled nodes and edges. Formally it is a 8-tuple where

• Σ_V and Σ_E are finite alphabetes of the available node and edge labels,
• V and E are disjoint sets of nodes and edges,
• and are two maps indicating the source and target node of an edge,
• and are two maps describing the labeling of the nodes and edges.

As a multigraph is a graph with multiple edges, i.e. edges with the same source and target node, a labeled multigraph is a labeled graph with multiple labeled edges, i.e. edges with the same source and target node and the same edge label .