Степень каждой вершины неориентированного графа не больше 5 (можно и другую константу), расстояние (число рёбер в кратчайшем пути) между любыми двумя вершинами не больше N. Найдите асимптотику (по N) максимально возможного числа вершин в таком графе.
Эту задачу мне вчера за обедом сообщил А. Л. Таламбуца. Решать мы её не умеем; кто решит — молодец.
Комментариев нет:
Отправить комментарий