pro.algorithms
Добрый вечер. Дан граф с вершинами (v1, v2, v3, v4).
Как они соединены, это не важно. Надо найти все возможные объединения этих вершин. То есть:
1) v1 + v2 = v12, то получается граф с вершинами (v12, v3, v4)
2) v2 + v3 = v23; v1 + v4 = v14. То получается граф (v23, v14)
3) v1 + v2 + v4 = v124. Получается граф с вершинами (v124, v3)
4) v1 + v2 + v3 + v4 = v1234, граф с одной вершиной
Попробовал решить с помощью инкриментирования числа в системе счисления 4. Но при большем количестве вершин, вычислительная сложность увеличивается и она больше чем 2^n.
По сути при 4 вершинах должно получиться 2^n (n = 4) возможных объединений.
Может существуют другие алгоритмы?
2 ответов
Не, насчёт названия понятия не имею, как-то само в голову пришло. Можем как-нибудь назвать, а-ля: последовательный набор подмножеств
Tuple
Cats
Автор вопроса
Не, насчёт названия понятия не имею, как-то само в...
Пиши статью по алгоритму))
Похожие вопросы
Обсуждают сегодня