Page 71 - 4386

утворювати ліс у графі G , то знову повернутися до початку
і
даного кроку. Якщо ні, то перейти до кроку 2.

Крок 2. Оскільки додавання до множини E дуги e приводить
і
до того, що дуги з множини E перестають утворювати ліс в графі
і
G , то дуга e, у сукупності з деякими іншими дугами з E , утворює
і
і
контур. Позначити такий контур через С .
і
Виявивши контур С , стягнути всі дуги та вершини контуру
і
С в одну вершину, яку позначити v . Одержаний у результаті
і
і
такого стягування граф, вважати графом G . Таким чином, будь-
і+1
яка дуга в графі G , інцидентна в точності одній вершині контуру
і
C , буде інцидентна вершині v у графі G , а вершинами графа
і
і+1
і
G , крім вершини v , є всі вершини графа G , що не входять у
і
i
і+1
контур C .
і
Для всіх дуг графа G , за винятком тих, які заходять у
і+1
вершину v , залишити ваги такими ж, якими вони були в графі G .
і
і
Для кожної дуги (х, у) графа G , що переходить у графі G у дугу
і+1
і
(х, v ), розрахувати нову вагу:
і
с(х, v )=с(х, у)+с(r, s)-с(t, у), (6.1)
і
де (r, s) – дуга, що має в контурі C мінімальну вагу; (t, у) –
і
дуга контуру C , що заходить у вершину у.
і
Сформувати множину V , включивши в неї всі вершини
i+l
графа G , які були в V (таким чином, V містить усі вершини V ,
i+l
i
i
і+1
що не входять у контур C ). Сформувати множину E ,
і+1
і
включивши в неї всі дуги графа G , які були в E (таким чином,
і
і+1
E містить усі дуги E , що не входять у контур C ).
і
і+1
і
Збільшити і на одиницю та перейти до кроку 1.
Крок 3. Даний крок виконується тільки тоді, коли всі
вершини графа G входять у множину V , а дуги з множини E
i
і
і
утворюють в графі G орієнтований ліс.
і
70