Интервальная функция

Интервальная функция (Interval function) - пусть [math]\displaystyle{ G = (V,E) }[/math] --- граф и пусть [math]\displaystyle{ {\mathcal P}(V) }[/math] --- множество всех подмножеств из [math]\displaystyle{ V }[/math]. Отображение [math]\displaystyle{ I_{G}: \; V \times V \leftarrow {\mathcal P}(V) }[/math], определяемое как [math]\displaystyle{ I_{G}(u,v) = \{w \, | \, w \in V, \, w }[/math] лежит на кратчайшем пути [math]\displaystyle{ P(u,v) }[/math] в графе [math]\displaystyle{ G\}, }[/math] называется И.ф. графа [math]\displaystyle{ G }[/math].

Для дерева интервальная функция для любых двух его вершин [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] дает образ, состоящий из вершины единственного кратчайшего пути, соединяющего пару [math]\displaystyle{ u, v }[/math].

Литература

[Mulder]