Macierz Supnicka

Macierz Supnicka lub tablica Supnicka – nazwana na cześć Freda Supnicka z City College of New York , który wprowadził to pojęcie w 1957 r. – to tablica Monge’a , która jest również macierzą symetryczną .

Definicja matematyczna

Macierz Supnicka to kwadratowa tablica Monge'a , która jest symetryczna wokół głównej przekątnej .

Macierz n -na- n jest macierzą Supnicka, jeśli dla wszystkich i , j , k , l taka, że jeśli

{\ Displaystyle 1 \ równoważnik i <k \ równoważnik n}

i

{\ Displaystyle 1 \ równoważnik j <l \ równoważnik n}

Następnie

równoważnik a_ {il} + a_ {kj} \,}

i również

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

Logicznie równoważną definicję podają Rudolf i Woeginger, którzy udowodnili to w 1995 roku

Macierz jest macierzą Supnicka, jeśli można ją zapisać jako sumę macierzy sumarycznej S i nieujemnej liniowej kombinacji macierzy blokowych LL-UR.

Macierz sum jest zdefiniowana za pomocą ciągu n liczb rzeczywistych {α _i }:

{\ Displaystyle S = [s_ {ij}] = [\ alfa _ {i} + \ alfa _ {j}]; \,}

a macierz blokowa LL-UR składa się z dwóch symetrycznie rozmieszczonych prostokątów w lewym dolnym i prawym górnym rogu, dla których a _ij = 1, a wszystkie pozostałe elementy macierzy są równe zeru.

Nieruchomości

Dodanie dwóch macierzy Supnicka razem da w rezultacie nową macierz Supnicka (Deineko i Woeginger 2006).

Mnożenie macierzy Supnicka przez nieujemną liczbę rzeczywistą daje nową macierz Supnicka (Deineko i Woeginger 2006).

Jeśli macierz odległości w problemie komiwojażera można zapisać jako macierz Supnicka, to ten konkretny przypadek problemu dopuszcza łatwe rozwiązanie (mimo że ogólnie problem jest NP trudny ).

Supnick, Fred (lipiec 1957). „Ekstremalne linie Hamiltona”. Roczniki matematyki . Druga seria. 66 (1): 179–201. doi : 10.2307/1970124 . JSTOR 1970124 .
Woeginger, Gerhard J. (czerwiec 2003). „Problemy obliczeniowe bez obliczeń” (PDF) . Nieuwarszyf . 5 (4): 140–147.
Deineko, Władimir G.; Woeginger, Gerhard J. (październik 2006). „Pewne problemy związane z podróżującymi sprzedawcami, tarczami do rzutek i monetami euro” (PDF) . Biuletyn Europejskiego Stowarzyszenia Informatyki Teoretycznej . EATCS . 90 : 43–52. ISSN 0252-9742 .