2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задача построения оптимального графа
Сообщение14.01.2014, 10:34 
Добрый день.

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

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

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

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

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 10:41 
Аватара пользователя
Формулировка выиграла бы в краткости от использования слова "диаметр".

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

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

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

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 11:23 
Степень каждой вершины ровно $K$ или можно меньше?

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 12:29 
Кстати, родственной этой задаче является degree diameter problem.

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 13:37 

(Оффтоп)

В 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$

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 14:03 
Аватара пользователя
Null в сообщении #814215 писал(а):
Степень каждой вершины ровно $K$ или можно меньше?
Можно меньше. Задача, скорее всего, прикладная. Если добавление новых ребер не уменьшит диаметр графа, то и ни к чему.
При $N=5, K=3$ ровно и не получится.

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 14:42 
Аватара пользователя
ИСН в сообщении #814199 писал(а):
Эти задачи обычно полнопереборные,

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

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

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 20:31 
ИСН в сообщении #814199 писал(а):
Формулировка выиграла бы в краткости от использования слова "диаметр".
то, что ТС называет "высотой вершины", правильно называется ее эксцентриситетом, "минимальная высота" - радиусом графа, а "оптимальная вершина" - центром графа.

ИСН в сообщении #814199 писал(а):
Эти задачи обычно полнопереборные, но есть простые хорошие приближения.
она "полнопереборная" в том смысле, что приходится перебирать (почти) все пары $(i,j)$ вершин и искать кратчайшие пути между всякими $i$ и $j$.

Conrad в сообщении #814197 писал(а):
Нужен алгоритм построения такого графа или графа близкого к оптимальному.

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

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

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 21:43 
nikvic в сообщении #814432 писал(а):
Гм, а сколько подмножеств у множества пар? :wink:

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 22:06 
Аватара пользователя
patzer2097 в сообщении #814463 писал(а):
нам не нужны подмножества пар.

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

 
 
 
 Re: Задача построения оптимального графа
Сообщение14.01.2014, 22:31 
nikvic в сообщении #814479 писал(а):
Я понял задачу так, что нам разрешено использовать фиксированную валентность как угодно. И разрешено перебирать все получающиеся графы.
а, да, Вы правы.. ТС вообще какую-то непонятность написал. он, видимо, о самом "плохом" графе в плане радиуса спрашивает :-( ну, самым плохим будет тогда простой путь, и без всякого алгоритма поиска :-)

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

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

Из двух вариантов:
1) какой-то граф с $n$ вершинами уже дан, и его надо достроить;
2) граф строится «с нуля»: вначале есть только $n$ вершин, все ребра добавляем сами, —
я склоняюсь ко второму. Фраза ТС
Conrad в сообщении #814197 писал(а):
Дано: Неориентированный граф имеет N вершин. Каждая вершина может быть связана с K других вершин
означает лишь, что граф таким должен получиться после построения.

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


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