171
правка
Изменения
Нет описания правки
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – [[Основные определения теории графов|путь]] между ними, в котором каждая из вершин графа встречается не более одного раза.
}}
Предположение:
Пусть он не простой.
Тогда в нём содержmatатся содержатся две одинаковые вершины <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> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.
}}
== Замечания ==
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого пути.
* Теорема может быть сформулирована как для [[Основные определения теории графов|ориентированного]], так и для [[Основные определения теории графов|неориентированного]] графа.
== См. также ==
* [[Основные определения теории графов]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
