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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Интервальная функция''' (''Interval function'') - пусть <math>G = (V,E)</math> --- граф и пусть <mat...)
 
Нет описания правки
Строка 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>G = (V,E)</math> --- граф и пусть <math>{\cal P}(V)</math> --- множество всех
подмножеств из <math>V</math>. Отображение <math>I_{G}: \; V \times V \leftarrow {\cal
P}(V)</math>, определяемое как
<math>I_{G}(u,v) = \{w \, | \, w \in V, \, w\mbox{ лежит на кратчайшем
пути } P(u,v)\mbox{ в графе } G\},</math>
называется '''И.ф.''' графа <math>G</math>.


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

Версия от 13:15, 28 октября 2009

Интервальная функция (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]