Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 10.10.2009, 21:27
гость

 
Сообщений: n/a

Число Гамильтоновых циклов
Привет, подскажите как найти Число Гамильтоновых циклов, не через алгоритмы.. а просто зная количество вершин, ребер и связности... Возможно через матрицу смежности?
  #2  
Старый 10.10.2009, 23:22
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Привет, подскажите как найти Число Гамильтоновых циклов, не через алгоритмы.. а просто зная количество вершин, ребер и связности... Возможно через матрицу смежности?
Ну что значит не через алгоритмы? Вопрос лишен смысла.

А через алгоритм - да запросто, берешь и запускаешь рекурсивный перебор. Если вопрос заключается в том, можно ли как-то быстрее, без перебора, отвечаю: есть подозрение что это #P-полная задача (ну, как минимум не легче NP-полные задачи), так что как это сделать быстро (за полином от размера матрицы) пока никто не знает, возможно что вообще невозможно.
  #3  
Старый 11.10.2009, 13:17
гость

 
Сообщений: n/a

Мне препод сказал что должна быть какая то формула. Ну судя по всему придется с ней спорить)
  #4  
Старый 11.10.2009, 18:28
гость

 
Сообщений: n/a

Есть формула (и даже не одна) для n-го простого числа - http://en.wikipedia.org/wiki/Formula...oor_functi on
Но их никто не использует, они не практичны. Даже в теории. Что, легче стало, от этого факта?

Впрочем, что-то вроде формулы Миллса (см. ссылку выше), для твоей задачи, думаю, наверняка можно придумать
  #5  
Старый 12.10.2009, 12:06
гость

 
Сообщений: n/a

Может в каком то плане это поможет
http://www.mathnet.ru/php/getFT.phtm...ion_ lang=rus
но здесь даются нижние оценки для определенного типа графа
  #6  
Старый 13.10.2009, 00:28
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

Сообщение от гость Посмотреть сообщение
Возможно через матрицу смежности?
Возможно, если привлечь принцип включений-исключений. Вот здесь есть реализация этой формулы на PARI/GP: http://www.cse.sc.edu/~maxal/gpscripts/
  #7  
Старый 04.11.2009, 14:37
гость

 
Сообщений: n/a

есть формула
Если граф сильно связан то есть полный то число циклов равно |V|! вроде
  #8  
Старый 04.11.2009, 14:43
гость

 
Сообщений: n/a

хм
Ребята а вообще если постановку переформулировать вот так:
Дан неориентированный граф не полный но связанный
то каково количество Гамильтоновых путей в нем?

ну еще стоит добавить для уточнения что дано, количество вершин, количество ребер и как эти ребра соединены, как подсчитать количество путей за не экспоненциальное время? желательно по формуле за О(1)?

при этом сами пути выводить не нужно!
  #9  
Старый 04.11.2009, 18:49
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Если граф сильно связан то есть полный то число циклов равно |V|! вроде
в полном да, но сильно-связный - не значит полный
  #10  
Старый 04.11.2009, 18:53
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Ребята а вообще если постановку переформулировать вот так:
Дан неориентированный граф не полный но связанный
то каково количество Гамильтоновых путей в нем?

ну еще стоит добавить для уточнения что дано, количество вершин, количество ребер и как эти ребра соединены, как подсчитать количество путей за не экспоненциальное время? желательно по формуле за О(1)?

при этом сами пути выводить не нужно!
Задача - опрделить, есть ли хотя бы один гамильтоновый путь или нет, является классическим примером NP-сложной задачи. Делайте выводы.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск длин всех возможныц циклов в ориентированном графе chtoosha Графы 4 22.07.2009 14:42
Отрисовка орграфа по матрице циклов Даниил Ярославцев Графы 2 12.05.2009 10:45
поиск циклов в неориентированном графе giena Графы 1 26.01.2009 05:45
кто автор алгоритма для поиска всех циклов в ориентированном графе njuri Графы 4 26.12.2008 10:42
Нахождение множества элементарных циклов графа kilobait Графы 9 17.03.2008 10:02