Может ли кто подсказать данный алгоритм или же поделиться ссылкой на него?

задан 17 Июн '17 15:31

изменен 17 Июн '17 15:56

В плоском графе нет полных подграфов K_5. Поэтому достаточно перебрать все четвёрки. Их будет C_n^4=O(n^4), то есть это алгоритм полиномиальной сложности.

(17 Июн '17 15:45) falcao

Получается в случае если ни одной такой четверки нет, то далее нам придется перебирать все тройки и т.д.?

(17 Июн '17 15:59) Horaigo

@Horaigo: в процессе перебора четвёрок мы неизбежно просматриваем также и тройки, то есть это всё запоминается в ходе процесса. На каждом шаге мы запоминаем текущее максимальное значение размера клики, которое мы наблюдали, а потом увеличиваем его, если нашли что-то побольше.

Здесь суть задачи, как я понимаю, только в том, что для графов общего вида проблема NP-полная, а планарность сразу ограничивает размер клики глобальной константой, что даёт полиномиальную сложность.

(17 Июн '17 17:19) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,476
×548

задан
17 Июн '17 15:31

показан
364 раза

обновлен
17 Июн '17 17:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru