Изменения
Нет описания правки
==Теорема о существовании простого пути в случае существования пути==
[[Файл:Simple way.png|thumb|250px|center|Ориентированный граф. <font color=#ED1C24>Красным</font> выделен вершинно-простой путь. <font color=#3771c8ff>Синим</font> {{---}} реберно-простой путь.]]
{{Теорема
|statement=
Тогда в нём содержатся две одинаковые вершины <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> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь {{---}} простой.
}}
== Замечания ==
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого пути.
