Линейный алгоритм перестройки графа

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