Материал из Викиконспекты
| Теорема (Редеи-Камиона (для пути)): |
|
| Доказательство: |
| [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] - количество вершин в графе.
База индукции:
| Утверждение: |
Cильно связанный турнир [math] T [/math] из [math] n \geq 3 [/math] вершин содержит цикл длины [math] 3 [/math]. |
| [math]\triangleright[/math] | |
Пусть [math] u [/math] - произвольная вершина турнира [math] T [/math]. Множество вершин [math] VT - u [/math] распадается на [math] 2 [/math] непересекающихся множества:
- [math] V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} [/math],
- [math] V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} [/math].
[math] T [/math] сильно связен, следовательно:
- [math] V_1 \neq \emptyset [/math], иначе у турнира существует исток.
- [math] V_2 \neq \emptyset [/math], иначе у турнира существует сток.
- [math] \exists e = (w_2, w_1) \in ET [/math]:
- [math] w_1 \in V_1 [/math],
- [math] w_2 \in V_2 [/math].
Цикл [math] S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) [/math] - искомый цикл длины [math] 3 [/math], q.e.d. | | [math]\triangleleft[/math] |
Индукционный переход:
| Утверждение: |
Если сильно связанный турнир [math] T [/math] из [math] n \geq 3 [/math] вершин содержит цикл [math] S_k [/math] длины [math] k [/math], то он содержит и цикл длины [math] k + 1 [/math]. |
| [math]\triangleright[/math] | |
Пусть [math] S_k = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) [/math].
Пусть [math] v_0 \notin S_k [/math] такая, что [math] \exists u, w \in S_k [/math]:
- [math] (v_0, u) \in ET [/math],
- [math] (w, v_0) \in ET [/math].
Рассмотрим два случая:
- существует такая вершина [math] v_0 [/math],
- не существует такой вершины [math] v_0 [/math].
Первый случай:
 [math] S_{k + 1} в первом случае. [/math] - Пусть [math] v_1 [/math] - вершина из [math] S_k [/math] такая, что ребро [math] e = (v_1, v_0 ) \in ET [/math]. Пусть [math] v_i [/math] – первая вершина при обходе [math] S_k [/math] из [math] v_1 [/math], для которой ребро [math] f = (v_0, v_i ) \in ET [/math].
- Тогда ребро [math] g = (v_{i - 1}, v_0) \in ET [/math].
- Тогда [math] S_{k + 1} = (v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow v_0 \rightarrow v_i \rightarrow \ldots \rightarrow v_k \rightarrow v_1) [/math] – искомый цикл длины [math] k + 1 [/math].
Второй случай:
 [math] S_{k + 1} во втором случае. [/math] - Пусть:
- [math] V_1 = \{ u \in VT | u \notin S, e = (u, v_i) \in ET, \forall i = \overline{1, n} \} [/math],
- [math] V_2 = \{ u \in VT | u \notin S, f = (v_i, u) \in ET, \forall i = \overline{1, n} \} [/math].
- Тогда [math] V_1 \cap V_2 = \emptyset [/math].
- Турнир сильно связен, следовательно:
- [math] V_1 \neq \emptyset [/math],
- [math] V_2 \neq \emptyset [/math],
- [math] \exists g = (w_2, w_1) \in T: [/math]
- [math] w_1 \in V_1 [/math],
- [math] w_2 \in V_2 [/math].
- Тогда [math] S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) [/math] – искомый цикл длины [math] k + 1 [/math].
Цикл [math] S_{k + 1} [/math] - искомый цикл длины [math] k + 1 [/math], q.e.d. | | [math]\triangleleft[/math] |
Таким образом, в любой сильно связанный турнир [math] T [/math] из [math] n \geq 3 [/math] вершин содержит цикл длины [math] n [/math], то есть гамильтонов цикл, q.e.d. |
| [math]\triangleleft[/math] |
| Лемма (Следствие): |
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл. |
- Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы
- Ф. Харари: Теория графов
