В математической дисциплине теории графов трехмерное паросочетание является обобщением двудольного паросочетания (также известного как двумерное паросочетание) на трехдольные гиперграфы , которые состоят из гиперребер, каждое из которых содержит 3 вершины (вместо ребер, содержащих 2 вершины в обычном графе).
3-мерное сопоставление, часто сокращенно 3DM , также является названием известной вычислительной задачи: нахождения наибольшего 3-мерного сопоставления в заданном гиперграфе. 3DM — одна из первых задач, для которых было доказано, что они являются NP-трудными .
Пусть X , Y и Z — конечные множества, а T — подмножество X × Y × Z. То есть T состоит из троек ( x , y , z ) таких, что x ∈ X , y ∈ Y и z ∈ Z. Теперь M ⊆ T является 3 -мерным паросочетанием, если выполняется следующее: для любых двух различных троек ( x1 , y1 , z1 ) ∈ M и ( x2 , y2 , z2 ) ∈ M имеем x1 ≠ x2 , y1 ≠ y2 и z1 ≠ z2 .
Рисунок справа иллюстрирует трехмерные соответствия. Набор X отмечен красными точками, Y отмечен синими точками, а Z отмечен зелеными точками. Рисунок (a) показывает набор T (серые области). Рисунок (b) показывает трехмерное соответствие M с | M | = 2, а рисунок (c) показывает трехмерное соответствие M с | M | = 3.
Паросочетание M, показанное на рисунке (c), является максимальным 3-мерным паросочетанием , т. е. оно максимизирует | M |. Паросочетания, показанные на рисунках (b)–(c), являются максимальными 3-мерными паросочетаниями , т. е . их нельзя расширить, добавив больше элементов из T.
Вот пример интерактивной визуализации на JavaScript
Двумерное соответствие можно определить совершенно аналогичным образом. Пусть X и Y — конечные множества, а T — подмножество X × Y . Теперь M ⊆ T является двумерным соответствием, если выполняется следующее: для любых двух различных пар ( x 1 , y 1 ) ∈ M и ( x 2 , y 2 ) ∈ M имеем x 1 ≠ x 2 и y 1 ≠ y 2 .
В случае двумерного сопоставления множество T можно интерпретировать как множество ребер в двудольном графе G = ( X , Y , T ); каждое ребро в T соединяет вершину в X с вершиной в Y. Двумерное сопоставление тогда является сопоставлением в графе G , то есть множеством попарно несмежных ребер.
Следовательно, 3-мерные паросочетания можно интерпретировать как обобщение паросочетаний на гиперграфы: множества X , Y и Z содержат вершины, каждый элемент T является гиперребром, а множество M состоит из попарно несмежных ребер (ребер, не имеющих общей вершины). В случае 2-мерного паросочетания имеем Y = Z.
Трехмерное паросочетание является частным случаем упаковки множеств : мы можем интерпретировать каждый элемент ( x , y , z ) множества T как подмножество { x , y , z } множества X ∪ Y ∪ Z ; тогда трехмерное паросочетание M состоит из попарно непересекающихся подмножеств.
В теории сложности вычислений трехмерное сопоставление (3DM) — это название следующей задачи принятия решения : для заданного множества T и целого числа k решить, существует ли трехмерное сопоставление M ⊆ T с | M | ≥ k .
Известно, что эта задача принятия решений является NP-полной ; это одна из 21 NP-полной задачи Карпа . [1] Она является NP-полной даже в частном случае, когда k = | X | = | Y | = | Z |, и когда каждый элемент содержится не более чем в 3 множествах, т. е. когда мы хотим получить идеальное паросочетание в 3-регулярном гиперграфе. [1] [2] [3] В этом случае 3-мерное паросочетание является не только упаковкой множеств, но и точным покрытием : множество M покрывает каждый элемент X , Y и Z ровно один раз. [4] Доказательство заключается в сведении из 3SAT . Учитывая экземпляр 3SAT, мы строим экземпляр 3DM следующим образом: [2] [5]
Существуют полиномиальные алгоритмы для решения 3DM в плотных гиперграфах. [6] [7]
Максимальное 3-мерное соответствие — это наибольшее 3-мерное соответствие. В теории сложности вычислений это также название следующей задачи оптимизации : для заданного множества T найти 3-мерное соответствие M ⊆ T , которое максимизирует |M| .
Поскольку описанная выше задача принятия решения является NP-полной, эта задача оптимизации является NP-трудной , и, следовательно, кажется, что не существует полиномиального алгоритма для поиска максимального 3-мерного паросочетания. Однако существуют эффективные полиномиальные алгоритмы для поиска максимального двудольного паросочетания (максимального 2-мерного паросочетания), например, алгоритм Хопкрофта–Карпа .
Существует очень простой алгоритм 3-приближения с полиномиальным временем для 3-мерного сопоставления: найти любое максимальное 3-мерное сопоставление. [8] Так же, как максимальное сопоставление находится в пределах множителя 2 от максимального сопоставления, [9] максимальное 3-мерное сопоставление находится в пределах множителя 3 от максимального 3-мерного сопоставления.
Для любой константы ε > 0 существует полиномиальный алгоритм аппроксимации (4/3 + ε) для трехмерного сопоставления. [10]
Однако достижение лучших коэффициентов аппроксимации, вероятно, затруднительно: задача является APX-полной , то есть ее трудно аппроксимировать с точностью до некоторой константы. [11] [12] [8]
NP-трудно достичь фактора аппроксимации 95/94 для максимального 3-мерного соответствия и фактора аппроксимации 48/47 для максимального 4-мерного соответствия. Трудность сохраняется даже при ограничении экземплярами с ровно двумя вхождениями каждого элемента. [13]
Существуют различные алгоритмы для трехмерного сопоставления в модели массовых параллельных вычислений. [14]