Графы. Опции

[fms]

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

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

[Fire_Rage]

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

[fms]

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

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

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

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

[Metalic]

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

[fms]

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

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