Массив Монжа

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение

[править | править код]

Говорят, что 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. — JSTOR 1970124.

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.