Здравствуйте! Задача такая. Нужно доказать, что граф с более чем одной вершиной связен тогда и только тогда, когда все его вершины лежат на некотором цикле.

задан 23 Сен '19 1:52

@Math_2012: под циклом обычно понимается контур циклического подграфа. Тогда это утверждение неверно -- достаточно взять любое дерево, которым по определению называется связный граф без циклов.

Чтобы все вершины лежали на одном цикле, необходимо и достаточно, чтобы граф был гамильтоновым, но это очевидно в силу определения.

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

Ваш ответ

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

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

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

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

отмечен:

×1,787
×629

задан
23 Сен '19 1:52

показан
241 раз

обновлен
23 Сен '19 2:01

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

по почте:

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

по RSS:

Ответы

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

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