Интервальная функция: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Интервальная функция''' (''[[Interval function]]'') | '''Интервальная функция''' (''[[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>. | Для [[дерево|дерева]] интервальная функция для любых двух его [[вершина|вершин]] <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. | |||
Текущая версия от 16:29, 22 февраля 2011
Интервальная функция (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.