Задача построения оптимального графа

[patzer2097]

svv в сообщении #814526 писал(а):

patzer2097 в сообщении #814499 писал(а):

он, видимо, о самом "плохом" графе в плане радиуса спрашивает

ТС спрашивает о графе с минимальным диаметром среди связных графов с $n$ вершинами, степень которых не превосходит $k$.

ох, прошу прощения, я неправильно понял первый пост

Conrad в сообщении #814197 писал(а):

То есть берем вершину находим кратчайшие пути к остальным вершинам - максимальный из них будет "высотой" вершины. Надо найти такое соединение (граф) при котором максимальная "высота" всех вершин будет минимальной.

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

[nikvic]

Для степени 3, как говорил, довольно хороши сбалансированные деревья.
Конструкция годится и для бОльших К.

А что можно сказать про оценку снизу?

[svv]

nikvic
А Вы эти деревья собираетесь так и оставить деревьями, или соедините как-нибудь разумно висячие вершины, что даст возможность значительно уменьшить диаметр?

[nikvic]

svv в сообщении #814648 писал(а):

А Вы эти деревья собираетесь так и оставить деревьями, или соедините как-нибудь разумно висячие вершины, что даст возможность значительно уменьшить диаметр?

Значительно - не удастся: чтобы добраться от одной висячей вершины до другой в том же "блоке" (от "короля" идёт К поддеревьев), нужно подняться почти до "короля".

[Skeptic]

Если я правильно понял задачу, то получается такой алгоритм. Располагаем все вершины по окружности. Получаем граф, у которого все диаметры равны. Максимальный диаметр равен $mod(N/2)$. Для уменьшения диаметров в построенный граф дополняем соединениями через вершину. Ьаксимальный диаметр получается $mod(N/4)$. И т.д. Записав граф как матрицу, предложенный алгоритм сводится к последовательному заполнения её диагоналей.

[svv]

nikvic
Правильно! Так, может, к черту деревья?
Смотрите: при $n=14$ и $k=3$ я легко добиваюсь диаметра $3$:

Здесь все вершины равноценны. Выделяем любую. Цифра у вершины — её расстояние от выделенной.
А Ваши деревья дают только $6$.

[patzer2097]

Я прошу прощения, а это не degree diameter problem все-таки обсуждается, о которой писал Sender?

Sender в сообщении #814245 писал(а):

Кстати, родственной этой задаче является degree diameter problem.

[nikvic]

svv в сообщении #814803 писал(а):

А Ваши деревья дают только $6$.

Посчитайте, как у Вас растёт диаметр с ростом числа вершин и фикс. валентностью. Линейно.
А у меня - как логарифм

[Sender]

nikvic в сообщении #814601 писал(а):

А что можно сказать про оценку снизу?

Её можно получить, рассмотрев графы Мура. Для графов порядка $N$, степень вершин которых не превосходит $K$, а диаметр равен $d$, справедливо соотношение: $N \leqslant 1+K\sum\limits_{i=0}^{d-1}(K-1)^i$, откуда получаем:

$$d \geqslant \Biggl \lceil \log_{K-1}\Big[1+(N-1)(1-\frac{2}{K})\Big] \Biggr \rceil.$$

Нетрудно заметить, что диаметр сбалансированных деревьев ровно вдвое превосходит эту оценку.

[nikvic]

Sender в сообщении #815063 писал(а):

Её можно получить, рассмотрев графы Мура. Для графов порядка $N$, степень вершин которых не превосходит $K$, а диаметр равен $d$, справедливо соотношение:

А что такое граф Мура?
Сама оценка получается несложно. Берём любую вершину и оцениваем сверху число точек в сферах радиуса 1, 2, 3 и т.д. с центром в этой точке. В первой сфере - не более К точек, дальнейшее "размножение" - не более К - 1.

[ИСН]

Это который реализует эту оценку как точную. Их таких мало.