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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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> в противном
случае.
случае.
Строка 8: Строка 8:
существует.
существует.
==Литература==
==Литература==
[Харари]
* Харари Ф. Теория графов. —  М.: Мир, 1973.

Текущая версия от 13:01, 4 мая 2011

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

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

Литература

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