Покрытие графа непересекающимися по ребрам цепями

Количество таких цепей равно k /2, где k – количество вершин с нечетными степенями, оно всегда четно.

Если k = 2, то получается эйлерова цепь.

Если граф не удовлетворяет условиям Эйлера, то для нахождения покрытия графа непересекающимися по ребрам цепями надо дополнить граф до эйлерова графа, построить эйлеров цикл, а затем удалить введенные ребра (и вершины). Если граф эйлеров, то просто строим эйлеров цикл или эйлерову цепь.

Для преобразования графа в эйлеров граф можно:

1) продублировать все ребра (дуги) графа, или

2) добавить фиктивную вершину и соединить ее ребрами с вершинами, имеющими нечетную степень; таких вершин четное число, поэтому степень введеной вершины будет четной и, следовательно, все вершины будут удовлетворять условиям Эйлера, или

3) разбить множество вершин с нечетными степенями на пары и соединить вершины каждой пары ребром или маршрутом кратчайшей длины.