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

Материал из Викиконспекты
Версия от 23:34, 13 октября 2010; Alexey.tsyplenkov (обсуждение | вклад) (Покрытие ребер графа путями)
Перейти к: навигация, поиск

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

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

Утверждение:
Пусть [math]G[/math] - почти связный граф, в котором [math]2N[/math] вершин имеют нечетную степень. Тогда множество ребер [math]G[/math] можно покрыть [math]N[/math] реберно простыми путями.

См. также

Источники

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