Скажите, что вам дали черный ящик, который решает проблему клики в постоянное время.Поиск вершин максимальной клики за полиномиальное время
Вы даете черному ящику неориентированный граф G с привязкой k и выводит либо «Да», либо «Нет», что граф G имеет клику с не менее k вершинами.
Как бы вы использовали этот черный ящик, чтобы найти вершины максимальной клики в полиномиальное время?
Как подсказка, подумайте о том, что произойдет, если вы выберете узел из графика, удалите его, а затем проверьте, есть ли еще k-клика. Черный ящик либо скажет, что есть, либо нет. Что вы узнаете, если еще есть k-клика? Что вы узнаете, если нет?
Надеюсь, это поможет!
Я вижу, вы говорите, что все, что вам нужно сделать, это удалить узел из графика, вставить граф в черный ящик и снова проверить? Таким образом, каждый удаленный таким образом узел, который приводит к да-> без изменений, является узлом, который является частью максимальной клики, иначе это не так. – Grib
Это звучит как домашнее задание - оно должно быть помечено как домашнее задание. – Kaganar
Очевидная домашняя работа без попытки решения -> голосовать за закрытие как «слишком широкую». –
Я не прошу полного решения, просто помогите, как начать. Что вы подразумеваете под тегом как домашнее задание? В нем указано, что тег домашней работы запрещен. – Grib