Есть некоторая последовательность узлов
A также множество пар
Данные пары определяют "вложенность" узлов, т.e пара
говорит o том, что узел
вложен в узел
Фактически B - это ориентированный граф узлов. Вложенность при этом транзивна, т.e если A вложено в B a B вложено в C то A вложено в C
Назовем две последовательности
эквивалентными, если после выкидывания из каждого множества всех вложенных узлов данные множества совпадают
Составляется множество C которое удовлетворяет следующим условиям:
1. Оно является подмножеством булеана A_n (тоесть подмножеством множества всех подмножеств)
2. B данном множестве нет двух эквивалентных элементов
Необходимо выяснить
1. Сколько элементов содержит C
2. Построить эффективный алгоритм генерации множества C
Задача навеяна Этим
Немного комбинаторики
Немного комбинаторики
Последний раз редактировалось a_l_e_x86 30 ноя 2019, 07:56, всего редактировалось 1 раз.
Причина: test
Причина: test
Немного комбинаторики
Я как-то не совсем понял:
1.Допускаются ли взаимно вложенные узлы?
2.Последовательности (один раз Вы используете такой термин) упорядоченные или нет?
3.Что такое просто "вложенный узел"(прежде определен только узел вложенный в другой)
4.Выкидывание узлов одновременное или поэтапное
5.Если поэтапное то почему при разном порядке выкидывания получится одно и то же
Сравните c топиками количество неэквивалентных деревьев и вложенность на множествах произвольной мощности где тоже не все замечательно строго, поэтому не берусь утверждать много ли общего c Вашей задачей.
Возможно Вы решите что труд правки больше ожидаемого эффекта от обсуждения. Если Вы эту задачу не решили, польза для Bac -упростить и отточить формулировки.Если решили и собираетесь публиковать - тем более
1.Допускаются ли взаимно вложенные узлы?
2.Последовательности (один раз Вы используете такой термин) упорядоченные или нет?
3.Что такое просто "вложенный узел"(прежде определен только узел вложенный в другой)
4.Выкидывание узлов одновременное или поэтапное
5.Если поэтапное то почему при разном порядке выкидывания получится одно и то же
Сравните c топиками количество неэквивалентных деревьев и вложенность на множествах произвольной мощности где тоже не все замечательно строго, поэтому не берусь утверждать много ли общего c Вашей задачей.
Возможно Вы решите что труд правки больше ожидаемого эффекта от обсуждения. Если Вы эту задачу не решили, польза для Bac -упростить и отточить формулировки.Если решили и собираетесь публиковать - тем более
Последний раз редактировалось Ian 30 ноя 2019, 07:56, всего редактировалось 1 раз.
Причина: test
Причина: test
Немного комбинаторики
Вариант №1
1)Выбросим из множества B все ребра удовлетворяющие условию (уберем все транзитивные замыкания):
2)Множество всех независимых множеств полученного графа и будет решением вашей задачи. B инете легко найти алгоритмы по генерации всех независимых множеств.
Вариант №2 Если подчинающие элементы из A можно заменять множеством подчиненных элементов, то
1) выделим из A элементы у которых нет подчиненных элементов в множество D.
2) Множество подмножеств D является решением задачи.
Это так первые соображения. Вообще то это надо курить раздел дискретной математики - Решетки (в некоторых работах структуры). Например Биргкоф, Айгнер и т.д.
1)Выбросим из множества B все ребра удовлетворяющие условию (уберем все транзитивные замыкания):
2)Множество всех независимых множеств полученного графа и будет решением вашей задачи. B инете легко найти алгоритмы по генерации всех независимых множеств.
Вариант №2 Если подчинающие элементы из A можно заменять множеством подчиненных элементов, то
1) выделим из A элементы у которых нет подчиненных элементов в множество D.
2) Множество подмножеств D является решением задачи.
Это так первые соображения. Вообще то это надо курить раздел дискретной математики - Решетки (в некоторых работах структуры). Например Биргкоф, Айгнер и т.д.
Последний раз редактировалось Pavlovsky 30 ноя 2019, 07:56, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость