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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Массив Монжа»  – Новости  · газеты  · книги  · ученый  · JSTOR (Сентябрь 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

An м-к-п матрица считается Массив Монжа если для всех ${ displaystyle scriptstyle i, , j, , k, , ell}$ такой, что

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

можно получить^[1]

${ 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 <п}$.

• Любой подмассив, созданный путем выбора определенных строк и столбцов из исходного массива Монжа, сам будет массивом Монжа.
• Любой линейная комбинация с неотрицательными коэффициентами массивов Монжа сам является массивом Монжа.
• Одно интересное свойство массивов Монжа состоит в том, что если вы отметите кружком крайний левый минимум каждой строки, вы обнаружите, что ваши кружки идут вниз вправо; то есть, если ${ 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.
• Матрица Монжа - это просто еще одно название для субмодульная функция двух дискретных переменных. Именно так, А является матрицей Монжа тогда и только тогда, когда А[я,j] - субмодулярная функция переменныхя,j.

Приложения

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

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

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