Условие:
доказать что в любом дереве существует единственный простой путь между любыми двумя вершинами (дерево-связный граф без циклов,другими определениями и свойствами пользоваться нельзя)
Решение:
Рассмотрим дерево, то есть связный граф без циклов. Пусть a и b – две произвольные вершины этого дерева. Шаг 1. Так как граф связный, существует хотя бы один простой путь через ребра, соединяющие a и b. Шаг 2. Предположим для противоречия, что между a и b существует два различных простых пути. Обозначим их за P1 и P2. Шаг 3. Пусть P1 и P2 н...
