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

cast MKuznetsov www_linux_org_ru dikiy jtootf

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

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

http://neerc.ifmo.ru/wiki/index.php?title=Вершинная,_реберная_связность,_связ...

первое что попадается в поиске

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

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

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

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

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

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

Я решал так:

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

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

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

1. Каково общепринятое название этой задачи?

https://en.wikipedia.org/wiki/Vertex_cover

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

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

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

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

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

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

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

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

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

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

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

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

Да, это оно! Премного благодарен.

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

хм.

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

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

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

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

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