Теорема Оре — различия между версиями
| Строка 1: | Строка 1: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Если <tex>n \ | + | Если <tex>n \geqslant 3</tex> и <tex>deg\ u + deg\ v \geqslant n</tex> для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов#Неориентированные графы|неориентированного графа]] <tex>G</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы | гамильтонов граф]]. |
|proof= | |proof= | ||
| Строка 10: | Строка 10: | ||
Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов. | Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов. | ||
| − | Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \ | + | Для вершин <tex>u,v</tex> выполнено <tex>deg\ u + deg\ v \geqslant n.</tex> |
По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex> | По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u..t_1t_2..v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex> | ||
| − | Действительно, пусть <tex>S=</tex> | + | Действительно, пусть <tex>S=</tex> <tex>\{ i \mid e_i=ut_{i+1} \in EG \}</tex> и <tex>T = </tex> <tex>\{ i \mid f_i=t_iv \in EG \}</tex> |
| − | Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg\ v \ | + | Имеем: <tex>\left\vert S \right\vert + \left\vert T \right\vert = deg\ u + deg\ v \geqslant n </tex>, но <tex>\left\vert S + T \right\vert < n.</tex> |
| − | Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex> т.е. <tex>\exists i | + | Тогда <tex>\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert > 0</tex>, т. е. <tex>\exists i \mid ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex> |
| − | Получили противоречие, т.к. <tex>u..t_1v..t_2u</tex> {{---}} гамильтонов цикл. | + | Получили противоречие, т. к. <tex>u..t_1v..t_2u</tex> {{---}} гамильтонов цикл. |
}} | }} | ||
| − | + | == См. также == | |
| + | * [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | ||
| + | * [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] | ||
| + | * [[Теорема Дирака]] | ||
== Источники == | == Источники == | ||
| − | + | * Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' | |
| − | + | * Харари {{---}} Теория графов. '''ISBN 978-5-397-00622-4''' | |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
Версия 20:28, 12 января 2015
| Теорема: |
Если и для любых двух различных несмежных вершин и неориентированного графа , то — гамильтонов граф. |
| Доказательство: |
|
Пусть, от противного, существует граф , который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф . В силу того, что мы только добавляли ребра, условие теоремы не нарушилось. Пусть несмежные вершины в полученном графе . Если добавить ребро , появится гамильтонов цикл. Тогда путь — гамильтонов. Для вершин выполнено По принципу Дирихле всегда найдутся две смежные вершины на пути , т.е. , такие, что существует ребро и ребро Действительно, пусть и Имеем: , но Тогда , т. е. и Получили противоречие, т. к. — гамильтонов цикл. |
См. также
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Дирака
Источники
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
- Харари — Теория графов. ISBN 978-5-397-00622-4
