Покрытие рёбер графа путями — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (ё)
Строка 1: Строка 1:
 
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
 
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
 
{{Теорема|statement=
 
{{Теорема|statement=
Пусть <tex>G</tex> {{---}}  граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|реберно-простыми]] путями.
+
Пусть <tex>G</tex> {{---}}  граф, в котором <tex>2N</tex> вершин имеют нечётную [[Основные определения теории графов|степень]]. Тогда множество рёбер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|рёберно-простыми]] путями.
 
|proof=
 
|proof=
  
 
'''Необходимость'''
 
'''Необходимость'''
  
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.
+
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> рёберно-простыми путями.
  
Добавим <tex> N </tex> ребер <tex>uv</tex> таких, что степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex> (критерием Эйлеровости графа является отсутствие нечетных вершин в связном мультиграфе).
+
Добавим <tex> N </tex> рёбер <tex>uv</tex> таких, что степени вершин <tex>u</tex> и <tex>v</tex> нечётные. Тогда степени всех вершин станут чётными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex> (критерием Эйлеровости графа является отсутствие нечётных вершин в связном мультиграфе).
  
Удалим из <tex>c</tex> добавленные ребра.
+
Удалим из <tex>c</tex> добавленные рёбра.
Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: возьмем Эйлеров цикл и удалим из него <tex>N</tex> ребер. Теперь полученный граф можно разбить на <tex>N</tex> (или меньше) цепей между этими удаленными ребрами.
+
Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: возьмем Эйлеров цикл и удалим из него <tex>N</tex> рёбер. Теперь полученный граф можно разбить на <tex>N</tex> (или меньше) цепей между этими удалёнными рёбрами.
  
 
'''Достаточность'''
 
'''Достаточность'''
  
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.  
+
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> рёберно-простыми путями.  
  
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>. Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_m}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_m}u_{{i+1}_0}</tex> (соединяют конец предыдущей и начало следующей цепи) и ребро <tex>u_{k_m}u_{1_0}</tex> (соединяет конец последней и начало первой цепей).  
+
Предположим, что такое возможно, и существует набор рёберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все рёбра <tex>G</tex>. Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_m}</tex>. Добавим в <tex>G</tex> все рёбра вида <tex>u_{i_m}u_{{i+1}_0}</tex> (соединяют конец предыдущей и начало следующей цепи) и ребро <tex>u_{k_m}u_{1_0}</tex> (соединяет конец последней и начало первой цепей).  
  
В новом графе появится Эйлеров цикл, т.к. мы добавили ребра, соединяющие конец и начало <tex> i </tex> и <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>k</tex> ребер, которые меняют четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечетной степени, что не удовлетворяет критерию Эйлеровости графа.<br/>
+
В новом графе появится Эйлеров цикл, т.к. мы добавили рёбра, соединяющие конец и начало <tex> i </tex> и <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>k</tex> рёбер, которые меняют чётность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечётной степени, что не удовлетворяет критерию Эйлеровости графа.<br/>
  
 
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.
 
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.

Версия 00:04, 31 января 2017

Следующее утверждение являются следствием из критерия Эйлеровости графа:

Теорема:
Пусть [math]G[/math] — граф, в котором [math]2N[/math] вершин имеют нечётную степень. Тогда множество рёбер [math]G[/math] можно покрыть [math]N[/math] рёберно-простыми путями.
Доказательство:
[math]\triangleright[/math]

Необходимость

Докажем, что [math]G[/math] можно покрыть [math]N[/math] рёберно-простыми путями.

Добавим [math] N [/math] рёбер [math]uv[/math] таких, что степени вершин [math]u[/math] и [math]v[/math] нечётные. Тогда степени всех вершин станут чётными, и в [math]G[/math] появится Эйлеров цикл [math]c[/math] (критерием Эйлеровости графа является отсутствие нечётных вершин в связном мультиграфе).

Удалим из [math]c[/math] добавленные рёбра. Заметим, что теперь цикл распадается на [math] N [/math] простых путей. В самом деле: возьмем Эйлеров цикл и удалим из него [math]N[/math] рёбер. Теперь полученный граф можно разбить на [math]N[/math] (или меньше) цепей между этими удалёнными рёбрами.

Достаточность

Докажем, что [math]G[/math] нельзя покрыть менее, чем [math]N[/math] рёберно-простыми путями.

Предположим, что такое возможно, и существует набор рёберно-простых путей [math]p_1, p_2, ... p_k, k \lt N[/math], такой что он покрывает все рёбра [math]G[/math]. Пусть [math]i-[/math]й путь из этого набора имеет вид [math] w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_m}[/math]. Добавим в [math]G[/math] все рёбра вида [math]u_{i_m}u_{{i+1}_0}[/math] (соединяют конец предыдущей и начало следующей цепи) и ребро [math]u_{k_m}u_{1_0}[/math] (соединяет конец последней и начало первой цепей).

В новом графе появится Эйлеров цикл, т.к. мы добавили рёбра, соединяющие конец и начало [math] i [/math] и [math] i + 1 [/math] пути соответственно. Всего добавлено [math]k[/math] рёбер, которые меняют чётность не более, чем [math]2k[/math] вершин. Т.к. [math]k \lt N[/math], то в графе останутся вершины нечётной степени, что не удовлетворяет критерию Эйлеровости графа.

Противоречие. Значит, такого набора, что его мощность меньше [math]N[/math], не существует.
[math]\triangleleft[/math]

См. также

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

  • Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6