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

[Conrad]

Добрый день.

Дано: Неориентированный граф имеет $N$ вершин. Каждая вершина может быть связана с $K$ других вершин ($K=2..N-1$).
Вес любого ребра = 1. Граф дожен быть связанным.

Надо найти оптимальное соединение, чтобы минимизировать путь из любой вершины в любую вершину.

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

$N$ в пределах $10-1000000$.

Нужен алгоритм построения такого графа или графа близкого к оптимальному.

[ИСН]

Формулировка выиграла бы в краткости от использования слова "диаметр".

-- менее минуты назад --

Ответ скорее всего известен, но я о нём не слышал, а скажу из общих соображений. Эти задачи обычно полнопереборные, но есть простые хорошие приближения. Ну вот и делайте так: выбираем пару вершин, между которыми наибольшее расстояние и у которых есть свободные валентности, и их связываем. И так до упора.

[Sender]

Мне представляется перспективным построение графа в виде иерархической "кластерной" структуры. Все вершины сначала объединяем в кластеры первого уровня так, чтобы каждая вершина кластера была соединена со всеми остальными, а количество свободных валентностей кластера было наибольшим. Кластеры 1-го уровня по тому же принципу объединяем в кластеры 2-го уровня и т.д.

[Deggial]

Conrad
Оформляйте формулы и термы $\TeX$ом, код - тегом code, маленькие строки кода - тегом tt.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
В случае неоформления формул тема будет перемещена в Карантин.

[Null]

Степень каждой вершины ровно $K$ или можно меньше?

[Sender]

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

[Null]

(Оффтоп)

В oeis для диаметра 2 2 разных последовательности.A058201 A064513

Можно сделать тупую оценку: Если $\left(\frac{k-1}{2}\right)^2\ge n$ то возможен диаметр 2. Более того если $l_1\cdot l_2\cdot\dots\cdot l_s\ge n$ и $l_1+l_2+\dots +l_s+1=k$ то возможен диаметр $s$

[svv]

Null в сообщении #814215 писал(а):

Степень каждой вершины ровно $K$ или можно меньше?

Можно меньше. Задача, скорее всего, прикладная. Если добавление новых ребер не уменьшит диаметр графа, то и ни к чему.
При $N=5, K=3$ ровно и не получится.

[nikvic]

ИСН в сообщении #814199 писал(а):

Эти задачи обычно полнопереборные,

Не факт: полнопереборные обычно задаются конкретными ограничениями из большого множества.

А исходная задача, для степени 3, имеет отношение к хорошо сбалансированным деревьям - с логарифмической оценкой. Другой крайний случай - полные паросочетания с диаметром два.

Интересно, будет ли логарифмическая оценка верной как нижняя при фиксации степени...

[patzer2097]

ИСН в сообщении #814199 писал(а):

Формулировка выиграла бы в краткости от использования слова "диаметр".

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

ИСН в сообщении #814199 писал(а):

Эти задачи обычно полнопереборные, но есть простые хорошие приближения.

она "полнопереборная" в том смысле, что приходится перебирать (почти) все пары $(i,j)$ вершин и искать кратчайшие пути между всякими $i$ и $j$.

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

Нужен алгоритм построения такого графа или графа близкого к оптимальному.

А с точки зрения вычислительной сложности задача не переборная, она допускает быстрое решение: всевозможных пар $n^2$, а расстояние между заданными вершинами может быть найдено за $O(n^2)$ с помощью алгоритма Дейкстры. (Через $n$ я число вершин обозначил.)

[nikvic]

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

А с точки зрения вычислительной сложности задача не переборная, она допускает быстрое решение: всевозможных пар $n^2$, а расстояние между заданными вершинами может быть найдено за $O(n^2)$ с помощью алгоритма Дейкстры. (Через $n$ я число вершин обозначил.)

Гм, а сколько подмножеств у множества пар?

[patzer2097]

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

Гм, а сколько подмножеств у множества пар?

нам не нужны подмножества пар. мы для каждой пары $(i,j)$ считаем минимальное расстояние $s_{ij}$ между ними (по алгоритму Дейкстры). Дальше находим $e_k$ как $\max_j s_{jk}$ для всех вершин $k$. Вершина с минимальным $e_k$ и будет центром

[nikvic]

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

нам не нужны подмножества пар.

Я понял задачу так, что нам разрешено использовать фиксированную валентность как угодно. И разрешено перебирать все получающиеся графы.

[patzer2097]

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

Я понял задачу так, что нам разрешено использовать фиксированную валентность как угодно. И разрешено перебирать все получающиеся графы.

а, да, Вы правы.. ТС вообще какую-то непонятность написал. он, видимо, о самом "плохом" графе в плане радиуса спрашивает ну, самым плохим будет тогда простой путь, и без всякого алгоритма поиска

[svv]

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

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

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

Похоже, каждый понял задачу по-своему.

Из двух вариантов:
1) какой-то граф с $n$ вершинами уже дан, и его надо достроить;
2) граф строится «с нуля»: вначале есть только $n$ вершин, все ребра добавляем сами, —
я склоняюсь ко второму. Фраза ТС

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

Дано: Неориентированный граф имеет N вершин. Каждая вершина может быть связана с K других вершин

означает лишь, что граф таким должен получиться после построения.