вариант А, зад 1:

Задачата е почти същата като разглежданата на лекции изчислителна задача
"търсене в сортирана по редове и колони матрица".  В текущите лекционни
записки това е в Секция 7.4.3, стр. 247.  Малката разлика е, че там
матрицата е n x n, докато сега е m x n, съответно начупената линия е с
дължина m+n-1, а не 2n-1.  Иначе, алгоритъмът е същият, аргументацията
с противник за долната граница е същата.



вариант А, зад 2:

Алчният алгоритъм е такъв:
 A <- \emptyset
 Докато върховете на всяка свързана компонента
 (в началото е само една -- самото дърво) са повече
 от два, прави следното:
   Намери множеството U от висящите върхове
   Добави U към A
   Премахни U от графа
   Премахни висящите върхове

Когато останат по два върха в свързана компонента,
добави произволно единият от тях към А и премахни
другия

Накрая върни A

Това е алгоритъмът.  Аргументацията за коректност е
следната.  Нека U е м-вото от висящите върхове във
входното дърво. Нека v1 .. vk са върховете, които
имат съсед-висящ връх (работим при допускането,
че върховете са поне 3).  U се разбива на U1 .. Uk
според съседствата с v1 .. vk.  За всеки vi е вярно следното:

  ако нито vi, нито върховете от Ui са в
  независимото множество А, то А не е максимално (очевидно)

  не може едновременно vi и кой да е връх
  от Ui да е в A

  по-добре е да сложим Ui в A (самото Ui е антиклика),
  отколкото vi.  Ако |Ui| > 1, това е задължително,
  ако |Ui| = 1, не е задължително, но няма да сбъркаме.
  Няма смисъл да слагаме само някои върхове от Ui в А --
  трябва да го сложим цялото, инак А няма да е максимално.

  ако Ui е в A, няма как vi да е в A

Тези съображения позволяват да "белим" дървото
от висящите върхове навътре, като слагаме висящите
в A и после изтриваме множеството от съседите им
и тях.  При това дървото може да се разкъса и
да се получат много дървета, но това няма значение.

Сложността е линейна в размера на дървото, ако поначало
се изчислят степените на върховете.  След това е тривиално
да се намерят U и v1 .. vk; за изтриването на върховете от
U не е необходимо да се прави нещо, а просто самото U става
празно; изтриването на v1 .. vk се състои в
намаляването с 1 на степените на всеки съсед, като при
получаване на степен точно 1 този съсед бива сложен в U.

Задачата може да се реши и с динамично, с пускане на един 
модифициран DFS.



вариант Б, зад 1:

При даден  пример на HP -- обикновен граф G,
правим пример <G, n> на LONGEST PATH, където
n е броят на върховете.  Очевидно G е ДА-пример
на HP тстк <G,n> е ДА-пример на LONGEST PATH.



вариант Б, зад 2:

Това е задачата INTERVAL SCHEDULING.  Решение по алчната
схема, както и решение с динамично, има в лекционните
записки.  В момента това е в Секция 13.10 на стр. 397.
Сложността е Theta(n lg n).