Радужное соответствие

В математической дисциплине теории графов радужное паросочетание в графе с раскрашенными ребрами — это паросочетание , в котором все ребра имеют разные цвета.

Определение

с раскрашенными ребрами $Для графа G = (V, E)$ радужное сопоставление $M$ в $G$ представляет собой набор попарно несмежных ребер, то есть никакие два ребра не имеют общей вершины, так что все ребра в наборе имеют отчетливые цвета.

Максимальное радужное паросочетание — это радужное паросочетание, содержащее максимально возможное количество ребер.

История

Радужные сопоставления представляют особый интерес, поскольку они связаны с трансверсалами латинских квадратов .

Обозначим через $K n, n$ полный двудольный граф на $n + n$ вершинах. Каждая правильная $-$ реберная раскраска Kn $, n n n$ соответствует латинскому квадрату $порядка$ . Тогда радужное сопоставление соответствует трансверсальному латинскому квадрату, что означает выбор из $n$ позиций, по одной в каждой строке и каждом столбце, содержащих разные записи.

Эта связь между трансверсалями латинских квадратов и радужными паросочетаниями в $K n, n$ вызвала дополнительный интерес к изучению радужных паросочетаний в графах без треугольников . ^[1]

Существование, когда каждое ребро имеет один цвет

Раскраска ребер называется правильной , если каждое ребро имеет один цвет и каждые два ребра одного цвета не имеют общих вершин.

Правильная раскраска краев не гарантирует существования идеального соответствия радуги. Например, рассмотрим граф $K 2,2$ : полный двудольный граф с 2+2 вершинами. Предположим, что ребра $(x 1, y 1)$ и $(x 2, y 2)$ окрашены в зеленый цвет, а ребра $(x 1, y 2)$ и $(x 2, y 1)$ окрашены в синий цвет. Это правильная раскраска, но идеальных сочетаний только две, и каждая из них окрашена в один цвет. Возникает вопрос: когда гарантированно существует большое радужное совпадение?

Границы, зависящие только от количества вершин

Большая часть исследований по этому вопросу была опубликована с использованием терминологии латинских трансверсалей в латинских квадратах . В переводе на терминологию сопоставления радуги:

В 1967 году Х. Дж. Райзер предположил, что, когда $n$ нечетно , каждая правильная раскраска ребер $K n, n$ имеет радужное сопоставление размера $n$ . ^[2]
В 1975 году С. К. Штейн и Бруальди предположили, что, когда $n$ четно , каждая правильная раскраска ребер $K n, n$ имеет радужное сопоставление размера $n - 1$ . ^[3] (известно, что в этом случае не обязательно должно существовать радужное паросочетание размера $n$ ).

Более общая гипотеза Штейна состоит в том, что радужное паросочетание размера $n - 1$ существует не только для правильной раскраски ребер, но и для любой раскраски, в которой каждый цвет встречается ровно на $n$ ребрах. ^[2]

Были доказаны некоторые более слабые версии этих гипотез:

Каждая правильная раскраска ребер $K n, n$ имеет радужное паросочетание размера $2 n /3$ . ^[4]
Каждая правильная раскраска ребер $K n, n$ имеет радужное паросочетание размера ⁠ $n-{\sqrt {n}}.$ ⁠ ^[5]
Каждая правильная раскраска ребер $K n, n$ имеет радужное сопоставление размера $n - 11 log 2. 2 (н)$ . ^[6]
Каждая правильная раскраска ребер $K n, n$ имеет радужное паросочетание размера $n - O(log n /log log n)$ . ^[7]
Каждая правильная раскраска ребер $K n, n$ имеет радужное паросочетание размера $n - 1$ . ^[8] (Препринт)

Границы в зависимости от минимальной степени

