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