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

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

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

Литература

[Mulder]