Максимальное независимое множество вершин в дереве

    Следует отметить, что поскольку на шаге возвращения вершина x_ik попадает в Q_k^-, то может оказаться, что при этом новом входе значение величины Δ меньше, чем для ранее фиксированной вершины x*. Значит, надо проверить, не ускорит ли эта новая вершина выполнение условия (8). Это особенно важно в начале ветвления, когда Q_k^- = Ø.

    Описание  алгоритма:

1. Пусть S₀ = Q_k^- = Ø, Q₀⁺, Q_k^- = V, k=0.
2. Выбрать вершину x_ik ∈ Q_k⁺, как упоминалось ранее, и сформировать S_k, Q_k+1^- и Q_k+1⁺, оставляя Q_k^- и Q_k⁺ нетронутыми. Положить k=k+1.
3. Если удовлетворяется условие (8), то перейти к шагу 5, иначе к шагу 4.
4. Если Q_k⁺ = Q_k^- = Ø, то напечатать максимальное независимое множество S_k и перейти к шагу 5. Если Q_k⁺ = Ø, a Q_k^- ≠ Ø, то перейти к шагу 5. Иначе перейти к шагу 2.
5. Положить k=k−1. Удалить x_ik из S_k + 1, чтобы получить S_k. Исправить Q_k^- и Q_k⁺, удалив вершину x_ik из Q_k⁺ и добавив ее к Q_k^-. Если k=0 и Q_k⁺ = Ø, то остановиться. (К этому моменту будут уже напечатаны все максимальные независимые множества.) Иначе перейти к шагу 3.

    Список  использованной литературы

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. - М.: Наука, 1975.
2. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962.
3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
4. Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир, 1981.
5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.