В математике массивы Монжа или матрицы Монжа — это объекты, названные по имени открывателя, французского математика Гаспара Монжа.
Определение Говорят, что m-на-n матрица является массивом Монжа, если для всех , таких, что
и
имеет место
Таким образом, для любых двух строк и любых двух столбцов массива Монжа (2 × 2 подматрицы) четыре элемента на точках пересечения имеют свойство, что сумма верхнего левого и нижнего правого элементов (по главной диагонали) меньше или равна сумме нижнего левого и верхнего правого элементов (по антидиагонали).
Эта матрица является массивом Монжа:
Например, возьмём пересечение строк 2 и 4 со столбцами 1 и 5. Четыре элемента на пересечениях образуют матрицу:
17 + 7 = 24 23 + 11 = 34
Сумма элементов по главной диагонали меньше суммы элементов по антидиагонали.
Свойства Вышеприведённое определение эквивалентно утверждению Матрица является массивом Монжа тогда и только тогда, когда для всех и .
Любой подмассив, полученный отбором определённых строк и столбцов из начального массива Монжа, снова будет массивом Монжа.
Любая линейная комбинация с неотрицательными коэффициентами массивов Монжа будет массивом Монжа.
Есть одно интересное свойство массивов Монжа. Если обвести кружками минимальный элемент каждой строки (если несколько одинаковых, выбираем самый левый), вы увидите, что кружки перемещаются вниз и направо. То есть, если , то для всех . Симметрично, если выбрать (первый сверху) минимум в каждом столбце, кружки будут перемещаться направо и вниз. При выборе максимальных значений кружки перемещаются в противоположных направлениях — вверх направо и вниз налево. Любой массив Монжа полностью монотонен, что означает, что минимальные элементы строк идут в неубывающем порядке столбцов, и то же самое свойство верно для любого подмассива. Это свойство позволяет найти быстро минимумы в строках с помощью .
Связанные определения Было предложено понятие слабого массива Монжа — это квадратная n-на-n матрица, которая удовлетворяет свойству Монжа только для всех . Матрица Монжа — это просто другое название для субмодулярной функции от двух дискретных переменных. A является матрицей Монжа тогда и только тогда, когда A[i,j] является субмодулярной функцией от переменных i,j. n-на-n матрица A называется антиматрицей Монжа, если она удовлетворяет неравенству для всех и (это неравенство называется антинеравенством Монжа).
Приложения Квадратная матрица Монжа, которая также симметрична относительно главной диагонали, называется матрицей Сапника (по имени Фреда Сапника). Такие матрицы применяются для решения задачи коммивояжёра (а именно — эта задача легко решается, если матрицу расстояний можно представить как матрицу Сапника). Заметим, что любая линейная комбинация матриц Сапника снова является матрицей Сапника.
Литература 5.E Girlich,MKovalev,AZaporozhets Subcones of submodular functions ( subclasses of Monge matrices)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p
Категория:Исследование операций Категория:Теоретическая информатика