Изменения

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

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

137 байт добавлено, 14:35, 26 февраля 2012
Нет описания правки
Cильно связанный турнир <tex> T </tex> из <tex> n \geq 3 </tex> вершин содержит [[Основные_определения_теории_графов#.D0.9E.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|цикл]] длины <tex> 3 </tex>.
|proof=
[[Файл:cycle_3.png|150px|thumb|right|<tex> S_3 </tex>]]
Пусть <tex> u </tex> - произвольная вершина турнира <tex> T </tex>. Множество вершин <tex> VT - u </tex> распадается на <tex> 2 </tex> непересекающихся множества:
* <tex> V_1 = \{ v_1 \in VT | (v_1, u) \in ET \} </tex>,
* <tex> V_2 = \{ v_2 \in VT | (u, v_2) \in ET \} </tex>.
[[Файл: Redei_kamion_1.png|250px|thumb|center]]
<tex> T </tex> сильно связен, следовательно:
#* <tex> w_1 \in V_1 </tex>,
#* <tex> w_2 \in V_2 </tex>.
[[Файл: Redei_kamion_2.png|250px|thumb|center|<font color=#ED1C24>Красным</font> цветом выделен цикл длины 3]]
 
Цикл <tex> S_3: (u \rightarrow w_2 \rightarrow w_1 \rightarrow u) </tex> - искомый цикл длины <tex> 3 </tex>, q.e.d.
}}
272
правки

Навигация