<<
>>

Жадный алгоритм для более общих графов

Работоспособность жадного алгоритма, приведенного выше, для общих графов не гарантирована, потому что не гарантируется нахождение листа при каждой

итерации. Однако утверждение (10.5) относится к любому графу: если имеется произвольный граф G с ребром (и, v), в котором и является единственным соседом v, то всегда безопасно поместить v в независимое множество, удалить и и v и повто- рить с уменьшенным графом.

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

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

Еще по теме Жадный алгоритм для более общих графов:

  1. Создавать более веские основания для расстройства
  2. Как использовать тип для более эффективного консультирования
  3. Внутренне опустошенные люди, как правило, более открыты для восприятия нового.
  4. Найдя в себе более веские основания для расстройства, нам будет легче осмыслить, что существуют глубинные переживания.
  5. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  6. АЛГОРИТМ
  7. АЛГОРИТМ УДАЧИ
  8. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  9. Алгоритм исцеления:
  10. Алгоритм избавления от боли