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

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

Следующее утверждение являются следствием из критерия Эйлеровости графа:

Теорема:

Пусть [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]\triangleleft[/math]

См. также

Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов

Источники

1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.