Изменения

Докажем,что в любом турнире есть гамильтонов путь Приведем доказательство по индукции по числу вершин . Пусть <tex>n</tex>- количество вершин в графе.

<u> ''База индукции:'' <br> Очевидно, для <tex>n = 3</texu> утверждение верно.

Очевидно, для <tex> n = 3 </tex> утверждение верно. <u> ''Индукционный переход:'' <br/u> Предположим, что теорема верна  Пусть предположение верно для всех турниров с количеством вершин не более <tex>n</tex> вершинами. Рассмотрим турнир <tex>T</tex> с <tex>n + 1</tex> вершинами.  Пусть <tex>v_0u </tex> – произвольная вершина турнира <tex>T</tex>. Тогда турнир <tex>T</tex> – <tex>v_0- u </tex> имеет <tex>n</tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_n</tex> . Одно из ребер ( <tex>v_0</tex>(u, <tex>v_1) </tex> ) или ( <tex>(v_1</tex>, <tex>v_0u) </tex> ) обязательно содержится в <tex>T</tex>. Рассмотрим 3 случая: # Ребро <tex> ( v_0u, v_1 ) \in T ET </tex>. Тогда путь <tex>v_0v_1v_2...v_nu \rightarrow P </tex> является гамильтоновым- гамильтонов. # Ребро <tex> ( v_0u, v_1 ) \notin T ET </tex>. Обозначим через Пусть <tex>v_i</tex> первую вершину - первая вершина пути <tex>P</tex>, для которой ребро <tex> ( v_0u, v_i ) \in T </tex>,если .## Если такая вершина есть. Тогда существует, то в <tex>T</tex> существует ребро ( <tex>(v_{i-1}</tex>, <tex>v_0u) </tex> ) <br> и путь <tex>v_1...\rightarrow \ldots \rightarrow v_{i-1}v_0v_i...\rightarrow u \rightarrow v_i \rightarrow \ldots v_n</tex>– гамильтонов. ## Если такой вершины <tex>v_i</tex> нетне существует, тогда гамильтоновым путем будет то путь <tex>v_1v_2...v_nv_0P \rightarrow u </tex>- гамильтонов.ИтакЗначит, в любом случае в турнире существует гамильтонов путь, q.e.d.

==Литература==* ХарариАсанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''* Ф. Харари: ''Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009''