Автор Тема: Граф Петерсена  (Прочитано 810 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Student

  • Пользователь
  • Сообщений: 33
    • Просмотр профиля
Граф Петерсена
« : Июнь 09, 2016, 05:57:34 am »
Все смог решить , а это читая лит-ру не смог.  :'(


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

Оффлайн Student

  • Пользователь
  • Сообщений: 33
    • Просмотр профиля
Re: Граф Петерсена
« Ответ #1 : Июнь 09, 2016, 11:42:15 pm »
Лучший способ это перебором ,и проверять нет ли циклов меньше 4.
Но как это написать в тетрадь , не имею представления)
 

Оффлайн Student

  • Пользователь
  • Сообщений: 33
    • Просмотр профиля
Re: Граф Петерсена
« Ответ #2 : Июнь 10, 2016, 12:28:58 am »
Собрал в кучу , все что прочитал. (есть копипаст)

У графа Петерсена нет никакого гамильтонова цикла C, описываем 3-регулярные графы с десятью вершинами, которые действительно имеют гамильтонов цикл и показывают, что ни один из них не граф Петерсена, находя цикл в каждом из них, который короче чем любой цикл в графе Петерсена. Любой гамильтонов 3-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами C плюс пять аккордов. Если какой-либо аккорд соединяет две вершины на расстоянии два или три вдоль C друг от друга, граф имеет с 3 циклами или с 4 циклами, и поэтому не может быть графом Петерсена. Если два аккорда соединяют противоположные вершины C к вершинам на расстоянии четыре вдоль C, есть снова с 4 циклами. Так как у графа Петерсена есть обхват пять, это не может быть сформировано таким образом и не имеет никакого гамильтонова цикла.