|
Необходимо решить четыре задачи на данную тематику, перечитал кучу книжек по теме, в том числе и Гери и Джонсона. Честно говоря, в голову ничего не приходит.
Помогите, пожалуйста, с решением.
Собственно сами задачи:
1)Доказать, что данная задача np-полная, путем сводимости ее к задаче 3-ВЫП. Задача: разбиение на гамильтоновы подграфы. Условие: задан ориентированный граф G = (V,A). Вопрос: можно ли разбить вершины графа G на непересекающиеся подмножества V1, V2, ..., Vk такие, что каждое Vi содержит по крайней мере 3 вершины, а все индуцируемые ими подграфы графа G содержали бы гамильтонов циклы?
2)Доказать, что данная задача np-полная, путем сводимости ее к задаче ТП-3. Задача: Разложение подстановки. Условие: задана подстановка b множества {1,2,...,N} и последовательность S1, S2,...,Sm подмножеств множества {1,2,...,N}. Вопрос: можно ли представить подстановку b в виде композиции подстановок b = b1,b2,...,bm, где для каждого i, 1 <= i <= m, подстановка bi оставляет неподвижными элементы множества {1,2,...,N}\Si ?
3)Доказать, что данная задача np-полная, путем сводимости ее к задаче ТП-3. Задача: оптимальный коммуникационный остов. (условие приводить не буду, проще всего его посмотреть в Гэри и Джонсоне)
4)Доказать, что данная задача np-полная, путем сводимости ее к задаче ВП. Задача: кратчайшая общая надпоследовательность. Условие: заданы конечный алфавит E, конечное множество R слов в алфавите E* и положительное целое число k. Вопрос: существует ли такое слово w из E*, что |w| <= k и каждое слово x из R есть подпоследовательность w, т.е. w = w0x1w1x2w2...xkwk, где wi из E*, а x = x1,x2,..,xk ?
|
