<<
>>

Задача о трехмерном сочетании

Начнем с обсуждения задачи о трехмерном сочетании, которая может считаться усложненной версией задачи о двудольном паросочетании, которая разбиралась ранее. Задача о двудольном паросочетании может рассматриваться следующим образом: даны два множества X и Y, каждое из которых имеет размер n, и множе- ство Р пар изX X Y.
Вопрос: существует ли в Р такое множество из n пар, в котором каждый элемент в X U Y содержится ровно в одной паре? Связь с задачей дву- дольного паросочетания очевидна: множество P таких пар просто соответствует ребрам двудольного графа.

Мы уже знаем, как решать задачу двудольного паросочетания за полиномиаль- ное время. Однако ситуация заметно усложняется при переходе от упорядоченных пар к упорядоченным триплетам. Рассмотрим следующую задачу о трехмерном сочетании:

Для заданных непересекающихся множеств X, Y и Z, каждое из которых имеет размер n, и заданного множества T !Ξ X χ Y χ Z упорядоченных триплетов суще- ствует ли в T такое множество из n триплетов, что каждый элемент X U Y U Z содержится ровно в одном из этих триплетов?

Такой набор триплетов называется идеальным трехмерным сочетанием. Интересный аспект задачи о трехмерном сочетании, кроме ее связи с двудоль- ным паросочетанием, заключается в том, что она одновременно образует част- ные случаи как задачи покрытия множества, так и задачи упаковки множества: фактически мы ищем покрытие универсального множества X U Y U Z набором непересекающихся множеств. Конкретнее, задача о трехмерном сочетании явля- ется частным случаем задачи покрытия множества, поскольку мы ищем покрытие универсального множества U = XU YU Z с использованием не более n множеств из заданного набора (триплетов). Аналогичным образом задача о трехмерном со- четании является частным случаем задачи упаковки множества, так как мы ищем n непересекающихся подмножеств универсального множества U = X U Y U Z.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача о трехмерном сочетании:

  1. Трехмерные чакры:
  2. некоторые сочетания различных акцентуаций у одного человека.
  3. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  4. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  5. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  6. ЗАДАЧА
  7. ЗАДАЧА: РЕШЕНИЕ
  8. Основные задачи.
  9. в) Задачи
  10. в) Задачи
  11. ПСИХОАНАЛИЗ: ЗАДАЧА
  12. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  13. Структура характера и жизненная задача
  14. Основные задачи
  15. Правило решаемой психологической задачи.
  16. Задачи и упражнения
  17. Терапевтическая задача
  18. 3. Задачи и функции социологии
  19. Основные задачи МПП.
  20. Задачи и упражнения