Ван спросил, существует ли функция $f (d)$ такая, что каждый правильно раскрашенный граф $G$ с минимальной степенью $d$ и не менее $f (d)$ вершин должен иметь радужное сопоставление размера $d$ . ^[9] Очевидно, что необходимо как минимум $2 d$ вершины, но сколько их достаточно?

Димунш и др. ответил на этот вопрос утвердительно и показал, что для графа $G$ с правильно раскрашенными ребрами минимальной степени $d$ и порядка не ниже $f (d) = 98δ/23$ существует радужное паросочетание размера $d$ в $G$ . ^[10]
Позднее эта оценка была улучшена до $f (d) = 4 d - 3$ Андрасом Дьярфасом и Габором Н. Саркози. ^[11] Они также показывают, что любой граф с хотя бы $2 d$ вершинами имеет радужное паросочетание размером не менее $d - 2 d. 2/3$ . Это самая известная оценка на сегодняшний день.

Существование, когда одно и то же ребро может иметь разные цвета

Предположим, что каждое ребро может иметь несколько разных цветов, при этом каждые два ребра одного цвета не должны иметь общих вершин. Другими словами, каждый цвет является соответствующим . Сколько цветов необходимо, чтобы гарантировать существование радужного совпадения?

В полных двудольных графах

Диарея ^[12] изучал этот вопрос, используя терминологию латинских прямоугольников . Он доказал, что для любого $n \leq k$ в полном двудольном графе $K n, k$ любое семейство из $2 n - 1$ паросочетаний (= цветов) размера $n$ имеет идеальное радужное паросочетание (размера $n$ ). Он применил эту теорему к вопросам о групповых действиях и разностных множествах .

Дриско также показал, что $2 n - 1$ может потребоваться $паросочетания: рассмотрим семейство из 2 n - 2$ паросочетаний, из которых $n - 1$ — это ${ (x 1, y 1), (x 2, y 2), ..., (x n, y n)},$ а остальные $n - 1$ равны ${(x 1, y 2), (x 2, y 3), \dots, (x n, y 1) }.$ Тогда самое большое радужное паросочетание имеет размер $n - 1$ (например, возьмите по одному ребру из каждого из первых $n - 1$ паросочетаний).

Алон ^[13] показал, что из теоремы Дриско следует более старый результат ^[14] в аддитивной теории чисел .

В общем случае двудольные графы

Ахарони и Бергер ^[15] обобщила теорему Дриско на любой двудольный граф, а именно: любое семейство из $2 n - 1$ паросочетаний размера $n$ в двудольном графе имеет радужное паросочетание размера $n$ .

Ахарони, Котлар и Зив ^[16] показал, что экстремальный пример Дриско уникален в любом двудольном графе.

В общих чертах

В обычных графах $2 n - 1$ паросочетаний уже недостаточно. Когда $n$ четное, можно добавить к примеру Дриско сопоставление ${ (x 1, x 2), (y 1, y 2), (x 2, x 3), (y 2, y 3), \dots }$ и получить семейство из $2 n - 1$ паросочетаний без каких-либо радужных паросочетаний.

Ахарони, Бергер, Чудновский, Ховард и Сеймур ^[17] доказал, что в общем графе $3 n - 2$ всегда достаточно паросочетаний (= цветов). Неизвестно, является ли это точным: в настоящее время лучшая нижняя граница для четного $n$ равна $2 n$ , а для нечетного $n$ — $2 n - 1$ . ^[18]

Радужные дробные соответствия

Дробное паросочетание — это набор ребер с неотрицательным весом, присвоенным каждому ребру, такой, что сумма весов, прилегающих к каждой вершине, не превышает 1. Размер дробного паросочетания — это сумма весов всех ребер. Это обобщение сопоставления, и его можно использовать для обобщения как цветов, так и сопоставления радуги:

Вместо требования, чтобы каждый цвет был паросочетанием размера $n$ , требование ослабляется: каждый «цвет» может быть произвольным набором ребер, но он должен допускать дробное сопоставление размера не менее $n$ .
Вместо поиска радужного совпадения мы ищем дробное радужное сопоставление — дробное сопоставление, в котором каждое ребро с положительным весом имеет разный цвет.

