<<
>>

Жадный алгоритм для задачи о независимом множестве для деревьев

Наше рассмотрение жадного алгоритма для дерева начнется с анализа того, как ре- шение выглядит с точки зрения одного ребра (разновидность идеи из раздела 10.1). Возьмем ребро e = (и, v) в графе G.
В любом независимом множестве S в G не более чем один из узлов и или v может принадлежать S. Нам хотелось бы найти ребро e, для которого жадный алгоритм мог бы решить, какой из двух концов следует вклю- чить в независимое множество.

Для этого мы воспользуемся важнейшим свойством деревьев: у каждого дерева должен быть как минимум один лист — узел со степенью 1. Возьмем лист v; пусть (и, v) — уникальное ребро, инцидентное v. Как «жадно» оценить относительные преимущества включения и или v в независимое множество S? Если включить v, то из всех остальных узлов только и напрямую «блокируется» от присоединения к независимому множеству. Если включить и, то блокируется не только v, но и все остальные узлы, присоединенные к и. Итак, если мы стремимся к максимизации размера независимого множества, похоже, включение v должно быть лучше (или по крайней мере не хуже) включения и.

(10.5) Если T = (V, E) — дерево, а v — лист этого дерева, то существует незави- симое множество максимального размера, содержащее v.

Доказательство. Рассмотрим независимое множество максимального раз- мера S. Пусть e = (и, v) — уникальное ребро, инцидентное узлу v. Очевидно, по крайней мере один из узлов и или v принадлежит S; в противном случае мы могли бы добавить v в S с увеличением размера. Теперь, если v

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

Еще по теме Жадный алгоритм для задачи о независимом множестве для деревьев:

  1. Высшее «Я» и жизненная задача для шизоидного характера
  2. Жизненная задача и высшее «Я» для оральной структуры
  3. Жизненная задача и высшее «Я» для психопатического характера
  4. Жизненная задача и высшее «Я» для мазохистского характера
  5. Жизненная задача и высшее «Я» для жесткого характера
  6. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО РЕШЕНИЮ ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ ЗАДАЧ
  7. для успешного осмотра места происшествия рекомендуется решать следующие три задачи
  8. Прием создания исходных благоприятных психологический условий для решения задач общения.
  9. 4. Успеха добивается тот, кто для того, чтобы лучше решить задачу, повышает планку цели.
  10. То, что очевидно для одного поколения, всегда было открытием для предыдущего.
  11. Г. Упражнение для предоставления наставникам вашего поля для работы.
  12. Для подзарядки мы обращаемся вверх, а для разрядки—вниз, к земле.
  13. Кроткое сердце – жизнь для тела, а зависть – гниль для костей (Притч. 14,30).
  14. Метод саморегуляции эффективен для подготовки беременных к родам и может быть рекомендован для массового обучения.
  15. Очерк 1: Гленда «Для себя и для организации я хочу, чтобы все делалось правильно и приводило к нужным результатам»
  16. Статья 203-1. Незаконный оборот дисков для лазерных систем считывания, матриц, оборудования и сырья для их производства