Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Графы.

Автор: fms 26.10.2003 15:04

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

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

Автор: Fire_Rage 27.10.2003 8:34

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

Автор: fms 27.10.2003 14:57

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

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

Алгоритм построения Гамильтонова контура.
   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)¦--------
----------

Автор: fms 27.10.2003 15:02

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

Автор: Metalic 27.10.2003 16:05

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

Автор: fms 27.10.2003 21:23

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

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