Известно, что в двудольном графе максимальный размер дробного соответствия равен максимальному размеру совпадения. Поэтому теорема Ахарони и Бергера ^[15] эквивалентно следующему. Пусть $n$ — любое положительное целое число. Учитывая любое семейство из $2 n - 1$ дробных совпадений (= цветов) размера $n$ в двудольном графе, существует дробно-радужное совпадение размера $n$ .

Ахарони, Хольцман и Цзян распространяют эту теорему на произвольные графы следующим образом. Пусть $n$ — любое целое положительное или полуцелое число. Любое семейство из $2 n$ дробных совпадений (= цветов) размера не менее $n$ в произвольном графе имеет дробно-радужное совпадение размера $n$ . ^[18]^{: Thm.1.5} 2 $— это наименьшее возможное число для дробных паросочетаний в произвольных n$ графах: экстремальный случай строится с использованием цикла нечетной длины.

Частичное доказательство

В случае идеальных дробных паросочетаний обе приведенные выше теоремы можно вывести из красочной теоремы Каратеодори .

Для каждого ребра $e$ в $E$ пусть $1 e$ — вектор размера $| В |$ , где для каждой вершины $v$ в $V$ элемент $v$ в $1 e$ равен 1, если $e$ смежна с $v$ , и 0 в противном случае (поэтому каждый вектор $1 e$ имеет 2 единицы и $| V |$ -2 нуля). Каждое дробное паросочетание соответствует конической комбинации ребер, в которой каждый элемент не превышает 1. Коническая комбинация, в которой каждый элемент равен ровно 1, соответствует идеальному дробному паросочетанию. Другими словами, набор $ребер F$ допускает идеальное дробное паросочетание тогда и только тогда, когда $1 v$ (вектор из $| V |$ единиц) содержится в конической оболочке векторов $1 e$ for $e$ в $F$ .

Рассмотрим граф с $2n вершинами и предположим ,$ существует $2n что$ подмножеств ребер, каждое из которых допускает идеальное дробное паросочетание (размера $n$ ). Это означает, что вектор $1 v$ находится в конической оболочке каждого из этих $n$ подмножеств. По красочной теореме Каратеодори существует набор из $2 n$ ребер, по одному из каждого подмножества, в конической оболочке которых содержится $1 v$ . Это соответствует идеальному дробному совпадению радуги. Выражение $2 n$ представляет собой размерность векторов $1 e$ — каждый вектор имеет $2 n$ элементов.

Теперь предположим, что граф двудольный. существует ограничение $В двудольном графе на векторы 1 e$ : сумма элементов, соответствующих каждой части графа, должна быть равна 1. Следовательно, векторы $1 e$ живут в $(2 n - 1)$ -мерном пространстве. Следовательно, тот же аргумент, что и выше, справедлив, когда существует только $2 n - 1$ подмножества ребер.

Сопоставление радуги в гиперграфах

r -однородный гиперграф — это набор гиперребер, каждое из которых содержит ровно $r$ вершин (поэтому 2-однородный гиперграф — это просто граф без петель). Ахарони, Хольцман и Цзян распространяют свою теорему на такие гиперграфы следующим образом. Пусть $n$ — любое положительное рациональное число. Любое семейство $⌈ r \cdot n ⌉$ дробных сопоставлений (= цветов) размера не менее $n$ в $r$ -однородном гиперграфе имеет дробно-радужное сопоставление размера $n$ . ^[18]^{: Thm.1.6} ⌈ $n r \cdot n ⌉$ является наименьшим возможным, когда $является$ целым числом.

