IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Графы.
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


Построить Гамильтонов обход связного графа.

может кто нибудь в курсе что это и как это?! хотя бы примерно.. smile.gif буду благодарна любой помощи..   :smile.gif


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 26

Репутация: -  0  +


У меня есть 2 обхода графа: в ширину и глубину, что такое Гамильтонов обход- не знаю. Расшифаруй.


--------------------
QUI NON PROFICIT, DEFICIT(Кто не идёт вперёд, идёт назад)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


дак если б знать что это..  

Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.

Алгоритм построения Гамильтонова контура.
   1. Свойства Гамильтоновых линий (коневой обход, при каких m,n
решетка m*n имеет гамильтонов цикл).
     1.1. Любой полный граф содержит Гамильтонов путь.
     1.2. Если |Г(i)| + |Г(i)|>= m-1, то существует Гамильтонова цепь.
     1.3. Если |Г(i)| + |Г(i)|>= m, то существует Гамильтонов путь.
  -------------¬          -----------------------¬  --------------¬
  ¦ Gam(i,lev) ¦       -->¦ lev=0;     New[V]=0  ¦->¦ Gam(i0,lev)  ¦->
  --------------          ¦ New[i0]=1; Rem[i0]=0 ¦  ---------------
                          ------------------------
 ------¬ нет ---------¬нет----------¬  --------------¬  ----------¬
->¦Lev=m¦---->¦New[i]=1¦-->¦New[i]:=1¦->¦Цикл jeГ(-,i)¦->¦New[i]=0 ¦->
 ---+---да   ----+-----   -----------  -------+-------  -----------
 ---v-¬    нет   V да                  -------v------¬
 ¦i=i0¦--------->+-------->            ¦ Gam(j,Lev+1)¦
 ---T--да        &                     ¦    rem[j]=i ¦
----v----¬       ¦                     ---------------
¦Use(Rem)¦--------
----------


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


ой.. не оч. понятно.. sad.gif


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Я понимаю, что для нахождения Гамильтонова цикла потребуется обход в глубину, при этом каждая вершина должна браться по одному разу...  Полностью гамельтонов цикл будет построен, если будут использованы по одному разу все вершины графа...
Впринципе ету прогу на пасе реально сделать за несколько часов (включая время на тесты и красивое оформление)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


Metalic
обход вглубину у меня есть.. правда я еще не оч. разбиралась.. smile.gif

если бы хотя бы не программу..а так, примерно алгоритм ты бы мне рассказал то я была бы оч. благодарна.. smile.gif


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 17:07
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name