Дизайн и анализ на алгоритми, КН2, пролет 2016

Следното грешно решение на шеста задача се среща в толкова много писмени работи, че започвам да мисля, че е имало комуникационен канал в зала 210, който е останал undetected за квесторите.

"Решението" е, при даден пример (G(V,E),k) на VC да построим пример (A, B, k') на другата задача, където A := E, B е множеството от множествата на инцидентните ребра (по всички върхове), а k' := k.

Това просто не работи.  Представете си граф с минимално върхово покриване.  Да кажем, едно.  Тогава G е граф-звезда.  Нека G се състои от един връх u от степен n и още n на брой върха v1 .. vn, всеки от които е съсед на u и на никой друг връх.  Тогава A ще е множеството от n на брой ребра e1 .. en, а B ще е множество от n на брой едноелементни множества {ei}, отговарящи на висящите върхове на графа, и още едно n-елементно множество {e1 .. en}, отговарящо на "централния" връх.  И освен това  k трябва да е 1.  Е няма как да изберем едноелементно подм-во на това А, демек едно ребро, демек някое {ej}, което да има непразно сечение с всеки елеемнт на B.  Това е все едно да търсим едно ребро, което да се среща във всички n+1 на брой елемента на B -- няма такова.

Това, че има връх, който е в сечението на всички n ребра, е ДРУГО НЕЩО.