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

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

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

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

Литература

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