Изменения
Нет описания правки
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – {{---}} путь между ними, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Длина пути''' – {{---}} количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}
* Алгоритм:
1. Для вершины <tex>v_i</tex> найдём момент её последнего вхождения в путь – {{---}} <tex>v_j</tex>.
2. Удалим отрезок пути от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно.
Получившаяся последовательность вершин и рёбер графа останется путём от <tex>v_0</tex> до <tex>v_n</tex>, и в нём вершина <tex>v_i</tex> будет содержаться ровно один раз.
Предположение:
Пусть он не простой.
Тогда в нём содержатся две одинаковые вершины <tex>v_i = v_j</tex>, <tex>i < j</tex>. Удалим из исходного пути отрезок от <tex>e_{i+1}</tex> до <tex>v_j</tex>, включительно. Конечная последовательность также будет путём от <tex>v_0</tex> до <tex>v_n</tex> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – {{---}} простой.
}}
