Матрица Супника

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

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

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

Матрица n x размером n таких , является матрицей Супника, если для всех i , j , k , l что если

$1\leq i<k\leq n$ и $1\leq j<l\leq n$

затем

$a_{ij}+a_{kl}\leq a_{il}+a_{kj}\,$

а также

$a_{ij}=a_{ji}.\,$

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

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

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

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

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

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

Если сложить две матрицы Супника, получится новая матрица Супника (Дейнеко и Воегингер, 2006).

Умножение матрицы Супника на неотрицательное действительное число дает новую матрицу Супника (Дейнеко и Воегингер, 2006).

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

Ссылки

• Супник, Фред (июль 1957 г.). «Крайние гамильтоновы линии». Анналы математики . Вторая серия. 66 (1): 179–201. дои : 10.2307/1970124 . JSTOR   1970124 .
• Вегингер, Герхард Дж. (июнь 2003 г.). «Вычислительные задачи без вычислений» (PDF) . Ньюваршиф . 5 (4): 140–147.
• Дейнеко Владимир Георгиевич; Вегингер, Герхард Дж. (октябрь 2006 г.). «Некоторые проблемы, связанные с коммивояжёрами, дартсом и евромонетами» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 90 . EATCS : 43–52. ISSN   0252-9742 .