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

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

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

Рис. 1.6. Размер наибольшего независимого множества в этом графе равен 4


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

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

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

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

Текущее состояние задачи независимого множества таково: эффективные алгоритмы для ее решения неизвестны, и есть гипотеза, что такого алгоритма не существует. Очевидный алгоритм, действующий методом «грубой силы», пере- бирает все подмножества узлов, проверяет каждое из них на независимость, после чего запоминает самое большое из обнаруженных подмножеств. Возможно, это решение близко к лучшему из того, что возможно сделать в этой задаче. Позднее в книге будет показано, что задача независимого множества принадлежит к боль- шому классу задач, называемых NP-полными. Ни для одной из этих задач не из- вестен эффективный алгоритм решения, но все они эквивалентны в том смысле, что решение любой такой задачи будет точно подразумевать существование такого решения у всех.

Естественно задать вопрос: можно ли сказать хоть что-нибудь положительное о сложности задачи независимого множества? Кое-что можно: если имеется граф G из 1000 узлов и мы захотим убедить вас в том, что он содержит независимое мно- жество S с размером 100, сделать это будет несложно. Достаточно показать граф G,

выделить узлы S красным цветом и позволить вам убедиться в том, что никакие два узла не соединены ребром. Итак, между проверкой того, что множество действи- тельно является большим независимым, и непосредственным поиском большого независимого множества существует огромная разница. На первый взгляд заме- чание кажется тривиальным (и действительно является таковым), но оно играет ключевую роль в понимании этого класса задач. Более того, как вы вскоре увидите, в некоторых особо сложных задачах даже может не быть простого способа «про- верки» решений в этом смысле.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Независимое множество:

  1. II. 1. 1. Множества.
  2. II. 2. 2. От единого к множеству.
  3. Вариантов множество.
  4. Великое множество «я»
  5. II. 2. 7. Тетрады и дальнейшее разбиение множеств.
  6. Обида порождает множество болезней
  7. Если вы заблокированы” вас расстраивает сразу множество вещей.
  8. 4.12. СТАНЬТЕ НЕЗАВИСИМЫМ НАБЛЮДАТЕЛЕМ
  9. Независимый мыслитель
  10. ИНФОРМАЦИОННАЯ НЕЗАВИСИМОСТЬ
  11. Побольше независимости
  12. Независимость
  13. НЕЗАВИСИМОСТЬ
  14. Одиночество и независимость
  15. КУЛЬТУРНАЯ НЕЗАВИСИМОСТЬ
  16. РЕЛИГИОЗНАЯ НЕЗАВИСИМОСТЬ