LINUX.ORG.RU

Максимальный вполне несвязный подграф

 ,


2

1

Условия задачи такие:
1. Дан граф;
2. Разрешено удалять вершины, вместе с вершиной удаляются все инцидентные ей ребра;
3. Никаким другим способом удалять ребра нельзя;
4. Требуется найти минимальное множество вершин, после удаления которого ребер в графе не остается.

Вопросы:
1. Каково общепринятое название этой задачи?
2. Есть ли готовые быстрые алгоритмы?

★★★★★

какова практическая ценность сего?

Deleted ()
Ответ на: комментарий от Deleted

Выросло из прикладной задачи об оптимизации. Если хочется более наглядной интерпретации, то могу такое предложить: вершины — это люди в тесной комнате; если два человека наступают друг другу на ноги, то соответствующие вершины соединены ребром; нужно ликвидировать давку, но оставить в комнате как можно больше народу.

Manhunt ★★★★★ ()
Последнее исправление: Manhunt (всего исправлений: 2)

Жадный алгоритм уже пробовал?

mix_mix ★★★★★ ()

Не встречалось такого. Может как-то так:

  1. Заполнить index priority queue парами "(вершина, её степень)".
  2. Выбрать вершину с наибольшей степенью.
  3. Если степень 0, завершить алгоритм.
  4. Иначе запомнить вершину, обновить степени смежных вершин и вернуться ко второму пункту.
  5. [Завершено] Использовать список запомненных вершин.

Должно выйти порядка n*log(n) операций.

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

Это, очевидно, не работает. Например для графа с вершинами {0, 1, .. n} и ребрами (0, i) и (i, i+1).

Степень центральной вершины(номер 0) равна n, степень остальных — 3. Но центральная вершина не входит в оптимальный набор вершин.

Waterlaz ★★★★ ()

Я решал так:

1. Удалять поочередно вершины с максимальной степенью.

2. При равенстве степеней удалять вершину у которой присутствует сосед с минимальной степенью.

Графа для которого этот алгоритм дает неоптимально решение я придумать не смог, препод задачу принял (2 курс был).

crowbar ()
Ответ на: комментарий от crowbar

Смотри мой предыдущий комментарий.

ЗЫ по твоей же ссылке написано, что задача NP-полная.

Waterlaz ★★★★ ()
Ответ на: комментарий от Waterlaz

Почему? Оптимальный набор будет 0, 1, 3, 5, ... n

ЗЫ по твоей же ссылке написано, что задача NP-полная.

Я и не утверждаю что мое решение всегда работает.

crowbar ()
Ответ на: комментарий от crowbar

Почему? Оптимальный набор будет 0, 1, 3, 5, ... n

Да, это я стормозил. Ребра должны быть (i, i+1) и (0, 1), (0, 3), (0, 5) итд.

Тогда правильный ответ 1, 3, 5, ... (вершины с нечетным номером)

Waterlaz ★★★★ ()
Ответ на: комментарий от Waterlaz

Да тогда всё правильно. Мой алгоритм тоже не работает.

crowbar ()
Ответ на: комментарий от MKuznetsov

Вершинная связность
первое что попадается в поиске

Тут путаница терминологическая. Строго говоря (и в определении вершинной связности) под «несвязным графом» подразумевается граф с более чем одной компонентой связности. А мне в названии темы следовало бы вместо «несвязный подграф» написать «вполне несвязный подграф» (я надеялся, что это станет ясно из описания в ОП).

PS название темы поправил

Manhunt ★★★★★ ()
Последнее исправление: Manhunt (всего исправлений: 1)

Сколько в графе оказывается несвязных вершин после удаления одной из них? Несвязных подграфов? Попробуйте мыслить а этом ключе! А не думать о том, чтоб удалять вершины с максимальной степенью.

anonymous ()

хм.

в некотором смысле это так направить рёбра - т.е из графа сделать оргграф.

что бы листьев(вершин в которых нет входящих)(ибо по факту у нас не только дерево но возможен DAG)-было наибольшее.

имхо думаю такая формулировка облегчит поиск алго

qulinxao ★★☆ ()
Ответ на: комментарий от qulinxao

ну да. решаем для связного ибо мера несвязного графа будет просто суммой мер связных компонент :)

qulinxao ★★☆ ()

Погугли Kayles game на графах. Вроде похоже.

unt1tled ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.