Покрытие рёбер графа путями — различия между версиями
м (переименовал Покрытие ребер графа путями в Покрытие рёбер графа путями) |
м (ё) |
||
| Строка 1: | Строка 1: | ||
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | ||
{{Теорема|statement= | {{Теорема|statement= | ||
| − | Пусть <tex>G</tex> {{---}} граф, в котором <tex>2N</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> 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>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> 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
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Теорема: |
Пусть — граф, в котором вершин имеют нечётную степень. Тогда множество рёбер можно покрыть рёберно-простыми путями. |
| Доказательство: |
|
Необходимость Докажем, что можно покрыть рёберно-простыми путями. Добавим рёбер таких, что степени вершин и нечётные. Тогда степени всех вершин станут чётными, и в появится Эйлеров цикл (критерием Эйлеровости графа является отсутствие нечётных вершин в связном мультиграфе). Удалим из добавленные рёбра. Заметим, что теперь цикл распадается на простых путей. В самом деле: возьмем Эйлеров цикл и удалим из него рёбер. Теперь полученный граф можно разбить на (или меньше) цепей между этими удалёнными рёбрами. Достаточность Докажем, что нельзя покрыть менее, чем рёберно-простыми путями. Предположим, что такое возможно, и существует набор рёберно-простых путей , такой что он покрывает все рёбра . Пусть й путь из этого набора имеет вид . Добавим в все рёбра вида (соединяют конец предыдущей и начало следующей цепи) и ребро (соединяет конец последней и начало первой цепей). В новом графе появится Эйлеров цикл, т.к. мы добавили рёбра, соединяющие конец и начало и пути соответственно. Всего добавлено рёбер, которые меняют чётность не более, чем вершин. Т.к. , то в графе останутся вершины нечётной степени, что не удовлетворяет критерию Эйлеровости графа. |
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
