Изменения

Перейти к: навигация, поиск

Теорема Редеи-Камиона

Нет изменений в размере, 21:18, 23 апреля 2012
Нет описания правки
Одно из ребер <tex> (u, v_1) </tex> или <tex> (v_1, u) </tex> обязательно содержится в <tex> T </tex>.
Если ребро <tex> (u, v_1) \in ET </tex>, то путь <tex> (u \rightarrow P) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен искомый путь]]
Пусть теперь ребро <tex> (u, v_1) \notin ET, v_i </tex> {{---}} первая вершина пути <tex> P </tex>, для которой ребро <tex> (u, v_i) \in T </tex>.
Если такая вершина существует, то в <tex> T </tex> существует ребро <tex> (v_{i - 1}, u) </tex> и путь <tex> (v_1 \rightarrow \ldots \rightarrow v_{i - 1} \rightarrow u \rightarrow v_i \rightarrow \ldots v_n) </tex> – гамильтонов.
[[Файл: Redei_kamion_3.png|250px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен искомый путь]]
Если такой вершины не существует, то путь <tex> (P \rightarrow u) </tex> {{---}} гамильтонов.
[[Файл: Redei_kamion_4.png|250px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен искомый путь]]
Значит, в любом случае в турнире существует гамильтонов путь, q.e.d.
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_6.png|350px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен цикл длины <tex> 3 </tex>]]
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> {{---}} искомый цикл длины <tex> 3 </tex>, q.e.d.
Тогда ребро <tex> g = (v_{i - 1}, v_0) \in ET </tex>.
[[Файл: Redei_kamion_8.png|250px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен искомый цикл длины <tex> k + 1 </tex> ]]
Тогда <tex> 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) </tex> – искомый цикл длины <tex> k + 1 </tex>.
** <tex> w_1 \in V_1 </tex>,
** <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_10.png|350px|thumb|center|<font color=#ED1C24ff2a2a>Красным</font> цветом выделен цикл длины <tex> k + 1 </tex>]]
Тогда <tex> S_{k + 1} = (v_1 \rightarrow w_2 \rightarrow w_1 \rightarrow v_3 \rightarrow \ldots \rightarrow v_k \rightarrow v_1) </tex> – искомый цикл длины <tex> k + 1 </tex>.
272
правки

Навигация