Теорема Редеи-Камиона — различия между версиями
Kirelagin (обсуждение | вклад) (Бред) |
|||
Строка 8: | Строка 8: | ||
''База индукции:'' <br> Очевидно, для <tex>n = 3</tex> утверждение верно. | ''База индукции:'' <br> Очевидно, для <tex>n = 3</tex> утверждение верно. | ||
− | ''Индукционный переход:'' <br> Предположим, что теорема верна для всех турниров с <tex>n</tex> вершинами. Рассмотрим турнир <tex>T</tex> с <tex>n + 1</tex> вершинами. Пусть <tex>v_0</tex> – произвольная вершина турнира <tex>T</tex>. Тогда турнир <tex>T</tex> – <tex>v_0</tex> имеет <tex>n</tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...v_n</tex> . Одно из ребер ( <tex>v_0</tex>, <tex>v_1</tex> ) или ( <tex>v_n</tex>, <tex>v_0</tex> ) обязательно содержится в <tex>T</tex>. Рассмотрим 3 случая: | + | ''Индукционный переход:'' <br> Предположим, что теорема верна для всех турниров с <tex>n</tex> вершинами. Рассмотрим турнир <tex>T</tex> с <tex>n + 1</tex> вершинами. Пусть <tex>v_0</tex> – произвольная вершина турнира <tex>T</tex>. Тогда турнир <tex>T</tex> – <tex>v_0</tex> имеет <tex>n</tex> вершин, значит, в нем есть гамильтонов путь <tex>P</tex>: <tex>v_1v_2...v_n</tex> . <!-- [Ох, неужели??] Одно из ребер ( <tex>v_0</tex>, <tex>v_1</tex> ) или ( <tex>v_n</tex>, <tex>v_0</tex> ) обязательно содержится в <tex>T</tex>. --> Рассмотрим 3 случая: |
# Ребро <tex> ( v_0, v_1 ) \in T </tex>. Тогда путь <tex>v_0v_1v_2...v_n</tex> является гамильтоновым. | # Ребро <tex> ( v_0, v_1 ) \in T </tex>. Тогда путь <tex>v_0v_1v_2...v_n</tex> является гамильтоновым. | ||
# Ребро <tex> ( v_0, v_1 ) \notin T </tex>. Обозначим через <tex>v_i</tex> первую вершину пути <tex>P</tex>, для которой ребро <tex> ( v_0, v_i ) \in T </tex>,если такая вершина есть. Тогда в <tex>T</tex> существует ребро ( <tex>v_{i-1}</tex>, <tex>v_0</tex> ) <br> и путь <tex>v_1...v_{i-1}v_0v_i...v_n</tex>– гамильтонов. | # Ребро <tex> ( v_0, v_1 ) \notin T </tex>. Обозначим через <tex>v_i</tex> первую вершину пути <tex>P</tex>, для которой ребро <tex> ( v_0, v_i ) \in T </tex>,если такая вершина есть. Тогда в <tex>T</tex> существует ребро ( <tex>v_{i-1}</tex>, <tex>v_0</tex> ) <br> и путь <tex>v_1...v_{i-1}v_0v_i...v_n</tex>– гамильтонов. |
Версия 20:26, 23 января 2011
Теорема (Теорема Редеи-Камиона для пути): |
В любом турнире есть гамильтонов путь. |
Доказательство: |
Докажем,что в любом турнире есть гамильтонов путь по индукции по числу вершин .База индукции: Индукционный переход:
|
Теорема (Теорема Редеи-Камиона для цикла): |
В любом сильно связанном турнире есть гамильтонов цикл. |
Доказательство: |
Докажем, что в любом сильно связанном турнире есть гамильтонов цикл, по индукции по длине цикла. База индукции: Индукционный переход:
|
Следствие
Турнир является сильно связанным тогда и только тогда, когда он имеет гамильтонов цикл.
Литература
- Харари, Ф. Теория графов. — М.: Книжный дом «ЛИБРОКОМ», 2009