Возможен ли поиск клики в планарном графе с n вершинами 4-клика за время O(n).

задан 6 Май '16 18:30

изменен 7 Май '16 0:04

10|600 символов нужно символов осталось
1

Здесь вообще-то надо было бы уточнить, в какой форме задаётся граф. (Также нужно, наверное, уточнение, что он является простым.) Будем считать, что для каждой вершины у нас известно множество вершин, с которой соединена данная. При этом степени всех вершин тоже известны при просмотре всех вершин за линейное время. Хорошо известно, что в планарном графе имеется вершина степени не более 5. Если она участвует в 4-клике, то требуется константное число проверок для того, чтобы выяснить, входит ли она в какую-либо 4-клику (число проверок не больше 10, т.е. числа троек на пяти вершинах).

Если при проверке оказывается, что такой клики с данной вершиной нет, то из "базы данных" эту вершину можно удалить со всеми инцидентными ей рёбрами, и далее искать 4-клику в оставшемся подграфе. Такой процесс может длиться порядка $%O(n^2)$% шагов с учётом поиска вершин малой степени, однако следует заметить, что общее число рёбер планарного графа с n вершинами строго меньше 3n, что следует из формулы Эйлера (по сути дела, именно это сначала и доказывается в лемме о вершине степени не более 5). С учётом того, что рёбра мы постепенно удаляем, а количество обращений к данному ребру не превосходит константы, процесс окончится за линейное время.

Здесь неявно могут быть использованы какие-то предположения о том, в каком виде должен быть представлен граф, чтобы всё работало. В частности, может потребоваться условие, что вершины заранее отсортированы по степеням. Поскольку чёткой формулировки в этом смысле в условии нет, я ограничусь сказанным выше.

ссылка

отвечен 6 Май '16 22:34

Иначе говоря: для вершины с наименьшей степенью (известно, что она меньше шести) выяснить, входит ли в 4-клику; если нет, удалить вершину со всеми инцидентными рёбрами и повторить процесс для оставшегося планарного графа. Время — линейное по количеству вершин… Поскольку для каждой вершины удалено не больше пяти рёбер, то на каждой вершине время удаления всех инцидентных рёбер с восстановлением отсортированности вершин по степеням не превышает константы: нужно уменьшить степени соседних вершин и переместить их в связном списке соответственно…

(7 Май '16 1:19) abracadabra
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,340
×477
×127

задан
6 Май '16 18:30

показан
470 раз

обновлен
7 Май '16 1:26

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

по почте:

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

по RSS:

Ответы

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

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