Массив Монжа (Bgvvnf Bku'g)
В математике массивы Монжа или матрицы Монжа — это объекты, названные по имени открывателя, французского математика Гаспара Монжа.
Определение
[править | править код]Говорят, что m-на-n матрица является массивом Монжа, если для всех , таких, что
- и
Таким образом, для любых двух строк и любых двух столбцов массива Монжа (2 × 2 подматрицы) четыре элемента на точках пересечения имеют свойство, что сумма верхнего левого и нижнего правого элементов (по главной диагонали) меньше или равна сумме нижнего левого и верхнего элементов (по антидиагонали).
Эта матрица является массивом Монжа:
Например, возьмём пересечение строк 2 и 4 со столбцами 1 и 5. Четыре элемента на пересечениях образуют матрицу:
- 17 + 7 = 24
- 23 + 11 = 34
Сумма элементов по главной диагонали меньше суммы элементов по антидиагонали.
Свойства
[править | править код]- Вышеприведённое определение эквивалентно утверждению
- Матрица является массивом Монжа тогда и только тогда, когда для всех и .
- Любой подмассив, полученный отбором определённых строк и столбцов из начального массива Монжа, снова будет массивом Монжа.
- Любая линейная комбинация с неотрицательными коэффициентами массивов Монжа будет массивом Монжа.
- Есть одно интересное свойство массивов Монжа. Если обвести кружками минимальный элемент каждой строки (если несколько одинаковых, выбираем самый левый), вы увидите, что кружки перемещаются вниз и направо. То есть, если , то для всех . Симметрично, если выбрать (первый сверху) минимум в каждом столбце, кружки будут перемещаться направо и вниз. При выборе максимальных значений кружки перемещаются в противоположных направлениях — вверх направо и вниз налево.
- Любой массив Монжа полностью монотонен, что означает, что минимальные элементы строк идут в неубывающем порядке столбцов, и то же самое свойство верно для любого подмассива. Это свойство позволяет найти быстро минимумы в строках с помощью алгоритма SMAWK[англ.].
Связанные определения
[править | править код]- Было предложено понятие слабого массива Монжа — это квадратная n-на-n матрица, которая удовлетворяет свойству Монжа только для всех .
- Матрица Монжа — это просто другое название для субмодулярной функции от двух дискретных переменных. A является матрицей Монжа тогда и только тогда, когда A[i,j] является субмодулярной функцией от переменных i,j.
- n-на-n матрица A называется антиматрицей Монжа, если она удовлетворяет неравенству для всех и
(это неравенство называется антинеравенством Монжа)[3].
Приложения
[править | править код]- Квадратная матрица Монжа, которая также симметрична относительно главной диагонали, называется матрицей Сапника (по имени Фреда Сапника)[4]. Такие матрицы применяются для решения задачи коммивояжёра (а именно — эта задача легко решается, если матрицу расстояний можно представить как матрицу Сапника). Заметим, что любая линейная комбинация матриц Сапника снова является матрицей Сапника.
Литература
[править | править код]- ↑ Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspectives of Monge properties in optimization. — ELSEVIER, 1996. — Т. 70, вып. 2. — С. 95–96.
- ↑ Томас Кармен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы, построение и анализ. — Москва, Санкт-Петербург, Киев: Издательский дом «Вильямс», 2005. — С. 137. — ISBN 5-8459-0857-4.
- ↑ Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases // Mathematical Programming. — June 1998. — Т. 82, вып. 1. — С. 125-158.
- ↑ Fred Supnick. Extreme Hamiltonian Lines // Annals of Mathematics. Second Series. — July 1957. — Т. 66, вып. 1. — С. 179–201. — .
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.
Для улучшения этой статьи желательно:
|