Расскажите пожалуйста, как узнать какой это граф: йлеров, полуэйлеров, гамильтонов или полугамильнов, если даны только лишь рисунки.

Просто правила все я выучил, а вот применять на практике не могу.
Подскажите на примерах с рисунками, пожалуйста.

задан 12 Ноя '14 19:13

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

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


9917

Для эйлерова графа всё очень просто: все степени (валентности) вершин должны быть чётны. Это сразу видно. При этом, конечно, граф должен быть связным. Если эйлеровости нет, то может быть полуэйлеровость, когда вершин нечётной степени ровно две, но не больше.

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

(12 Ноя '14 19:23) falcao

Про эйлеров все понятно. Как понять вот эту фразу:

Если гамильтонов цикл есть, то он просто находится и предъявляется. Если его нет, это нужно как-то доказывать?

(12 Ноя '14 19:28) gagarin

@Алексей авт: её именно так и надо понимать как она сказана, то есть буквально. Если граф на самом деле гамильтонов, то надо найти обход "методом проб и ошибок", то есть подбором. Потом Вы нумеруете вершины и предъявляете рисунок. Проверка того, что 1-я вершина соединена со 2-й, 2-я с 3-й и так далее, а последняя с первой, труда не составляет.

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

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

(12 Ноя '14 20:09) falcao

Еще вопрос: может ли граф быть одновременно и эйлеровым и гамильтоновым (как в случае с квадратом, например), а еще какие?

(12 Ноя '14 21:27) gagarin

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

(12 Ноя '14 21:51) falcao

Как доказать то, что есть есть 2 графа.

Один из них граф, а другой его дополнение, как доказать, что один из них связный?

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

@Алексей авт: эту задачу лучше сделать отдельным вопросом. Только надо корректно её сформулировать: имеются в виду, я так понимаю, подграфы полного графа с конечным числом вершин. В принципе, решение здесь простое: это доказывается по индукции.

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

Ваш ответ

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

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

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

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

отмечен:

×649
×146

задан
12 Ноя '14 19:13

показан
563 раза

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

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

по почте:

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

по RSS:

Ответы

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

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