2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Граф Петерсена и его негамильтоновость
Сообщение22.12.2013, 21:26 
Аватара пользователя


17/10/13
790
Деревня
Здравствуйте! Вопрос такой: как доказать, что этот граф негамильтонов? Как я понял, проверить теорему Хватала не достаточно..Что тут нужно сделать?

 Профиль  
                  
 
 Re: Граф Петерсена и его негамильтоновость
Сообщение22.12.2013, 22:07 
Заслуженный участник


23/07/08
10626
Crna Gora
Не знаю. Но могу вывести это, опираясь на то, что хроматический класс графа Петерсена равен 4.

В графе Петерсена 10 вершин и 15 ребер. Гамильтонов цикл (если он есть) содержит 10 ребер. Раскрасим их поочередно (в порядке движения по циклу) в красный и зеленый цвет. Остальные 5 ребер, не принадлежащих циклу, покрасим в синий цвет. В каждой вершине соединяются 3 ребра. Так как каждая вершина проходится один раз, ей инцидентно одно красное и одно зеленое ребро, а также одно синее, не участвующее в обходе. Но тогда мы получим трехцветную реберную раскраску, тогда как сам Петерсен доказал, что это невозможно.

 Профиль  
                  
 
 Re: Граф Петерсена и его негамильтоновость
Сообщение22.12.2013, 22:52 
Заслуженный участник


14/03/10
867
еще можете тут посмотреть topic79189.html

 Профиль  
                  
 
 Re: Граф Петерсена и его негамильтоновость
Сообщение22.12.2013, 23:18 
Аватара пользователя


17/10/13
790
Деревня
svv в сообщении #804908 писал(а):
Не знаю. Но могу вывести это, опираясь на то, что хроматический класс графа Петерсена равен 4.

В графе Петерсена 10 вершин и 15 ребер. Гамильтонов цикл (если он есть) содержит 10 ребер. Раскрасим их поочередно (в порядке движения по циклу) в красный и зеленый цвет. Остальные 5 ребер, не принадлежащих циклу, покрасим в синий цвет. В каждой вершине соединяются 3 ребра. Так как каждая вершина проходится один раз, ей инцидентно одно красное и одно зеленое ребро, а также одно синее, не участвующее в обходе. Но тогда мы получим трехцветную реберную раскраску, тогда как сам Петерсен доказал, что это невозможно.

Спасибо, всё доступно и понятно. Вопрос только в том, что означает число 4? Количество цветов, такие что при определенной раскраске ни один не будет соприкасаться с другим?

 Профиль  
                  
 
 Re: Граф Петерсена и его негамильтоновость
Сообщение23.12.2013, 00:08 
Заслуженный участник


23/07/08
10626
Crna Gora
Да. При определении хроматического числа раскрашивают вершины, чтобы смежные были разных цветов, а при определении хроматического класса (а здесь речь о нем) — ребра. Ребра, встречающиеся в любой вершине, должны быть разных цветов. И Петерсон показал (как — не знаю), что трех цветов для ребер барона графа Петерсона недостаточно.

 Профиль  
                  
 
 Re: Граф Петерсена и его негамильтоновость
Сообщение23.12.2013, 00:14 
Аватара пользователя


17/10/13
790
Деревня
Щас посидел, подумал...Вроде придумал другое решение: рассмотреть точку на внешнем пятиугольнике и рассмотреть два случая: удалить ребро ведущее в центр или удалить ребро идущее по внешнему пятиугольнику (их два, однако такие случаи идентичны). Далее будет ещё разветвление на два простых случая, которые ведут к не гамильтоновым циклам.

-- 23.12.2013, 02:03 --

Про разветвелния на два случая - это я, конечно, погорячился.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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