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

Автор: ОтчаявшийсяПрогер 6.12.2007 21:01

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

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

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

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

Автор: Michael_Rybak 6.12.2007 21:36

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

Автор: ОтчаявшийсяПрогер 6.12.2007 21:40

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

Автор: ОтчаявшийсяПрогер 6.12.2007 22:01

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

Автор: Michael_Rybak 6.12.2007 22:36

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

Алгоритм - http://www.msclub.ce.cctpu.edu.ru/bibl/ODM/Ll2_5.html по запросу "гамильтонов цикл".

Автор: ОтчаявшийсяПрогер 7.12.2007 0:48

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

Автор: Michael_Rybak 7.12.2007 1:20

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

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

Автор: ОтчаявшийсяПрогер 7.12.2007 15:25

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

Подскажи тогда сначала рандомно вводишь, после этого симметричной делаешь?
К примеру ввел все элементы
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 7.12.2007 18:34

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

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

Автор: ОтчаявшийсяПрогер 8.12.2007 14:30

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

Автор: Michael_Rybak 8.12.2007 16:29

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

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

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

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

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