Просмотр кода страницы Labeled graph, labelled graph

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

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

<math>l_{V}: \; V \rightarrow C_{V}</math> is the node-labeling function,

<math>l_{E}: \; E \rightarrow C_{E}</math> is the edge-labeling function.

Similarly, a labeled directed graph, or simply a <math>C-d</math>-graph, is
defined as a directed graph with a labeling function <math>l</math> defined as
above.

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

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