Изменения
Нет описания правки
=== Доказательство построением ===
Возьмём любой из существующих путей между нужными нам вершинами: <mathtex>V_0E_1V_1E_2V_2 ... E_nV_n</mathtex>.
* Алгоритм:
1. Для вершины <mathtex>V_i</mathtex> найдём момент её последнего вхождения в путь – <mathtex>V_j</mathtex>. 2. Удалим отрезок пути от <mathtex>E_{i+1}</mathtex> до <mathtex>V_j</mathtex>, включительно. Получившаяся последовательность вершин и рёбер графа останется путём от <mathtex>V_0</mathtex> до <mathtex>V_n</mathtex>, и в нём вершина <mathtex>V_i</mathtex> будет содержаться ровно один раз.Начнём процесс с вершины <mathtex>V_0</mathtex> и будем повторять его каждый раз для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
=== Альтернативное ===
Предположение:
Пусть он не простой.
Тогда в нём содержатся содержmatатся две одинаковые вершины <mathtex>V_i = V_j</mathtex>, <mathtex>i < j</mathtex>. Удалим из исходного пути отрезок от <mathtex>E_{i+1}</mathtex> до <mathtex>V_j</mathtex>, включительно. Конечная последовательность также будет путём от <mathtex>V_0</mathtex> до <mathtex>V_n</mathtex> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.
}}
