Задача о трехмерном сочетании
Мы уже знаем, как решать задачу двудольного паросочетания за полиномиаль- ное время. Однако ситуация заметно усложняется при переходе от упорядоченных пар к упорядоченным триплетам. Рассмотрим следующую задачу о трехмерном сочетании:
Для заданных непересекающихся множеств 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.
Еще по теме Задача о трехмерном сочетании:
- Трехмерные чакры:
- некоторые сочетания различных акцентуаций у одного человека.
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Структура характера и жизненная задача
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
- Основные задачи МПП.
- Задачи и упражнения