По теореме Оре следует, что если пусть $%p$% — количество вершин в данном графе и $%p>2$%. Если для любой пары несмежных вершин $%(x, y)$% выполнено неравенство $%\deg x + \deg y\geqslant p$%, то данный граф — Гамильтонов (другими словами: сумма степеней любых двух несмежных вершин не меньше общего числа вершин в графе). Но как тогда получилось, что додекаидр это тоже Гамильтон граф, если любая его вершина имеет степень $%3$%, и получается $%3+3\geqslant 20$%. Это неверно. Но тем не менее граф Гамильтонов?

задан 12 Ноя '14 1:06

изменен 15 Ноя '14 12:53

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Вы спутали прямое и обратное утверждение. Теорема Оре даёт только достаточное условие гамильтоновости. Необходимым оно не является, и ещё более простой пример -- это циклический граф. В нём кроме гамильтонова цикла ничего нет, а валентности всех вершин равны двум. Понятно, что условиям теоремы Оре он не удовлетворяет. Это значит, что гамильтоновость графов совершенно не обязательно устанавливать по теореме Оре: она охватывает лишь некоторую их часть. А для других графов можно использовать, например, определение.

(12 Ноя '14 1:12) falcao

Если дан граф в виде треугольника и рядом расположены 3 изолированные вершины, то почему этот граф называется эйлеровым? Нам так сказали на лекции.

(13 Ноя '14 1:07) gagarin

@Алексей авт: это чисто формальный момент. Если говорить о графах, в которых есть эйлеров цикл, содержащий все рёбра, то изолированные вершины этому свойству не мешают. Но если их удалить, то оставшаяся часть будет связным графом.

(13 Ноя '14 2:01) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×655
×149

задан
12 Ноя '14 1:06

показан
420 раз

обновлен
13 Ноя '14 2:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru