H-distance

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

[math]\displaystyle{ H }[/math]-distance --- [math]\displaystyle{ H }[/math]-расстояние.

Let [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math] be two graphs of the same order and size such that [math]\displaystyle{ V(G_{1}) = V(G_{2}) }[/math], and let [math]\displaystyle{ H }[/math] be a connected graph of order at least 3.

A [math]\displaystyle{ G_{1} - G_{2} }[/math] [math]\displaystyle{ H }[/math]-path is a sequence [math]\displaystyle{ G_{1}=F_{0}, F_{1}, \ldots, F_{k} = G_{2} }[/math] of graphs of the same order and the same size such that [math]\displaystyle{ F_{i} }[/math] is [math]\displaystyle{ H }[/math]-adjacent to [math]\displaystyle{ F_{i+1} }[/math] for [math]\displaystyle{ i = 0,1, \ldots, k-1 }[/math]. The graphs [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math] are [math]\displaystyle{ H }[/math]-connected if there exists a [math]\displaystyle{ G_{1} - G_{2} }[/math] [math]\displaystyle{ H }[/math]-path. For [math]\displaystyle{ H }[/math]-connected graphs [math]\displaystyle{ G_{1} }[/math] and [math]\displaystyle{ G_{2} }[/math], the [math]\displaystyle{ H }[/math]-distance [math]\displaystyle{ d_{H}(G_{1},G_{2}) }[/math] from [math]\displaystyle{ G_{1} }[/math] to [math]\displaystyle{ G_{2} }[/math] is the minimum number of [math]\displaystyle{ H }[/math]-adjacencies required to transform [math]\displaystyle{ G_{1} }[/math] into [math]\displaystyle{ G_{2} }[/math].