4624
правки
Интервальная функция: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Интервальная функция''' (''[[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>. | '''Интервальная функция''' (''[[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] | [Mulder] | ||