Теорема о существовании простого пути в случае существования пути — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{Теорема
 +
|statement=
 +
Если между двумя вершинами графа существует путь, то между ними существует простой путь.
 +
|proof=
 +
Для доказательства этой теоремы введём два определения.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – путь между ними, в котором каждая из вершин графа встречается не более одного раза.
 
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – путь между ними, в котором каждая из вершин графа встречается не более одного раза.
 
}}
 
}}
−
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 9: Строка 13:
 
}}
 
}}
  
−
{{Теорема
+
* Доказательство построением:
−
|statement=
+
 
−
Если между двумя вершинами графа существует путь, то между ними существует простой путь.
+
Возьмём любой из существующих путей <math>V_0E_1V_1E_2V_2 ... E_nV_n</math>.
−
|proof=
+
 
−
Возьмём любой из существующих путей <math>V_0E_1V_1E_2V_2 ... E_nV_n</math>. Для вершины <math>V_i</math> найдём момент её последнего вхождения в путь – <math>V_j</math> – и удалим отрезок пути от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Получившаяся последовательность вершин и рёбер графа останется путём от <math>V_0</math> до <math>V_n</math>, и в нём вершина <math>V_i</math> будет содержаться ровно один раз. Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз  для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
+
Алгоритм:
 +
1. Для вершины <math>V_i</math> найдём момент её последнего вхождения в путь – <math>V_j</math>.
 +
2. Удалим отрезок пути от <math>E_{i+1}</math> до <math>V_j</math>, включительно.
 +
Получившаяся последовательность вершин и рёбер графа останется путём от <math>V_0</math> до <math>V_n</math>, и в нём вершина <math>V_i</math> будет содержаться ровно один раз.
 +
Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз  для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
  
  
 
* Альтернативное:
 
* Альтернативное:
−
Выберем из всех путей между данными вершинами путь наименьшей длины. Пусть он не простой; тогда в нём содержатся две одинаковые вершины <math>V_i</math> и <math>V_j</math>, <math>i < j</math>. Удалим из исходного пути отрезок от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Конечная последовательность также будет путём и станет короче исходной. Значит, исходный путь не был кратчайшим; предположение неверно, выбранный путь – простой.
+
Выберем из всех путей между данными вершинами путь наименьшей длины.
 +
 
 +
Предположение:
 +
Пусть он не простой.
 +
Тогда в нём содержатся две одинаковые вершины <math>V_i = V_j</math>, <math>i < j</math>. Удалим из исходного пути отрезок от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Конечная последовательность также будет путём от <math>V_0</math> до <math>V_n</math> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.
 
}}
 
}}

Версия 00:49, 11 октября 2010

Теорема:
Если между двумя вершинами графа существует путь, то между ними существует простой путь.
Доказательство:
[math]\triangleright[/math]

Для доказательства этой теоремы введём два определения.

Определение:
Простой (вершинно-простой) путь между двумя вершинами графа – путь между ними, в котором каждая из вершин графа встречается не более одного раза.


Определение:
Длина пути – количество вершин, входящих в последовательность, задающую этот путь.


  • Доказательство построением:

Возьмём любой из существующих путей [math]V_0E_1V_1E_2V_2 ... E_nV_n[/math].

Алгоритм: 

1. Для вершины [math]V_i[/math] найдём момент её последнего вхождения в путь – [math]V_j[/math].
2. Удалим отрезок пути от [math]E_{i+1}[/math] до [math]V_j[/math], включительно.
Получившаяся последовательность вершин и рёбер графа останется путём от [math]V_0[/math] до [math]V_n[/math], и в нём вершина [math]V_i[/math] будет содержаться ровно один раз.

Начнём процесс с вершины [math]V_0[/math] и будем повторять его каждый раз для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.


  • Альтернативное:

Выберем из всех путей между данными вершинами путь наименьшей длины.

Предположение: 

Пусть он не простой.
Тогда в нём содержатся две одинаковые вершины [math]V_i = V_j[/math], [math]i \lt j[/math]. Удалим из исходного пути отрезок от [math]E_{i+1}[/math] до [math]V_j[/math], включительно. Конечная последовательность также будет путём от [math]V_0[/math] до [math]V_n[/math] и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_о_существовании_простого_пути_в_случае_существования_пути&oldid=3523»