Задача 30822

Темы:    [ Ориентированные графы ] [ Неопределено ]

Сложность: 3 Классы: 7,8

Условие

Докажите, что на рёбрах связного графа можно так расставить стрелки, чтобы из некоторой вершины можно было добраться по стрелкам до любой другой.

Решение

Зафиксируем вершину A. Рассмотрим сначала вершины, соединённые с A, затем – новые вершины, соединённые с ними, и т.д. При этом рёбра, соединяющие добавляемые вершины с уже рассмотренными, ориентируем в направлении к новым вершинам.

Источники и прецеденты использования

книга
Автор	Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания	1994
Название	Ленинградские математические кружки
Издательство	Киров: "АСА"
Издание	1
глава
Номер	13
Название	Графы-2
Тема	Теория графов
задача
Номер	044