Массив Монжа

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

Определение

Говорят, что m-на-n матрица является массивом Монжа, если для всех , таких, что

и

имеет место[1][2]

Таким образом, для любых двух строк и любых двух столбцов массива Монжа (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]. Такие матрицы применяются для решения задачи коммивояжёра (а именно — эта задача легко решается, если матрицу расстояний можно представить как матрицу Сапника). Заметим, что любая линейная комбинация матриц Сапника снова является матрицей Сапника.

Литература

  1. Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspectives of Monge properties in optimization. — ELSEVIER, 1996. Т. 70, вып. 2. С. 95–96.
  2. Томас Кармен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы, построение и анализ. — Москва, Санкт-Петербург, Киев: Издательский дом «Вильямс», 2005. — С. 137. — ISBN 5-8459-0857-4.
  3. 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.
  4. 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.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.