2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 00:49 
Заслуженный участник


14/03/10
867
svv в сообщении #814526 писал(а):
patzer2097 в сообщении #814499 писал(а):
он, видимо, о самом "плохом" графе в плане радиуса спрашивает
:shock:
ТС спрашивает о графе с минимальным диаметром среди связных графов с $n$ вершинами, степень которых не превосходит $k$.
ох, прошу прощения, я неправильно понял первый пост :-(

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 11:29 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 14:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 15:20 
Заслуженный участник
Аватара пользователя


06/04/10
3152
svv в сообщении #814648 писал(а):
А Вы эти деревья собираетесь так и оставить деревьями, или соедините как-нибудь разумно висячие вершины, что даст возможность значительно уменьшить диаметр?

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 18:01 


01/12/11

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 20:18 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 20:54 
Заслуженный участник


14/03/10
867
Я прошу прощения, а это не degree diameter problem все-таки обсуждается, о которой писал Sender?
Sender в сообщении #814245 писал(а):
Кстати, родственной этой задаче является degree diameter problem.

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение15.01.2014, 22:22 
Заслуженный участник
Аватара пользователя


06/04/10
3152
svv в сообщении #814803 писал(а):
А Ваши деревья дают только $6$.

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение16.01.2014, 09:57 


14/01/11
2916
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 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Sender в сообщении #815063 писал(а):
Её можно получить, рассмотрев графы Мура. Для графов порядка $N$, степень вершин которых не превосходит $K$, а диаметр равен $d$, справедливо соотношение:

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

 Профиль  
                  
 
 Re: Задача построения оптимального графа
Сообщение16.01.2014, 11:06 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Это который реализует эту оценку как точную. Их таких мало.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group