Кратки решения на задачите от поправителния изпит
Здравейте,
Това е скелетът на примерни решения на задачите (самите решения се очаква да са по-подробни).
Вариант 1.
Зад 1. Щом във всеки връх влиза ребро, графът не може да е dag. Алгоритъмът просто връща НЕ. Сложност по време: O(1). За втората подзадача, първо забелязваме, че задължително има едно ребро, чието премахване води до dag. Нека u е връх, от който има път до всеки друг връх. Нека e= (w,u) е ориентираното ребро, влизащо в u. Премахването на (w,u) води до dag. Ето д-во на това: нека H = G - e. Да си представим DFS(H, u). Щом има път от u до всеки друг връх, то едно единствено пускане на DFS открива целия граф. Твърди се, че пускането на DFS няма да класифицира ребра като обратни. Да допуснем обратното: DFS открива обратно ребро (x,y). Но y не може да е u, понеже махнахме единственото влизащо в u ребро. Ако допуснем, че y не е u, пак получаваме противоречие: тогава в x влизат поне две ребра, едното от y (обратно ребро) и другото (което не е обратно ребро) от родителя на x, който лежи на някой път от u до x. И така, обратни ребра няма, следователно няма и цикли, следователно H е dag, следователно има единствено ребро e, чието махане прави от G dag, следователно търсеното м-во E' се състои от едно единствено ребро. Как да намерим такова ребро в G? Може да го намерим в линейно време, т.е. в O(n+m) така. Започваме от произволен връх и посещаваме неговия уникален предшественик (за да можем да изчисляваме предшественика във време O(1), може първо да си построим транспонирания граф, това ще добави един суманд O(n+m) в израза за сложността и тя ще остане O(n+m) ), маркирайки върховете като посетени, докато не достигнем до връх z, който вече е бил посетен. Твърдим, че единственото ребро e', влизащо в z, е такова, че G-e' е dag. Защо? Очевидно z е връх от някакъв цикъл c. Всеки връх в c има влизащо ребро, което ребро е част от c, но, от др. страна, това е единственото влизащо ребро в този връх в контекста на целия граф G. Следователно, единствените върхове в графа, от които има път до z, са върховете в c. Знаем, че от u има път до всеки друг връх. Тогава u е връх от цикъла. Но има път от u до z. От транзитивността на релацията "има път до" следва, че щом има път от z до u (току-що видяхме, че е така) и от u до всеки друг (по условие) следва, че има път от z до всеки друг връх. Тогава прилагаме разсъждения като тези преди малко.
Зад. 2: ползваме динамично програмиране. Нека sum(i) е максималният брой точки, който можем да получим за въпроси q[i], ..., q[n]. Очевидно ни трябва q[1]. Очевидно sum(n) = q[n]. За i < n, sum(i) е по-доброто, т.е., по-голямото (или, по-прецизно казано, не по-малкото) от това, което може да получим, ако не ползваме q[i] (това количество е q[i+1]), и това, което можем да получим, ползвайки q[i]---което ни дава p[i] точки---и изтървавайки по този начин следващите t[i] въпроса. Ако изтървем въпроси q[i+1] ... q[i + t[i]], то следващият въпрос, от който можем да вземем нещо, е q[i + t[i] + 1]. Оттук веднага следният рек. алг. ни решава задачата
sum[n+1] = 0 // това е в случай, че се налага да прескочим n-ия въпрос
sum[n] = q[n]
for i from n-1 downto 1
sum[i] = max{ p[i] + sum[i + t[i] + 1], p[i+1] }
return sum[1]
Коректността е очевидно, сложността очевидно е линейна.
Зад 3: Твърдението не е вярно. Може f2 и f3 да са асимптотично несравними, но f1 да е толкова бързо растяща, че да "маскира" това. Например, f2 = n, f3 = n^2 върху четните и f3 = 1 върху нечетните (f2 и f3 са несравними асимпт.), но f1(n) = 2^n.
Зад. 4: Задачата съдържа в себе си задачата INDEPENDENT SET като частен случай. В нашата задача се иска, при дадено p, да се намери подмножество от >= p съставки, които имат минимална сума от несъвместимости, като несъвместимостите са реални числа от [0,1]. Частен случай на тази задача е този, в който несъвместимостите са булеви -- 0 или 1. В IS се иска да се отговори с ДА или НЕ дали изобщо има подмножество от поне p неща, които имат нулева сумарна несъвместимост.
Вариант 2:
Зад 1: Ако графът е dag, то или съществува такава верига, или изобщо не съществува (трябва да съдържа поне два върха, за да е верига по дефиницията), или съществува макс. верига, като в нея има най-много n върха. Ако графът не е dag, то в него има цикъл и макс. верига е безкрайна в смисъл, че за всяко число има верига с такава дълж. Знаем как с модифициран DFS можем да намираме дали граф е dag в линейно време. Ако не е dag, то output(\infinity), в противен случай намираме най-дълъг път в dag---знаем как става това, можем да ползваме вече направеното топо-сортиране, в линейно време---и връщаме дължината му, ако е повече от 1, или връщаме, че изобщо вериги няма, ако дълж. му е 1.
Зад 2: Задачата е добре известната 3SUM. Сортираме в O(n^2) и после опитваме за i \in {1 .. n-2} дали A[i] може да е най-малък елемент от тройка със сума нула така: правим j <-- i+1 и k <-- n, после s <-- A[i] + A[j] + A[k], ако s = 0 връщаме ДА, в противен случай, ако има елементи между A[j] и A[k], ако sum < 0 то k--, else j++; в противен случай (няма такива) i ++.
По индукция става тривиално. Трябва да док. поотделно O() и \Omega(). За O() може да ползваме константа 2, за \Omega ползваме 1.
Зад 4: Упътването почти я решава. Правим редукция на ХЦ до ХЦ в ориент. вариант така: по даден неор. граф G правим ориентиран G' със същите върхове, заменяйки всяко ребро с двойка ориентирани противоположно ребра. Очевидно G има хам. цикъл тстк G' има ориентиран х.ц., очевидно конструкцията става в полин. време. Освен това, очевидно ХЦ в ориент. вариант е в NP. Показахме, че ХЦ в ориент. вар. е NP-complete.
Редуцираме ХЦ в ориент. вар. до ОХП. При даден ориент. граф G, пример на ХЦ в ор. вар, правим G' -- пример на ОХП, така: цепим произволен връх на две, от едното копие пускаме вс. ребра към ворховете, към коите е бил свързан, а от всички, от които е имало към него, пускаме по ребро до другото копие. G има ориент. хам. цикъл тстк G' има ор. хам. път, почващ в едното копие и свършващ в другото копие. Двата върха в дефиницията на ОХП са двете копия. Очевидно конструкцията става в полин. време. Очевидно ОХП е в NP. Показахме, че ОХП е NP-c.