Partial graph morphism

Материал из WikiGrapp
Версия от 13:32, 9 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Partial graph morphism''' --- частичный морфизм графов. Given two graphs <math>G</math> and <math>H</math> with colors in <math>L</math>, …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Partial graph morphism --- частичный морфизм графов.

Given two graphs [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] with colors in [math]\displaystyle{ L }[/math], a pair of partial mappings [math]\displaystyle{ h = (h_{V}: G_{V} \rightarrow H_{V}, h_{E}: G_{E} \rightarrow H_{E}) }[/math] is called partial graph morphism if

(1) whenever [math]\displaystyle{ h_{E} }[/math] is defined for [math]\displaystyle{ e \in G_{E} }[/math], [math]\displaystyle{ h_{V} }[/math] is defined for [math]\displaystyle{ s_{G}(e) }[/math] and [math]\displaystyle{ t_{G}(e) }[/math], and [math]\displaystyle{ h_{V} \circ s_{G}(e) = s_{H} \circ h_{E}(e) }[/math] and [math]\displaystyle{ h_{V} \circ t_{G}(e) = t_{H} \circ h_{E}(e) }[/math];

(2) whenever [math]\displaystyle{ h_{V} }[/math], respectively [math]\displaystyle{ h_{E} }[/math], is defined for [math]\displaystyle{ o }[/math], [math]\displaystyle{ vl_{G}(o) = vl_{H} \circ h_{V}(o) }[/math], respectively [math]\displaystyle{ el_{G}(o) = el_{H} \circ h_{E}(o) }[/math].

Here two mappings [math]\displaystyle{ s,t: E \rightarrow V }[/math] provide the source and target vertices for each edge, and two mappings [math]\displaystyle{ vl: V \rightarrow L_{V} }[/math], respectively [math]\displaystyle{ el: E \rightarrow L_{E} }[/math], attach a color to every vertex, respectively edge.