Labeled graph, labelled graph

Labeled graph, labelled graph --- помеченный граф.

Let [math]\displaystyle{ C = (C_{E}, C_{V}) }[/math] be a pair of distinct sets of labels; [math]\displaystyle{ C_{V} }[/math] (resp. [math]\displaystyle{ C_{E} }[/math]) stands for node (resp. edge or arc) labels. A labeled graph over [math]\displaystyle{ C }[/math], or simply a [math]\displaystyle{ C }[/math]-graph, consists of a graph [math]\displaystyle{ G = (V,E,Ends) }[/math] and a labeling function which is a pair of mappings [math]\displaystyle{ l = (l_{V}, l_{E}) }[/math] such that:

[math]\displaystyle{ l_{V}: \; V \rightarrow C_{V} }[/math] is the node-labeling function,

[math]\displaystyle{ l_{E}: \; E \rightarrow C_{E} }[/math] is the edge-labeling function.

Similarly, a labeled directed graph, or simply a [math]\displaystyle{ C-d }[/math]-graph, is defined as a directed graph with a labeling function [math]\displaystyle{ l }[/math] defined as above.

A labeled graph [math]\displaystyle{ G = (V,E,\lambda) }[/math], where [math]\displaystyle{ \lambda }[/math] is a labeling function, is isomorphic to a labeled graph [math]\displaystyle{ G' = (V', E', \lambda') }[/math] if there is a pair [math]\displaystyle{ \phi = (\phi_{V}, \phi_{E}) }[/math] of one-to-one mappings [math]\displaystyle{ \phi_{V}: \; V \rightarrow V' }[/math] and [math]\displaystyle{ \phi_{E}: \; E \rightarrow E' }[/math] such that [math]\displaystyle{ \phi_{E}((v,w)) = (\phi_{V}(v),\phi_{V}(w)) }[/math] for every [math]\displaystyle{ (v,w) }[/math] in [math]\displaystyle{ E(G) }[/math] and [math]\displaystyle{ \lambda_{V'} \circ \phi_{V} = \lambda_{V} }[/math] and [math]\displaystyle{ \lambda_{E'} \circ \phi_{E} = \lambda_{E} }[/math].

If a subgraph [math]\displaystyle{ G }[/math] of [math]\displaystyle{ G' }[/math] is isomorphic to a labeled graph [math]\displaystyle{ G'' }[/math], [math]\displaystyle{ G }[/math] is called an occurrence of [math]\displaystyle{ G'' }[/math] in [math]\displaystyle{ G' }[/math]. Two occurrences [math]\displaystyle{ O = (V_{O},E_{O},\lambda) }[/math] and [math]\displaystyle{ O' = (V_{O'},E_{O'},\lambda') }[/math] are overlapping in [math]\displaystyle{ G }[/math], if the set of vertices [math]\displaystyle{ V_{O} \cap V_{O'} }[/math] is not empty.