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