Найти наибольшее подмножество непрямого графика

Question

Ввод: список вершин и список смежности.

Выход: наибольшее подмножество хороших вершин.

(Мы говорим вершина в подмножестве, как «хорошая вершина», если она имеет по крайней мере 2 смежных вершины и, по меньшей мере, 2 несмежные вершины в этом подмножестве.)

Пример 1:

Vertexes: [1, 2, 3, 4, 5] 
Relations: [(1,2), (1,3), (3,4), (3,5), (4,5)] 

output: [] 

Пример 2:

output: [1,2,3,4,5,6] 

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

Answer 1

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

Удалить все нехорошие вершины из графика. Когда вы это делаете, ранее верные вершины могут перестать быть в порядке, поскольку они заканчиваются из соседних или не соседних; эти вершины также не могут быть в выводе, поэтому относитесь к ним, как и к любым другим нехорошим вершинам, и удаляйте их тоже. Продолжайте движение, пока все оставшиеся вершины не будут в порядке.

Вывести набор оставшихся вершин.

Answer 2

1. Удалите вершины, которые имеют менее двух соседей.

2. Построить края дополнения (левых) вершин. Дополнение не имеет такого же отношения в наборе отношений происхождения, но имеет другие. Объедините набор отношений происхождения с дополнением, он станет множеством отношений, которое является полным соотношением с левыми вершинами.

3. Удалите вершины, в которых есть не более двух соседей. Вершины результата - это результат.

Процесс удаления на этапах 1 и 3, является рекурсивным процессом. Он должен удалить вершины, пока никто не сможет быть удален.