Изменения

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

Теорема Хватала

Нет изменений в размере, 12:11, 11 марта 2012
Нет описания правки
<tex> S \cap T = \emptyset </tex>.
|proof=
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \rightarrow^xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \rightarrow^xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов.
[[Файл: Hvatal_4.png|400px|thumb|center|]]
Значит, <tex> S \cap T </tex>, q.e.d.
272
правки

Навигация