Независимое множество

А теперь перейдем к чрезвычайно общей задаче, которая включает большинство более ранних задач как частные случаи. Для заданного графа G = (V, E) множество узлов S Ӭ V называется независимым, если никакие два узла, входящие в S, не соединяются ребром.

Таким образом, задача поиска независимого множества формулируется так: для заданного графа G найти независимое множество максимально возможного размера. Например, максимальный размер независимого множества для графа на рис. 1.6 равен 4: оно состоит из четырех узлов {1, 4, 5, 6}

Допустим, у вас есть n друзей, но некоторые пары терпеть друг друга не могут. Сколько друзей можно пригласить на обед, если вы хотите избежать лишней напряженности? По сути, речь идет о поиске наибольшего независимого множества в графе, узлы которого представляют ваших друзей, а ребра — конфликты в парах.

Задачи интервального планирования и паросочетаний в двудольном графе могут рассматриваться как особые случаи задачи независимого множества. Для задачи интервального планирования определите граф G = (V, E), в котором узлы соответствуют интервалам, а каждая перекрывающаяся пара соединяется ребром; независимые множества в G соответствуют совместимым подмножествам интер- валов.

С представлением задачи паросочетаний в двудольном графе ситуация чуть менее тривиальна. Для заданного двудольного графа G’ = (V’, E’) выбираемые объекты соответствуют ребрам, а конфликты возникают между двумя ребрами, имеющими общий конец (такие пары ребер не могут принадлежать общему паросочетанию).

Соответственно мы определяем граф G = (V, E), в котором множество узлов V эквивалентно множеству ребер E’ в G’. Мы определяем ребро между каждой парой элементов V, соответствующих ребрам G’ с общим концом. Теперь можно проверить, что независимые множества G точно соответствуют паросочетаниям G’.

Проверка не так уж сложна, но чтобы уследить за преобразованиями «ребра в узлы, узлы в ребра», придется как следует сосредоточиться.

С учетом общего характера задачи независимого множества эффективный алгоритм ее решения должен получиться весьма впечатляющим. Он должен неявно включать алгоритмы для задач интервального планирования, паросочетаний  в двудольном графе, а также ряда других естественных задач оптимизации.

Текущее состояние задачи независимого множества таково: эффективные алгоритмы для ее решения неизвестны, и есть гипотеза, что такого алгоритма не существует.

Очевидный алгоритм, действующий методом «грубой силы», перебирает все подмножества узлов, проверяет каждое из них на независимость, после чего запоминает самое большое из обнаруженных подмножеств.

Возможно, это решение близко к лучшему из того, что возможно сделать в этой задаче. Позднее в книге будет показано, что задача независимого множества принадлежит к большому классу задач, называемых NP-полными.

Ни для одной из этих задач не известен эффективный алгоритм решения, но все они эквивалентны в том смысле, что решение любой такой задачи будет точно подразумевать существование такого решения у всех.