Покрытие рёбер графа путями

2012-03-21T16:12:24Z

95.28.130.202:

Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
{{Теорема|statement=
Пусть <tex>G</tex> {{---}} [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#cite_note-almost-0|почти связный]] граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> реберно простыми путями.
|proof=
[[Файл:Make_edges_paths_1.png|200px|right|thumb|Пример графа для <tex>N = 2</tex>]]

'''Необходимость''' 
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями. 
Добавим в <tex>G</tex> <tex>N</tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> ∉ <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра. 
Тогда цикл <tex>c</tex> распадется на <tex>N</tex> путей, которым будут принадлежать все ребра <tex>G</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_l}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_l}u_{{i+1}_0}</tex> и ребро <tex>u_{k_l}u_{1_0}</tex>. В новом графе появится Эйлеров цикл. Всего будет добавлено <tex>k</tex> ребер, которые изменят четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечетной степени. 
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.

}}

==См. также==
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]

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

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Викиконспекты - Вклад участника [ru]

Покрытие рёбер графа путями