Матрица обходов

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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

Литература

[Харари]