105
правок
Изменения
Нет описания правки
'''Необходимость'''<br/>
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми цепями.<br/>
Добавим в <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> добавленные ребра.<br/>
Тогда цикл <tex>c</tex> распадется на <tex>N</tex> путей, которым будут принадлежать все ребра <tex>G</tex>.
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.<br/>
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>.<br/>
Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u</tex><sub><tex>u_{i_0</tex></sub> <tex> } \rightarrow u</tex><sub><tex>u_{i_0</tex></sub> <tex>u</tex><sub><tex>}u_{i_1</tex></sub> <tex> } \rightarrow u</tex><sub><tex>u_{i_1</tex></sub> <tex> } \rightarrow ... \rightarrow u</tex><sub><tex>u_{i_l}</tex></sub>. Добавим в <tex>G</tex> все ребра вида <tex>u</tex><sub><tex>u_{i_l</tex></sub> <tex>u</tex><sub><tex>(}u_{{i+1)}_0}</tex></sub> и ребро <tex>u</tex><sub><tex>u_{k_l</tex></sub> <tex>u</tex><sub><tex>}u_{1_0}</tex></sub>. В новом графе появится Эйлеров цикл. Всего будет добавлено <tex>k</tex> ребер, которые изменят четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечетной степени.<br/>
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.
