Покрытие рёбер графа путями — различия между версиями
Timur (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]: | ||
{{Теорема|statement= | {{Теорема|statement= | ||
| − | Пусть <tex>G</tex> {{---}} | + | Пусть <tex>G</tex> {{---}} граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|реберно-простыми]] путями. |
|proof= | |proof= | ||
[[Файл:Make_edges_paths_1.png|180px|right|thumb|Пример графа для <tex>N = 2</tex>]] | [[Файл:Make_edges_paths_1.png|180px|right|thumb|Пример графа для <tex>N = 2</tex>]] | ||
| Строка 7: | Строка 7: | ||
'''Необходимость'''<br/> | '''Необходимость'''<br/> | ||
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.<br/> | Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.<br/> | ||
| − | Добавим в <tex>G</tex> <tex>N</tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> | + | Добавим в <tex>G</tex> <tex> N </tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> <tex>\notin</tex> <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра.<br/> |
| − | + | Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: отметим удаленные ребра в порядке их обхода в Эйлеровом цикле. Тогда <tex> c </tex> разбивается на <tex> N </tex> реберно-непересекающихся путей, т.к. каждый такой путь мы можем сопоставить удаленному ребру. Необходимость доказана. | |
| + | |||
'''Достаточность'''<br/> | '''Достаточность'''<br/> | ||
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.<br/> | Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.<br/> | ||
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>.<br/> | Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>.<br/> | ||
| − | Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_l}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_l}u_{{i+1}_0}</tex> и ребро <tex>u_{k_l}u_{1_0}</tex>. В новом графе появится Эйлеров цикл. Всего | + | Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_l}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_l}u_{{i+1}_0}</tex> и ребро <tex>u_{k_l}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>, не существует. | ||
| Строка 21: | Строка 22: | ||
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | * [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | ||
| − | == | + | ==Источники информации== |
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6 | * Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6 | ||
| − | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
| + | [[Категория: Эйлеровы графы]] | ||
Версия 16:45, 14 января 2016
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Теорема: |
Пусть — граф, в котором вершин имеют нечетную степень. Тогда множество ребер можно покрыть реберно-простыми путями. |
| Доказательство: |
|
Необходимость
|
См. также
Источники информации
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
