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