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