основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Алгоритмы >> Графы

Страницы: 1
CD_Eater
опытный
*****

Рег.: 08/04/04
Сообщений: 310
Из: Москва
Как построить граф с наилучшими маршрутами ?
      #12084 - 09/15/06 02:30 AM

Представим себе ориентированный граф, такой что из любой вершины, двигаясь по рёбрам, можно попасть в любую другую.
Для каждой упорядоченной пары вершин (A,B) вычислим "длину маршрута" - минимальное количество рёбер, которое нужно пройти, чтобы попасть из A в B.
Максимальную из "длин маршрутов" всех пар вершин назовём "задержкой" графа.

Как построить граф на N вершинах, чтобы:
1) Из каждой вершины выходило ровно 2 ребра
2) "Задержка" графа была бы минимально возможной ?

Чему будет равна "задержка" такого графа ?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Wasya
новичок


Рег.: 06/26/06
Сообщений: 2
Из: Trfnthby,ehu
Re: Как построить граф с наилучшими маршрутами ? [Re: CD_Eater]
      #12087 - 09/15/06 10:30 PM

Теоретический предел log(n+1)-1 логарифм по основанию 2. Теоретический предел не всегда достижим. Покрайней мере для n=7 мне не удалось построить граф с задержкой 2.
Следующий алгоритм построения графа вроде дает неплохие результаты.
Строим цикл из n вершин. Внутри этого большого кольца строим K циклов длины M, где K*M=n.
Это пока все.

Редактировал Wasya (09/15/06 10:33 PM)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
CD_Eater
опытный
*****

Рег.: 08/04/04
Сообщений: 310
Из: Москва
Re: Как построить граф с наилучшими маршрутами ? [Re: Wasya]
      #12088 - 09/16/06 02:59 AM

В ответ на:

Покрайней мере для n=7 мне не удалось построить граф с задержкой 2.



Несложно перебором доказать, что такого графа не существует


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: Как построить граф с наилучшими маршрутами ? [Re: CD_Eater]
      #12091 - 09/16/06 03:51 AM

Ну вроде как нужно строить полное бинарное дерево, нет?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
SergeyevАдминистратор
заслуженный
****

Рег.: 07/31/04
Сообщений: 1361
Из: Россия, Самара
Re: Как построить граф с наилучшими маршрутами ? [Re: _МГ_]
      #12093 - 09/16/06 05:57 AM

Нет - от каждого в каждый должен быть путь. Это не дерево.

А для 6 существует?

Просто алгоритм работающий по "соображениям умных действий" не дает хороших результатов?


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
CD_Eater
опытный
*****

Рег.: 08/04/04
Сообщений: 310
Из: Москва
Re: Как построить граф с наилучшими маршрутами ? [Re: Sergeyev]
      #12095 - 09/16/06 07:59 AM

В ответ на:

А для 6 существует?



Да, легко построить


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 759 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, PAV, Sergeyev 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 15245

Rate this topic

Переход в