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

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

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

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

Гамильтонов цикл
Здравствуйте! Помогите пожалуйста решить задачку.
Проверить существует ли среди связных графов имеющих 47 ребер и 25 вершин, их которых 21 вершина имеют степень 4, а три вершины имеют степень три, Гамильтонов цикл? Если существует, указать его, в противном случае дать обоснованный ответ его отсутствия
  #2  
Старый 11.06.2010, 07:06
Пользователь

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

графа не существует
Сообщение от гость Посмотреть сообщение
а три вершины имеют степень три
В графе не может быть нечетного количества вершин нечетной степени. Поэтому графа с указанными характеристиками по-просту не существует.

И вообще: 25 не равно 21 + 3
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Граф Эйлеров или Гамильтонов? Таня Графы 1 18.06.2009 18:47
Гамильтонов цикл в графе гость Графы 6 27.05.2009 00:50
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Цикл гость Графы 1 17.06.2008 20:47
цикл fox Графы 1 09.12.2006 20:45