R -частичный гиперграф — это $r$ -однородный гиперграф, в котором вершины разбиты на $r$ непересекающиеся множества, и каждое гиперребро содержит ровно одну вершину каждого множества (поэтому 2-частичный гиперграф — это просто двудольный граф). Пусть $n$ — любое положительное целое число. Любое семейство $rn - r + 1$ дробных сопоставлений (= цветов) размера не менее $n$ в $r$ -частичном гиперграфе имеет дробно-радужное сопоставление размера $n$ . ^[18]^{: Thm.1.7} rn $является - r + 1$ является наименьшим из возможных: крайний случай – это когда $- 1 n = r степенью$ простого числа , а все цвета являются ребрами усеченной проективной плоскости порядка $n$ . Итак, каждый цвет имеет $n 2 = rn - r + 1$ ребер и дробное сопоставление размера $n$ , но любое дробное сопоставление такого размера требует всех $rn - r + 1$ ребер. ^[19]

Частичное доказательство

В случае идеальных дробных паросочетаний обе приведенные выше теоремы можно вывести из теоремы красочного каратеодори из предыдущего раздела. Для общего $r$ -однородного гиперграфа (допускающего идеальное паросочетание размера $n$ ) векторы $1 e$ живут в $(rn)$ -мерном пространстве. Для $r$ -однородного $r$ -частного гиперграфа $ограничения r$ -частности означают, что векторы $1 e$ живут в $(rn - r + 1)$ -мерном пространстве.

Примечания

Приведенные выше результаты справедливы только для радужных дробных паросочетаний. Напротив, случай радужных интегральных паросочетаний в $r$ -однородных гиперграфах изучен гораздо меньше. Количество требуемых паросочетаний для радужного сопоставления размера $n$ растет, по крайней мере, экспоненциально с увеличением $n$ .

Вычисление

Гэри и Джонсон показали, что вычисление максимального радужного сопоставления является NP-полным с раскрашенными ребрами даже для двудольных графов . ^[20]

Приложения

Радужные сопоставления применялись для решения задач упаковки . ^[21]

См. также

Ссылки

