Задание олимпиады по теории графов: достижимость вершин
Докажите, что на рёбрах связного графа можно так расставить стрелки, чтобы из некоторой вершины можно было добраться по стрелкам до любой другой.
Разобрать решение
Зафиксируем вершину A. Рассмотрим сначала вершины, соединённые с A, затем – новые вершины, соединённые с ними, и т.д. При этом рёбра, соединяющие добавляемые вершины с уже рассмотренными, ориентируем в направлении к новым вершинам.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.