1632
правки
Изменения
м
==Покрытие ребер графа путями==
'''Необходимость'''<br/>
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями.<br/>
Добавим в <tex>G 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> добавленные ребра.<br/>
Тогда цикл <tex>c</tex> распадется на <tex>N</tex> путей, которым будут принадлежать все ребра <tex>G</tex>.
'''Достаточность'''Рассмотрим связный граф <tex>G,</tex> который содержит <tex>2N</tex> вершин, имеющих нечётную степень. Докажем, что его можно покрыть <tex>N</tex> рёберно-простыми путями.
rollbackEdits.php mass rollback
Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
{{Теорема|statement=
Пусть <tex>G</tex> {{- [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов#cite_note-almost-0|почти }} связный]] граф, в котором <tex>2N</tex> вершин имеют нечетную нечётную [[Основные определения теории графов|степень]]. Тогда множество ребер рёбер <tex>G</tex> можно покрыть <tex>N</tex> реберно [[Основные определения теории графов|рёберно-простыми ]] путями.
|proof=
Добавим в граф <tex>N</tex> рёбер, соединив попарно вершины, имеющие нечётные степени, и получим связный граф <tex>G',</tex> все вершины которого имеют чётную степень. Такой граф удовлетворяет [[Эйлеровость_графов#.D0.9A.D1.80.D0.B8.D1.82.D0.B5.D1.80.D0.B8.D0.B9_.D1.8D.D0.B9.D0.BB.D0.B5.D1.80.D0.BE.D0.B2.D0.BE.D1.81.D1.82.D0.B8|критерию эйлеровости]] и содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него <tex>N</tex> добавленных ребер <tex>G' \backslash G.</tex> Цикл распадётся на <tex>N</tex> путей, которые являются простыми, так как рассматриваемый цикл эйлеров, и покрывают весь граф, поэтому полученное разбиение является искомым.
}}
==См. также==
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфовграфов]]
==Источникиинформации==1* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. Фс англ.Харарии предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. Теория графов— М. Москва, издательство ": Едиториал УРСС", 2003. 2003 г— 296 с.— ISBN 5-354-00301-6 [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Эйлеровы графы]]
