Пусть у графа 12 ребер (каждое кратности 2, без петель) и 7 вершин

Докажите, что у графа есть Эйлеров цикл

задан 7 Апр 21:42

Если граф связен, то это очевидно. Но здесь связность не следует ниоткуда: возьмём два треугольника и одну изолированную вершину. Рёбра удвоим.

(7 Апр 22:54) falcao
1

@falcao, видимо количество ребер дано без учета кратности. Тогда если есть 2 компоненты связности 2+5 или 3+4, то ребер не хватает. С изолированными вершинами или 3 компонентами связности ребер еще меньше.

(7 Апр 23:51) spades

@spades: а что тогда означает информация о рёбрах кратности 2?

Видимо, имелся в виду сначала простой граф с 12 рёбрами, и доказательство того, что он связен. А потом уже рёбра удваивались. Но это как-то слишком уже "мудрёно" для меня. Я бы до такого "изыска" не догадался.

(8 Апр 0:25) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,699

задан
7 Апр 21:42

показан
49 раз

обновлен
8 Апр 0:25

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

по почте:

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

по RSS:

Ответы

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

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