Покрытие ребер графа путями
Следующее утверждение являются следствием из критерия Эйлеровости графа:
| Теорема: |
Пусть [math]G[/math] - почти связный граф, в котором [math]2N[/math] вершин имеют нечетную степень. Тогда множество ребер [math]G[/math] можно покрыть [math]N[/math] реберно простыми путями. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Необходимость
Докажем, что [math]G[/math] можно покрыть [math]N[/math] реберно-простыми цепями.
Добавим в [math]G N[/math] ребер [math]uv[/math] таки, что [math]uv[/math] ∉ [math]G[/math] и степени вершин [math]u[/math] и [math]v[/math] нечетные. Тогда степени всех вершин станут четными, и в [math]G[/math] появится Эйлеров цикл [math]c[/math]. Удалим из [math]c[/math] добавленные ребра.
Тогда цикл [math]c[/math] распадется на [math]N[/math] путей, которым будут принадлежать все ребра [math]G[/math].
Достаточность
Докажем, что [math]G[/math] нельзя покрыть менее, чем [math]N[/math] реберно-простыми путями.
Предположим, что такое возможно, и существует набор реберно-простых путей [math]p_1, p_2, ... p_k, k \lt N[/math], такой что он покрывает все ребра [math]G[/math].
Пусть [math]i-[/math]й путь из этого набора имеет вид [math] w_i = u[/math][math]i_0[/math] [math] \rightarrow u[/math][math]i_0[/math] [math]u[/math][math]i_1[/math] [math] \rightarrow u[/math][math]i_1[/math] [math] \rightarrow ... \rightarrow u[/math][math]i_l[/math]. Добавим в [math]G[/math] все ребра вида [math]u[/math][math]i_l[/math] [math]u[/math][math](i+1)_0[/math] и ребро [math]u[/math][math]k_l[/math] [math]u[/math][math]1_0[/math]. В новом графе появится Эйлеров цикл. Всего будет добавлено [math]k[/math] ребер, которые изменят четность не более, чем [math]2k[/math] вершин. Т.к. [math]k \lt N[/math], то в графе останутся вершины нечетной степени.
Противоречие. Значит, такого набора, что его мощность меньше [math]N[/math], не существует. |
| [math]\triangleleft[/math] |
См. также
Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
Источники
1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.
