Изменения

Перейти к: навигация, поиск

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

224 байта убрано, 23:01, 16 марта 2012
Отмена правки 19561 участника Русин Никита (обсуждение)
Пусть <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>]]
 
'''Необходимость'''<br/>
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями.<br/>
Добавим в <tex>G</tex> <tex>N</tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> &notin; <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>.
<br clear="all"/>
 
[[Файл:Make_edges_paths_2.png|200px|right|thumb|Пример графа для <tex>N = 3</tex>]]
'''Достаточность'''<br/>
147
правок

Навигация