Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

11:03a

Клики графа Задумался на таким вопросом: каково наибольшее возможное количество максимальных по включению клик графа, содержащих фиксированную вершину v, если есть k смежных вершине v вершин? (т.е. если именно из семейства клик, содержащих v, выбирать максимальные по включению, причём они не обязаны быть максимальными по отношению ко всему графу. Для простоты вообще можно считать, что в графе нет вершин, не смежных v )

(Клика графа - подмножество вершин, в котором любые две вершины смежны)

Зачем это понадобилось? Нужен алгоритм поиска всех таких максимальных клик, хочу понять, можно ли вообще придумать что-то более эффективное, чем тривиальный поиск всех клик, содержащих v ,и отбор из него максимальных, что займёт в худшем случае, если не ошибаюсь, O(2^(2k)). Пока что-то не получается отбирать сразу только максимальные...

Update Вопрос с алгоритмом и его трудоёмкостью вроде прояснился.

Update2

наибольшее количество максимальных клик 3^(k/3)