2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задачка на графы(на си)
Сообщение06.05.2010, 17:05 


06/05/10
1
Дан граф.Нужно найти максимальную длину графа(в какую точку неважно)в вершине можно побывать только один раз.Может кто подскажет как реализовать или у кого код есть.Я облазил гугл но там только задачи на минимальный граф

 Профиль  
                  
 
 Re: Задачка на графы(на си)
Сообщение06.05.2010, 19:19 
Заслуженный участник


26/07/09
1559
Алматы
2artumNax
Видимо вам надо поискать что-нибудь про гамильтоновы пути. Мне почему-то кажется, что для решения вашей задачи вполне можно приспособить обычный волновой алгоритм.

 Профиль  
                  
 
 Re: Задачка на графы(на си)
Сообщение07.05.2010, 01:04 


02/07/08
322
Если имелась в виду максимальная длина ациклического пути в графе, то это NP-полная задача. Если вкратце, пишите перебором.

 Профиль  
                  
 
 Re: Задачка на графы(на си)
Сообщение16.05.2010, 02:25 
Аватара пользователя


01/04/10
910
http://en.wikipedia.org/wiki/Longest_path_problem

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group