Задачка про Гамильтонов граф(((, очень нужна помощь!!!!!плз!!!! Опции

[ОтчаявшийсяПрогер]

Люди добрые и многознающие!!! Помогите пжлсты решить задачку про гамильтонов граф....курсовая моя...

Вот текст задачки____:
Гамильтоновым называется граф,в котором существует простой цикл,содержащий все вершины графа(но необязательно все ребра). Разработать алгоритм и написать программу, позволяющую определять - является ли задаваемый граф Гамильтоновым или нет.

ПЖЛУСТО ПОМОГИТЕ МНЕ Я В ШКОЛЕ ГРАФЫ НЕ ПРОХОДИЛ И ВПЕРВЫЕ О НИХ УСЛЫШАЛ....
На форумах тему по Гамильтонов граф небыло...вот и написал

Помогите решить курсовую....я вообще уже поник

[Michael_Rybak]

Задача решается полным перебором. В инете инфы просто туча. Ищи.

[ОтчаявшийсяПрогер]

Я уже всё обыскал...ничё ненайду(((
Уже крыша от этого инэта и Паскаля едет
Я просто непонимаю как сделать рандомно пути и по ним ходить....вообще немогу придумать процедуру как определить программно есть путь между вершинами графа или нет ??
да и вообще немогу граф построить ((

Сообщение отредактировано: ОтчаявшийсяПрогер - 6.12.2007 17:42

[ОтчаявшийсяПрогер]

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

Сообщение отредактировано: ОтчаявшийсяПрогер - 6.12.2007 18:03

[Michael_Rybak]

"Прога по созданию графов" - в FAQ.

Алгоритм - *вторая ссылка в гугле* по запросу "гамильтонов цикл".

[ОтчаявшийсяПрогер]

СПС за инфу...но я FAQ просмотрел и нашел только алгоритмы над графами(Гамильтонового небыло)
А по ссылке Гугля....разберусь как нибудь
Я немогу понять как написать процедуру случайного расставления рёбер меж. вершинами(чтоб некоторые верш. соединяла,а некоторые нет)...
или все вершины у графа соединены между собой???

[Michael_Rybak]

представляешь граф матрицей смежности. проходишь по ней циклом и ставишь рандомно нули и единички.

если граф неориентированный, после этого делаешь матрицу симметричной.

[ОтчаявшийсяПрогер]

Всё...теперь понятно что представляет собой граф в Паскале

Подскажи тогда сначала рандомно вводишь, после этого симметричной делаешь?
К примеру ввел все элементы
0 1 0 1
0 0 1 1
1 0 0 1
1 1 1 0
и делаешь симметрию относительно главной диагонали...а сама глал. диагональ состоит из 0..
0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
Вот так???

А так спасибо большое..терь я хоть чёто понял))

[Michael_Rybak]

чтобы сделать симметричной - копируешь инфу из верхней треугольной части в нижнюю (например):

for i := 1 to n do
  for j := 1 to i - 1 do
    a[i, j] := a[j, i];

т.е. да, ты правильно пример привел.

а можно и сразу генерить симметричную:

for i := 1 to n do
  for j := 1 to i - 1 do begin
    a[j, i] := random(2);
    a[i, j] := a[j, i];
  end

[ОтчаявшийсяПрогер]

Понятно..
Я в принципе так и сделал ...
Осталась процедура на проверку наличия Гамильтонова цикла..
А по ссылке которую ты кинул я ходил, ток ничё не понял)) и сейчас она неактивна в добавок...
Там надо сделать рекурсию в процедуре или без неё обойтись можно??

[Michael_Rybak]

Неактивную ссылку можно почитать в кеше у гугла.

Лучше с рекурсией.

Ладно, давай расскажу на пальцах.

Схема такая: заводишь масив булевых значений visited[]. Заполняешь fals'ами. В рекурсию принимаешь текущую точку и делаешь следующее: помечаешь ее как посещенную, и идешь циклом по всем достижимым из нее не посещенным. Для каждой запускаешь рекурсию. После этого цикла снимаешь флаг visited текущей точки.

Еще подумай, где и как здесь добавить проверку на то, что решение найдено.