Массив Монжа

В математике массивы Монжа или матрицы Монжа — это объекты, названные по имени открывателя, французского математика Гаспара Монжа.

ОпределениеПравить

Говорят, что m-на-n матрица является массивом Монжа, если для всех $i,j,k,\mathrm{\ell <!--\; \ell \; -->}$$\scriptstyle i,\,j,\,k,\,\ell$ , таких, что

$1\leq i<k\leq m$  и $1\leq j<\ell \leq n$ 

имеет место

$A[i,j]+A[k,\mathrm{\ell <!--\; \ell \; -->}]\le <!--\; \le \; -->A[i,\mathrm{\ell <!--\; \ell \; -->}]+A[k,j].$$A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].$ 

Таким образом, для любых двух строк и любых двух столбцов массива Монжа (2 × 2 подматрицы) четыре элемента на точках пересечения имеют свойство, что сумма верхнего левого и нижнего правого элементов (по главной диагонали) меньше или равна сумме нижнего левого и верхнего элементов (по антидиагонали).

Эта матрица является массивом Монжа:

${\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}$ 

Например, возьмём пересечение строк 2 и 4 со столбцами 1 и 5. Четыре элемента на пересечениях образуют матрицу:

${\begin{bmatrix}17&23\\11&7\end{bmatrix}}$ 

17 + 7 = 24

23 + 11 = 34

Сумма элементов по главной диагонали меньше суммы элементов по антидиагонали.

СвойстваПравить

• Вышеприведённое определение эквивалентно утверждению

Матрица является массивом Монжа тогда и только тогда, когда $A[i,j]+A[i+1,j+1]\le <!--\; \le \; -->A[i,j+1]+A[i+1,j]$$A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]$  для всех $1\leq i<m$  и $1\leq j<n$ .

• Любой подмассив, полученный отбором определённых строк и столбцов из начального массива Монжа, снова будет массивом Монжа.

• Любая линейная комбинация с неотрицательными коэффициентами массивов Монжа будет массивом Монжа.

• Есть одно интересное свойство массивов Монжа. Если обвести кружками минимальный элемент каждой строки (если несколько одинаковых, выбираем самый левый), вы увидите, что кружки перемещаются вниз и направо. То есть, если $f(x)=\arg <!--\; \; -->\underset{i\in <!--\; \in \; -->\{1,\dots <!--\; \dots \; -->,m\}}{min}A[x,i]$$f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]$ , то $f(j)\le <!--\; \le \; -->f(j+1)$$f(j)\leq f(j+1)$  для всех $1\leq j<n$ . Симметрично, если выбрать (первый сверху) минимум в каждом столбце, кружки будут перемещаться направо и вниз. При выборе максимальных значений кружки перемещаются в противоположных направлениях — вверх направо и вниз налево.
• Любой массив Монжа полностью монотонен, что означает, что минимальные элементы строк идут в неубывающем порядке столбцов, и то же самое свойство верно для любого подмассива. Это свойство позволяет найти быстро минимумы в строках с помощью алгоритма SMAWK^[en].

Связанные определенияПравить

• Было предложено понятие слабого массива Монжа — это квадратная n-на-n матрица, которая удовлетворяет свойству Монжа $A[i,i]+A[r,s]\le <!--\; \le \; -->A[i,s]+A[r,i]$$A[i,i]+A[r,s]\leq A[i,s]+A[r,i]$  только для всех $1\leq i<r,s\leq n$ .
• Матрица Монжа — это просто другое название для субмодулярной функции от двух дискретных переменных. A является матрицей Монжа тогда и только тогда, когда A[i,j] является субмодулярной функцией от переменных  i,j.
• n-на-n матрица A называется антиматрицей Монжа, если она удовлетворяет неравенству $A[i,j]+A[r,s]\ge <!--\; \ge \; -->A[i,s]+A[r,j]$$A[i,j]+A[r,s]\geq A[i,s]+A[r,j]$  для всех $1\leq i<r\leq n$  и $1\leq j<s\leq n$ 

(это неравенство называется антинеравенством Монжа).

ПриложенияПравить

• Квадратная матрица Монжа, которая также симметрична относительно главной диагонали, называется матрицей Сапника (по имени Фреда Сапника). Такие матрицы применяются для решения задачи коммивояжёра (а именно — эта задача легко решается, если матрицу расстояний можно представить как матрицу Сапника). Заметим, что любая линейная комбинация матриц Сапника снова является матрицей Сапника.

ЛитератураПравить

5.E Girlich,MKovalev,AZaporozhets Subcones of submodular functions ( subclasses of Monge matrices)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p

• Vladimir G. Deineko, Gerhard J. Woeginger. Some problems around travelling salesmen, dart boards, and euro-coins // Bulletin of the European Association for Theoretical Computer Science. — EATCS, October 2006. — Т. 90. — С. 43–52. — ISSN 0252-9742.