Изменения

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

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

47 байт добавлено, 01:10, 27 февраля 2012
Нет описания правки
<tex> S \cap T = \emptyset </tex>.
|proof=
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \rightarrow^{e_j} u_{j + 1} \rightarrow u_{j + 2} \rightarrow \ldots \rightarrow u_n \rightarrow^{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
правки

Навигация