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

Материал из WikiGrapp
Версия от 13:01, 4 мая 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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

Литература

  • Харари Ф. Теория графов. — М.: Мир, 1973.