Интервальная функция: различия между версиями

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

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

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