2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 00:49 
svv в сообщении #814526 писал(а):
patzer2097 в сообщении #814499 писал(а):
он, видимо, о самом "плохом" графе в плане радиуса спрашивает
:shock:
ТС спрашивает о графе с минимальным диаметром среди связных графов с $n$ вершинами, степень которых не превосходит $k$.
ох, прошу прощения, я неправильно понял первый пост :-(

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 11:29 
Аватара пользователя
Для степени 3, как говорил, довольно хороши сбалансированные деревья.
Конструкция годится и для бОльших К.

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 14:43 
Аватара пользователя
nikvic
А Вы эти деревья собираетесь так и оставить деревьями, или соедините как-нибудь разумно висячие вершины, что даст возможность значительно уменьшить диаметр?

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 15:20 
Аватара пользователя
svv в сообщении #814648 писал(а):
А Вы эти деревья собираетесь так и оставить деревьями, или соедините как-нибудь разумно висячие вершины, что даст возможность значительно уменьшить диаметр?

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

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 20:18 
Аватара пользователя
nikvic
Правильно! Так, может, к черту деревья?
Смотрите: при $n=14$ и $k=3$ я легко добиваюсь диаметра $3$:
Изображение
Здесь все вершины равноценны. Выделяем любую. Цифра у вершины — её расстояние от выделенной.
А Ваши деревья дают только $6$.

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 20:54 
Я прошу прощения, а это не degree diameter problem все-таки обсуждается, о которой писал Sender?
Sender в сообщении #814245 писал(а):
Кстати, родственной этой задаче является degree diameter problem.

 
 
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 22:22 
Аватара пользователя
svv в сообщении #814803 писал(а):
А Ваши деревья дают только $6$.

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение16.01.2014, 09:57 
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.$$
Нетрудно заметить, что диаметр сбалансированных деревьев ровно вдвое превосходит эту оценку.

 
 
 
 Re: Задача построения оптимального графа
Сообщение16.01.2014, 11:01 
Аватара пользователя
Sender в сообщении #815063 писал(а):
Её можно получить, рассмотрев графы Мура. Для графов порядка $N$, степень вершин которых не превосходит $K$, а диаметр равен $d$, справедливо соотношение:

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение16.01.2014, 11:06 
Аватара пользователя
Это который реализует эту оценку как точную. Их таких мало.

 
 
 [ Сообщений: 26 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group