Материал из Викиконспекты
| Теорема (Редеи-Камиона (для пути)): |
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Приведем доказательство по индукции по числу вершин. Пусть [math] n [/math] - количество вершин в графе.
База индукции:
Очевидно, для [math] n = 3 [/math] утверждение верно.
Индукционный переход:
Пусть предположение верно для всех турниров с количеством вершин не более [math] n [/math]. Рассмотрим турнир [math] T [/math] с [math] n + 1 [/math] вершинами.
Пусть [math] u [/math] – произвольная вершина турнира [math] T [/math]. Тогда турнир [math] T - u [/math] имеет [math] n [/math] вершин, значит, в нем есть гамильтонов путь [math] P: v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n [/math].
Одно из ребер [math] (u, v_1) [/math] или [math] (v_1, u) [/math] обязательно содержится в [math] T [/math].
- Ребро [math] (u, v_1) \in ET [/math]. Тогда путь [math] u \rightarrow P [/math] - гамильтонов.
- Ребро [math] (u, v_1) \notin ET [/math]. Пусть [math] v_i [/math] - первая вершина пути [math] P [/math], для которой ребро [math] (u, v_i) \in T [/math].
- Если такая вершина существует, то в [math] T [/math] существует ребро [math] (v_{i - 1}, u) [/math] и путь [math] v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n [/math] – гамильтонов.
- Если такой вершины не существует, то путь [math] P \rightarrow u [/math] - гамильтонов.
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d. |
| [math]\triangleleft[/math] |
| Теорема (Редеи-Камиона (для цикла)): |
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Приведем доказательство по индукции по числу вершин. Пусть [math] n [/math] - количество вершин в графе.
База индукции:
Пусть [math] T [/math] - сильно связанный турнир из [math] n \geq 3 [/math] вершин.
| Утверждение: |
В турнире [math] T [/math] есть орцикл длины [math] 3 [/math]. |
| [math]\triangleright[/math] | |
Пусть [math] u [/math] - произвольная вершина турнира [math] T , V_1 = \{ v_1 \in VT | (u, v_1) \in ET \}, V_2 = \{ v_2 \in VT | (v_2, u) \in ET \} [/math].
[math] T [/math] сильно связен, следовательно:
- [math] V_1 \neq \emptyset [/math]
- [math] V_2 \neq \emptyset [/math]
- [math] \exists e = (v'_1, v'_2) \in ET : [/math]
- [math] v'_1 \in V_1 [/math]
- [math] v'_2 \in V_2 [/math]
Цикл [math] P: u \rightarrow v'_1 \rightarrow v'_2 \rightarrow u [/math] - искомый орцикл длины [math] 3 [/math], q.e.d. | | [math]\triangleleft[/math] |
Индукционный переход:
Покажем, что если турнир [math] T [/math] с [math]n[/math] вершинами имеет орцикл [math] S = v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1 [/math] длины [math] k \lt n [/math], то он имеет также орцикл длины [math]k + 1[/math]. Рассмотрим 2 случая:
- Существует такая вершина [math]v_0 \notin S [/math] такая, что найдутся вершины [math]u , w \in S[/math] , такие, что ребра [math] (v_0 , u) , (w , v_0) \in T [/math]. Обозначим за [math]v_1[/math] вершину из [math]S[/math], такую, что ребро [math] ( v_1, v_0 ) \in T [/math]. Пусть [math]v_i[/math] – первая вершина при обходе контура [math]S[/math] из [math]v_1[/math], для которой ребро [math] ( v_0, v_i ) \in T [/math]. Тогда ребро [math](v_{i-1}, v_0)[/math] также содержится в [math]T[/math]. Поэтому [math]v_1v_2...v_{i-1}v_0v_i...v_kv_1[/math] – искомый орцикл длины [math]k+1[/math].
- Пусть такой вершины [math]v_0[/math] нет. Тогда разобьем вершины, не принадлежащие [math]S[/math], на два непересекающихся подмножества [math]W[/math] и [math]Z[/math], где [math]W[/math] - множество таких вершин [math]w[/math] , что ребро [math](v_i, w)[/math] для любого [math]i[/math] содержится в [math]T[/math], а [math]Z[/math] – множество таких вершин [math]z[/math], что ребро [math](z, v_i)[/math] для любого [math]i[/math] содержится в [math]T[/math]. Так как [math]T[/math] сильно связан, то оба множества [math]W[/math] и [math]Z[/math] не пусты и найдется ребро [math] (w', z') \in T [/math] , где [math]w' \in W , z' \in Z[/math]. Тогда [math]v_1 w' z' v_3...v_k v_1[/math] – требуемый орцикл.
Таким образом в любом сильно связанном турнире [math]T[/math] с [math]n[/math] вершинами будет орцикл длины [math]n[/math], то есть гамильтонов цикл. |
| [math]\triangleleft[/math] |
| Лемма (Следствие): |
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл. |
Литература
- Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы
- Ф. Харари: Теория графов
