Матрица обходов: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Матрица обходов''' (''Tournament matrix'') - матрица, определенная для орграфов; <math>(i,...)
 
Нет описания правки
Строка 1: Строка 1:
'''Матрица обходов''' (''Tournament matrix'') -  
'''Матрица обходов''' (''[[Tournament matrix]]'') -  
матрица, определенная для орграфов; <math>(i,j)</math>-й элемент ее равен длине
матрица, определенная для [[орграф|орграфов]]; <math>(i,j)</math>-й элемент ее равен длине
самого длинного пути из вершины <math>v_{i}</math> в вершину <math>v_{j}</math>
самого длинного [[путь|пути]] из [[вершина|вершины]] <math>v_{i}</math> в вершину <math>v_{j}</math>
если такой путь существует, и равен <math>\infty</math> в противном
если такой путь существует, и равен <math>\infty</math> в противном
случае.
случае.

Версия от 19:46, 23 ноября 2009

Матрица обходов (Tournament matrix) - матрица, определенная для орграфов; [math]\displaystyle{ (i,j) }[/math]-й элемент ее равен длине самого длинного пути из вершины [math]\displaystyle{ v_{i} }[/math] в вершину [math]\displaystyle{ v_{j} }[/math] если такой путь существует, и равен [math]\displaystyle{ \infty }[/math] в противном случае.

Эффективных алгоритмов для нахождения элементов матрицы обходов не существует.

Литература

[Харари]