11.2.1. Постановка задачи отыскания наибольшего независимого множества вершин

Задача отыскания наибольшего независимого множества вершин (и, тем самым, определения вершинного числа независимости /Зо) принадлежит к числу трудо­емких.

Эту задачу можно поставить следующим образом. Пусть задан граф G(V, E). Найти такое множество вершин X, X С V, что

w(X) = тахш(У),

где w(X): = \Х\, а £ : = {У с V \ Vu, v € Y (и, v) <£ Е} (см. раздел 2.7.5).

Если бы семейство £ независимых множеств оказалось матроидом, то поставлен­ную задачу можно было бы решить жадным алгоритмом (алгоритм 2.2). Одна­ко семейство £ матроидом не является. Действительно, хотя аксиомы mi и Mi (см. подраздел 2.7.1) выполнены, так как пустое множество вершин независимо и всякое подмножество независимого множества независимо, но аксиома Мз не выполнена, как видно из следующего примера.

Пример

Рассмотрим полный двудольный граф К_п<п+1. Доли этого графа образуют (мак­симальные) независимые множества, и их мощности различаются на 1. Однако никакая вершина из большей доли не может быть добавлена к вершинам мень­шей доли с сохранением независимости.