Матрица Супника - Supnick matrix

А Матрица Супника или Массив супника - назван в честь Фреда Супника из Городской колледж Нью-Йорка, который ввел это понятие в 1957 г. - Массив Монжа который также является симметричная матрица.

Математическое определение

Матрица Супника - это квадрат Массив Монжа это симметрично относительно главная диагональ.

An п-от-п матрица является матрицей Супника, если для всех я, j, k, л так что если

{displaystyle 1leq i

и

{displaystyle 1leq j

тогда

{displaystyle a_ {ij} + a_ {kl} leq a_ {il} + a_ {kj},}

а также

{displaystyle a_ {ij} = a_ {ji}.,}

Логически эквивалентное определение дано Рудольфом и Вегингером, которые в 1995 году доказали, что

Матрица - это матрица Супника если только его можно записать как сумму матрицы сумм S и неотрицательная линейная комбинация блочных матриц LL-UR.

В матрица сумм определяется в терминах последовательности п действительные числа {α_я}:

{displaystyle S = [s_ {ij}] = [alpha _ {i} + alpha _ {j}] ;,}

и Матрица блоков LL-UR состоит из двух симметрично расположенных прямоугольников в нижнем левом и верхнем правом углах, для которых а_ij = 1, при этом все остальные элементы матрицы равны нулю.

Характеристики

Сложение двух матриц Супника вместе приведет к новой матрице Супника (Deineko and Woeginger 2006).

Умножение матрицы Супника на неотрицательный настоящий номер производит новую матрицу Supnick (Deineko and Woeginger 2006).

Если матрица расстояний в задача коммивояжера можно записать в виде матрицы Супника, этот конкретный случай проблемы допускает простое решение (даже если проблема, в общем, NP жесткий ).

Матрица Супника - Supnick matrix

Математическое определение

Характеристики

Рекомендации