alt text

задан 4 Фев '15 21:43

10|600 символов нужно символов осталось
1

Связный простой граф, у которого степени всех вершин равны 1 или 2, представляет собой либо циклический граф $%C_m$% (при $%m\ge3$%), у которого имеется $%m$% рёбер и $%m$% вершин, либо цепь (линейный граф) $%L_m$% (при $%m\ge2$%), у которого $%m-1$% рёбро и $%m$% вершин (иными словами, это отрезок, разбитый на части).

Поскольку для каждой цепи происходит "потеря" ровно одного ребра, цепей должно быть ровно 5. На них уходит 10 или более вершин. Всё остальное -- это циклы. Располагая не более чем 10 вершинами, мы можем сформировать от 0 до 3 циклов включительно. Поэтому связных компонент будет от 5 до 8. Легко видеть, что все варианты реализуются.

ссылка

отвечен 4 Фев '15 22:27

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,339
×477
×127

задан
4 Фев '15 21:43

показан
512 раз

обновлен
4 Фев '15 22:27

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

по почте:

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

по RSS:

Ответы

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

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