^ Уэст, DB (2009), Rainbow Matchings
^ Jump up to: Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
^ Штейн, Шерман (1 августа 1975 г.). «Трансверсали латинских квадратов и их обобщения» . Тихоокеанский математический журнал . 59 (2): 567–575. дои : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .
^ Коксма, Клаас К. (1 июля 1969 г.). «Нижняя оценка порядка частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . 7 (1): 94–95. дои : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .
^ Вулбрайт, Дэвид Э. (1 марта 1978 г.). «Латинский квадрат размера n × n имеет трансверсаль, содержащую как минимум n−n различных символов» . Журнал комбинаторной теории, серия А. 24 (2): 235–237. дои : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .
^ Хатами, Пуя; Шор, Питер В. (1 октября 2008 г.). «Нижняя оценка длины частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории, серия А. 115 (7): 1103–1113. дои : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .
^ Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (15.04.2022). «Новые границы гипотезы Райзера и связанных с ней проблем» . Труды Американского математического общества, серия B. 9 (8): 288–321. arXiv : 2005.00526 . дои : 10.1090/btran/92 . ISSN 2330-0000 .
^ Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [ math.CO ].
^ Ван, Гуанхуэй (2009), «Радужные сопоставления в графах с правильно раскрашенными ребрами» , Электронный журнал комбинаторики , 18 (1): 162
^ Димунш, Дженнифер; Феррара, Майкл; Ло, Аллан; Моффатт, Кейси; Пфендер, Флориан; Венгер, Пол С. (2012), «Радужные сопоставления размера δ(G) в графах с правильно раскрашенными краями» , Электронный журнал комбинаторики , 19 (2): 52, arXiv : 1108.2521 , doi : 10.37236/2443 , S2CID 119177198
^ Дьярфас, Андрас; Саркози, Габор Н. (2012). «Радужные паросочетания и частичные трансверсали латинских квадратов». arXiv : 1208.5670 [ CO math. СО ].
^ Дриско, Артур А. (1 ноября 1998 г.). «Трансверсали в рядно-латинских прямоугольниках» . Журнал комбинаторной теории, серия А. 84 (2): 181–195. дои : 10.1006/jcta.1998.2894 . ISSN 0097-3165 .
^ Алон, Нога (2011). «Разноцветные совпадения в гиперграфах». Московский журнал комбинаторики и теории чисел . 1 :3–10.
^ Флорес, Карлос; Ордас, Оскар (1 мая 1996 г.). «О теореме Эрдеша-Гинзбурга-Зива» . Дискретная математика . 152 (1–3): 321–324. дои : 10.1016/0012-365x(94)00328-g . ISSN 0012-365X .
^ Jump up to: Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли (25 сентября 2009 г.). «Радужные сопоставления в $r$-частных $r$-графах» . Электронный журнал комбинаторики . 16 (1). дои : 10.37236/208 . ISSN 1077-8926 .
^ Ахарони, Рон; Котлар, Дэни; Зив, Ран (01 января 2018 г.). «Единственность крайних случаев в теоремах Дриско и Эрдеша – Гинзбурга – Зива» . Европейский журнал комбинаторики . 67 : 222–229. дои : 10.1016/j.ejc.2017.08.008 . ISSN 0195-6698 . S2CID 38268762 .
^ Ахарони, Рон; Бергер, Эли; Чудновский, Мария; Ховард, Дэвид; Сеймур, Пол (01 июня 2019 г.). «Большие радужные паросочетания в общих графах». Европейский журнал комбинаторики . 79 : 222–227. arXiv : 1611.03648 . дои : 10.1016/j.ejc.2019.01.012 . ISSN 0195-6698 . S2CID 42126880 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Ахарони, Рон; Хольцман, Рон; Цзян, Цзилинь (29 октября 2019 г.). «Радужные дробные соответствия». Комбинаторика . 39 (6): 1191–1202. arXiv : 1805.09732 . дои : 10.1007/s00493-019-4019-y . ISSN 0209-9683 . S2CID 119173114 .
^ Фюреди, Золтан (1 мая 1989 г.). «Покрытие всего графа разбиениями» . Дискретная математика . 75 (1–3): 217–226. дои : 10.1016/0012-365x(89)90088-5 . ISSN 0012-365X .
^ Гэри, MR ; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: WH Freeman and Co., стр. x+338 . ISBN 0-7167-1045-5 . МР 0519066 .
^ Баннак, Макс; Берндт, Себастьян; Маак, Мартен; Мних, Матиас; Лассота, Александра; Рау, Малин; Скамбат, Мальте (06 июля 2020 г.). «Решение проблем с упаковкой небольшого количества мелких предметов с помощью сопоставлений Rainbow». arXiv : 2007.02660 [ cs.DS ].

[1] Уэст, DB (2009), Rainbow Matchings

[:02-2] Jump up to: Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .

[3] Штейн, Шерман (1 августа 1975 г.). «Трансверсали латинских квадратов и их обобщения» . Тихоокеанский математический журнал . 59 (2): 567–575. дои : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .

[4] Коксма, Клаас К. (1 июля 1969 г.). «Нижняя оценка порядка частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . 7 (1): 94–95. дои : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .

[5] Вулбрайт, Дэвид Э. (1 марта 1978 г.). «Латинский квадрат размера n × n имеет трансверсаль, содержащую как минимум n−n различных символов» . Журнал комбинаторной теории, серия А. 24 (2): 235–237. дои : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .

[6] Хатами, Пуя; Шор, Питер В. (1 октября 2008 г.). «Нижняя оценка длины частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории, серия А. 115 (7): 1103–1113. дои : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .

[7] Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (15.04.2022). «Новые границы гипотезы Райзера и связанных с ней проблем» . Труды Американского математического общества, серия B. 9 (8): 288–321. arXiv : 2005.00526 . дои : 10.1090/btran/92 . ISSN 2330-0000 .

