Доказать свойство циклов в графе

@Jmaqasa · Регистрация: 18.10.2016

Author24 — интернет-сервис помощи студентам

Докажите, что если граф содержит цикл от вершины v к самой себе от то он содержит простой цикл от вершины v к самой себе.

@kabenyuk · 24.11.2016, 13:16

Сообщение от Jmaqasa

цикл от вершины v к самой себе

Ну и терминология, прости Господи.
Задача так формулируется. Докажите, что если граф содержит цикл, проходящий через заданную вершину, то он содержит и простой цикл, проходящий через эту же вершину.
Решение - коротко. Выбрасываем кратные вершины в этом цикле вместе с кусками цикла. Но стараемся не выбросить заданную вершину.

@Jmaqasa 0 / 0 / 0 Регистрация: 18.10.2016 Сообщений: 4
		1
	Доказать свойство циклов в графе 22.11.2016, 19:20. Показов 1767. Ответов 1 Метки нет (Все метки) Докажите, что если граф содержит цикл от вершины v к самой себе от то он содержит простой цикл от вершины v к самой себе. 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	24.11.2016, 13:16	2
	Сообщение было отмечено Mysterious Light как решение Решение Сообщение от Jmaqasa цикл от вершины v к самой себе Ну и терминология, прости Господи. Задача так формулируется. Докажите, что если граф содержит цикл, проходящий через заданную вершину, то он содержит и простой цикл, проходящий через эту же вершину. Решение - коротко. Выбрасываем кратные вершины в этом цикле вместе с кусками цикла. Но стараемся не выбросить заданную вершину. 0

Опции темы