Теорема Оре — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Если <math>n \ge  3</math> и <math>deg\ u + deg \ v \ge n</math>  для любых двух различных несмежных вершин <math>\ u</math> и <math>\ v</math> неориентированного графа  '''G''', то  '''G''' - гамильтонов граф.
+
Если <tex>n \geqslant 3</tex> и <tex>\operatorname{deg} u + \operatorname{deg} v \geqslant n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> [[Основные определения теории графов#Неориентированные графы|неориентированного графа]] <tex>G</tex>, то  <tex>G</tex> {{---}} [[Гамильтоновы графы | гамильтонов граф]].
  
 
|proof=
 
|proof=
  
−
Пусть, от противного, существует граф '''G''', который удовлетворяет условию теоремы, но не является гамильтоновым графом.
+
Пусть, от противного, существует граф <tex>G</tex>, который удовлетворяет условию теоремы, но не является гамильтоновым графом.
−
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф '''G''''. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
+
Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф <tex>G'</tex>. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.
  
−
Пусть <math>\ u,v</math> несмежные вершины в полученном графе '''G''''. Если добавить ребро <math>\ uv</math>, появится гамильтонов цикл. Тогда путь <math>\ (u,v)</math> - гамильтонов.
+
Пусть <tex>u,v</tex> несмежные вершины в полученном графе <tex>G'</tex>. Если добавить ребро <tex>uv</tex>, появится гамильтонов цикл. Тогда путь <tex>(u,v)</tex> {{---}} гамильтонов.
  
−
Для вершин <math>\ u,v</math> выполнено <math>deg\ u + deg \ v \ge n</math>.
+
Для вершин <tex>u,v</tex> выполнено <tex>\operatorname{deg} u + \operatorname{deg} v \geqslant n.</tex>  
  
−
По принципу Дирихле, всегда найдутся две смежные вершины <math>\ t_1,t_2</math> на пути <math>\ (u,v)</math> ,т.е. <math>\ u..t_1t_2..v</math> , такие, что существует ребро <math>\ ut_2</math> и ребро <math>\ t_1v</math>.
+
По принципу Дирихле всегда найдутся две смежные вершины <tex> t_1,t_2</tex> на пути <tex>(u,v)</tex>, т.е. <tex>u \dots t_1t_2 \dots v</tex> , такие, что существует ребро <tex>ut_2</tex> и ребро <tex>t_1v.</tex>
−
Получили противоречие, т.к. <math>\ u..t_1v..t_2u</math> - гамильтонов цикл.
+
 
 +
Действительно, пусть <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 = \operatorname{deg} u + \operatorname{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: ut_{i+1}\in EG</tex> и <tex> t_iv \in EG.</tex>
 +
Получили противоречие, т. к. <tex>u \dots t_1v \dots t_2u</tex> {{---}} гамильтонов цикл.
 
}}
 
}}
 +
== См. также ==
 +
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
 +
* [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 +
* [[Теорема Дирака]]
 +
== Источники информации ==
 +
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 +
* Харари {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''
 +
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:18, 4 сентября 2022

Теорема:
Если [math]n \geqslant 3[/math] и [math]\operatorname{deg} u + \operatorname{deg} v \geqslant n[/math] для любых двух различных несмежных вершин [math]u[/math] и [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] — гамильтонов граф.
Доказательство:
[math]\triangleright[/math]

Пусть, от противного, существует граф [math]G[/math], который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф [math]G'[/math]. В силу того, что мы только добавляли ребра, условие теоремы не нарушилось.

Пусть [math]u,v[/math] несмежные вершины в полученном графе [math]G'[/math]. Если добавить ребро [math]uv[/math], появится гамильтонов цикл. Тогда путь [math](u,v)[/math] — гамильтонов.

Для вершин [math]u,v[/math] выполнено [math]\operatorname{deg} u + \operatorname{deg} v \geqslant n.[/math]

По принципу Дирихле всегда найдутся две смежные вершины [math] t_1,t_2[/math] на пути [math](u,v)[/math], т.е. [math]u \dots t_1t_2 \dots v[/math] , такие, что существует ребро [math]ut_2[/math] и ребро [math]t_1v.[/math]

Действительно, пусть [math]S=[/math] [math]\{ i \mid e_i=ut_{i+1} \in EG \}[/math] и [math]T = [/math] [math]\{ i \mid f_i=t_iv \in EG \}[/math]

Имеем: [math]\left\vert S \right\vert + \left\vert T \right\vert = \operatorname{deg} u + \operatorname{deg} v \geqslant n [/math], но [math]\left\vert S + T \right\vert \lt n.[/math]

Тогда [math]\left\vert S\cap T \right\vert = \left\vert S \right\vert + \left\vert T \right\vert - \left\vert S+T \right\vert \gt 0[/math], т. е. [math]\exists i: ut_{i+1}\in EG[/math] и [math] t_iv \in EG.[/math]

Получили противоречие, т. к. [math]u \dots t_1v \dots t_2u[/math] — гамильтонов цикл.
[math]\triangleleft[/math]

См. также

Источники информации

  • Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
  • Харари — Теория графов. ISBN 978-5-397-00622-4
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Оре&oldid=84846»