[8] Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [ math.CO ].

[9] Ван, Гуанхуэй (2009), «Радужные сопоставления в графах с правильно раскрашенными ребрами» , Электронный журнал комбинаторики , 18 (1): 162

[10] Димунш, Дженнифер; Феррара, Майкл; Ло, Аллан; Моффатт, Кейси; Пфендер, Флориан; Венгер, Пол С. (2012), «Радужные сопоставления размера δ(G) в графах с правильно раскрашенными краями» , Электронный журнал комбинаторики , 19 (2): 52, arXiv : 1108.2521 , doi : 10.37236/2443 , S2CID 119177198

[11] Дьярфас, Андрас; Саркози, Габор Н. (2012). «Радужные паросочетания и частичные трансверсали латинских квадратов». arXiv : 1208.5670 [ CO math. СО ].

[12] Дриско, Артур А. (1 ноября 1998 г.). «Трансверсали в рядно-латинских прямоугольниках» . Журнал комбинаторной теории, серия А. 84 (2): 181–195. дои : 10.1006/jcta.1998.2894 . ISSN 0097-3165 .

[13] Алон, Нога (2011). «Разноцветные совпадения в гиперграфах». Московский журнал комбинаторики и теории чисел . 1 :3–10.

[14] Флорес, Карлос; Ордас, Оскар (1 мая 1996 г.). «О теореме Эрдеша-Гинзбурга-Зива» . Дискретная математика . 152 (1–3): 321–324. дои : 10.1016/0012-365x(94)00328-g . ISSN 0012-365X .

[:0-15] Jump up to: Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли (25 сентября 2009 г.). «Радужные сопоставления в $r$-частных $r$-графах» . Электронный журнал комбинаторики . 16 (1). дои : 10.37236/208 . ISSN 1077-8926 .

[16] Ахарони, Рон; Котлар, Дэни; Зив, Ран (01 января 2018 г.). «Единственность крайних случаев в теоремах Дриско и Эрдеша – Гинзбурга – Зива» . Европейский журнал комбинаторики . 67 : 222–229. дои : 10.1016/j.ejc.2017.08.008 . ISSN 0195-6698 . S2CID 38268762 .

[17] Ахарони, Рон; Бергер, Эли; Чудновский, Мария; Ховард, Дэвид; Сеймур, Пол (01 июня 2019 г.). «Большие радужные паросочетания в общих графах». Европейский журнал комбинаторики . 79 : 222–227. arXiv : 1611.03648 . дои : 10.1016/j.ejc.2019.01.012 . ISSN 0195-6698 . S2CID 42126880 .

[:1-18] Jump up to: Перейти обратно: ^а ^б ^с ^д Ахарони, Рон; Хольцман, Рон; Цзян, Цзилинь (29 октября 2019 г.). «Радужные дробные соответствия». Комбинаторика . 39 (6): 1191–1202. arXiv : 1805.09732 . дои : 10.1007/s00493-019-4019-y . ISSN 0209-9683 . S2CID 119173114 .

[19] Фюреди, Золтан (1 мая 1989 г.). «Покрытие всего графа разбиениями» . Дискретная математика . 75 (1–3): 217–226. дои : 10.1016/0012-365x(89)90088-5 . ISSN 0012-365X .

[20] Гэри, MR ; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: WH Freeman and Co., стр. x+338 . ISBN 0-7167-1045-5 . МР 0519066 .

[21] Баннак, Макс; Берндт, Себастьян; Маак, Мартен; Мних, Матиас; Лассота, Александра; Рау, Малин; Скамбат, Мальте (06 июля 2020 г.). «Решение проблем с упаковкой небольшого количества мелких предметов с помощью сопоставлений Rainbow». arXiv : 2007.02660 [ cs.DS ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]