найти минимальный размер доминирующего множества для дерева, используя жадный алгоритм

Question

Доминирующий набор (DS): = задан неориентированный граф G = (V; E), набор вершины S V является доминирующим множеством, если для каждой вершины в V есть вершина в S, смежный с v. Все множество вершин V является тривиальным доминирующим множеством в любой график.

Найти минимальный размер доминирующего множества для дерева.

Answer 1

1- Всегда начинать с листьев

2- Добавить своего родителя в DS и вырезать потомков

3- Отметить родителей выбранного родителя как уже доминирующих

4-После завершения процесса проверьте, есть ли у этих отмеченных узлов дочерние элементы, для которых не доминирует
, и добавьте их в DS

Удачи

Answer 2

Я попытаюсь доказать это более формальным способом.

OUTLINE

Чтобы доказать, что ваш жадный алгоритм верен, вам нужно доказать две вещи:

1. Во-первых, ваш жадный выбордопустимо и всегда может быть использовано при формировании оптимального решения, и
2. секунда, что ваша задача имеет оптимальное свойство подструктуры, то есть вы можете сформировать оптимальное решение из оптимальных решений для подзадач вашей собственной проблемы.

Жадный выбор : В вашем дереве T = (V, E) найдите вершину v в дереве с наибольшим количеством листьев.Добавьте его к своему доминирующему набору.

Оптимальная субструктура

T '= (V', E ') такая, что:

• V'= V \ ({a: a ϵ V, a смежна с v, а степень a ≤ 2} ∪ {v})
• E' = E - любое ребро, включающее любую из удаленных вершин

Другими словами

Найдите вершину с наибольшим числом листьев, удалите любую из смежных вершин со степенью, меньшей или равной 2, затем удалитеv и добавьте его в свой доминирующий набор.Повторяйте это до тех пор, пока у вас не останется вершин.

---

Доказательство

Жадное доказательство выбора

Для любого листа l , должно быть, что либо сам, либо его родитель находится в доминирующем множестве.В нашем случае вершина v , которую мы выбрали бы, находится в этой ситуации.

Пусть A = { v ₁ , v ₂ , ..., v _k } будет минимальным доминирующим набором T. Если A уже имеет v в качестве члена, мы закончили.Если это не так, он должен иметь l , в противном случае это не доминирующий набор.Таким образом, мы можем просто сформировать A ' = { A - {l} + { v }} и при этом оставаться доминирующим множеством.С | A ' |= | A |, A ' по-прежнему оптимально.Таким образом, мы всегда сможем сформировать оптимальное решение с нашим жадным выбором.

Оптимальное доказательство основания

Предположим, что A является минимумомДоминантный набор для T = ( V, E ), но это A ' = A \ { v } не является минимальным доминантным набором для T ', как определено выше.

Создайте минимальный доминантный набор для T ', назовите его B. Как уже упоминалось, | B |<| <em>A ' |.Можно показать, что B ' = B ∪ { v } является доминирующим набором для T .Тогда, так как | A ' |= | A |- 1, | B ' |= | B |+1 получаем | B ' |<| <em>A |.Это противоречиво, поскольку мы предполагали, что A является минимальным независимым множеством.Таким образом, должно быть, что A ' также является минимальным независимым набором T' .

Доказательство B ' = B ∪ { v } является доминирующим набором для T :

• v , возможно, смежные вершины смежны не в T '.Мы покажем, что в любых вершинах, которые не рассматривались в T ', будут доминировать вершины в B' (это означает, что мы выбрали оптимальный набор): Пусть y будет некоторой вершиной, смежной с v , а не с T '.По определению T ', у может иметь только степень 1 или 2. Теперь в y преобладает v .Если y - лист, то мы закончили.Однако, если y имеет степень 2, тогда y соединяется с другим узлом, который обязательно находится в доминирующем наборе B .Это потому, что когда мы удалили v , чтобы сделать T ', степень y стала 1, означая, что y или его родительский элемент был обязательно добавлен к доминирующемузадавать.Следовательно, B ' является доминирующим набором для T .