Массив Монжа - Monge array

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

An M матрицы с размерностью п матрица называется быть массивом Монжа , если для всех таким образом, что ${\ displaystyle \ scriptstyle i, \, j, \, k, \, \ ell}$

${\ Displaystyle 1 \ Leq я <к \ Leq м {\ текст {и}} 1 \ Leq J <\ ell \ Leq n}$

можно получить

${\ displaystyle A [i, j] + A [k, \ ell] \ leq A [i, \ ell] + A [k, j]. \,}$

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

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

${\ displaystyle {\ 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. Четыре элемента:

${\ displaystyle {\ begin {bmatrix} 17 и 23 \\ 11 и 7 \ end {bmatrix}}}$

17 + 7 = 24

23 + 11 = 34

Сумма левого верхнего и правого нижнего элементов меньше или равна сумме левого нижнего и правого верхнего элементов.

Свойства

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

Матрица является массивом Монжа тогда и только тогда, когда для всех и .${\ Displaystyle A [я, j] + A [я + 1, j + 1] \ Leq A [я, j + 1] + A [я + 1, j]}$${\ Displaystyle 1 \ Leq я <м}$${\ Displaystyle 1 \ Leq J <п}$

• Любой подмассив, созданный путем выбора определенных строк и столбцов из исходного массива Monge, сам будет массивом Monge.
• Любая линейная комбинация с неотрицательными коэффициентами массивов Монжа сама по себе является массивом Монжа.
• Одно интересное свойство массивов Monge состоит в том, что если вы пометите кружком крайний левый минимум каждой строки, вы обнаружите, что ваши круги движутся вниз вправо; то есть если , то для всех . Симметрично, если вы отметите самый верхний минимум каждого столбца, ваши круги будут двигаться вправо и вниз. Максимумы строки и столбца идут в противоположном направлении: вверх вправо и вниз влево.${\ Displaystyle е (х) = \ арг \ мин _ {я \ ин \ {1, \ ldots, м \}} А [х, я]}$${\ Displaystyle F (J) \ Leq F (J + 1)}$${\ Displaystyle 1 \ Leq J <п}$
• Было предложено понятие слабых массивов Монжа ; слабый массив Монжа представляет собой квадрат н матрицы с размерностью п матрица , которая удовлетворяет свойство Monge только для всех .${\ Displaystyle А [я, я] + А [г, s] \ Leq А [я, s] + А [г, я]}$${\ Displaystyle 1 \ Leq я <г, s \ Leq п}$
• Каждый массив Monge является полностью монотонным, что означает, что минимумы его строк встречаются в неубывающей последовательности столбцов, и что одно и то же свойство истинно для каждого подмассива. Это свойство позволяет быстро находить минимумы строки с помощью алгоритма SMAWK .
• Матрица Монжа - это просто другое название субмодульной функции двух дискретных переменных. Точно, A является матрицей Монжа тогда и только тогда, когда A [ i , j ] является субмодулярной функцией переменных  i , j .

Приложения

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

Ссылки

• Дейнеко, Владимир Г .; Вегингер, Герхард Дж. (Октябрь 2006 г.). «Некоторые проблемы с коммивояжером, досками для дартса и евро-монетами» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . EATCS . 90 : 43–52. ISSN  0252-9742 .