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

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

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

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

Литература

  • Mulder H.M. The interval function of a graph, Mathematical Centre Tracts 132. — Amsterdam, 1980.