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

Интервальная функция (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 H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.