5.5. Подсказки к задачам

Задача 5.1: Конечно, искать эйлеров цикл минимального веса в полном взвешенном графе есть совершенно бессмысленное занятие — они там все одинакового веса :). Сведение одной задачи к другой аналогично сведению этих задач для гамильтонова цикла не пройдёт, но задачи все-таки сводятся друг к другу, просто потому, что обе задачи есть \(P\)-задачи.

Задача 5.2: Подсказка: идея «разделяй и властвуй». Попробуйте доказать, что всегда существует (хотя бы) одна чёрная и одна белая точка такие, что если провести через них прямую, то слева от неё будет поровну белых и чёрных точек (а тогда справа тоже будет поровну). Если нашли такую пару точек, то дальше решаем задачи отдельно слева и отдельно справа.

Задача 5.3: Подсказка: если инвертировать граф (т.е. где было ребро — удалить, а где не было — добавить), то клика станет независимым множеством и наоборот. Ещё подсказка: если есть некоторое независимое множество, то оставшиеся вершины образуют контролирующее множество, и наоборот.