Алгоритм построения дерева-цепочки. Ребро максимальной длины в маршруте. Алгоритм построения матрицы контуров и сечений

1.2.2Алгоритм  построения  дерева-цепочки.

В  ряде  практических  задач  ограничения  на  степени  вершин  дерева  p=2 . В этом  случае  более  эффективным , чем  модифицированный  алгоритм  Прима , является  эвристический  алгоритм , в  котором  строится  замкнутый

маршрут  минимальной  длины , проходящий  через  все  вершины . Затем  из  него  удаляется  ребро  максимальной  длины ; получается  КСД  с    q(x _j)£ 2  " jÎx .

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

 Пусть  полный  граф  G(X,V) , имеющий  n  вершин , задан  матрицей  смежности  D .

M - множество ребер , вошедших  в  маршрут

Шаг1. Выбрать ребро (x _{i* ,}x _j*)  такое ,что d(x _i* ,x _j*)=min d(x _i ,x _j);

                                                                                           i ,jÎ x

            M={(x _i* , x _{j *}),(x _j* ,x _i*)}- начальный  замкнутый  маршрут .

            T={x _{i* ,}x _j*} ; L=2d(x _{i* ,}x _j*)- длина  начального  маршрута .

Шаг2. Выбрать  вершину  x _rÎ x \ T такую , что 

_DL= d(x _i* ,x _r)+ d(x _r  ,x _j*)- d(x _{i* ,}x _j*)=min  min  [d(x _{i ,}x _r)+ d(x _{r ,}x _j)- d(x _i ,x _j)]

                                                    (x _i ,x _j)ÎM; x _rÎx\T

            Включить  x_r  в  дерево : Т=ТÈX_r

            Включить   в  M  вместо  ребра  (x_j* ,x_i*) два  ребра  (x_i* ,x_r),(x_r ,x_j*),

            т.е. M=M\(x_i* ,x_j*) ; M=MÈ(x_i* ,x_r)È(x_r ,x_j*) ;

                                   L=L+DL .

            Если  êT ç=n , то  перейти  к  шагу  3 , иначе  повторить  шаг  2 .

Шаг3. Среди  ребер  (x_i  ,x_j)ÎM  выбрать  такое  (x_i* ,x_j*) , что 

d(x_i* ,x_j*) = max d(x_i ,x_j) .              

                            (x_i ,x_j)ÎM

             Удалить  ребро  (x_i* ,x_j*)  из  маршрута :

                  M=M\(x_i* ,x_j*) ;

                                    L=L-d(x_i* ,x_j*) .

             Полученное  дерево , описываемое  множеством  вершин  Т  и               

             множеством  ребер  М=А , есть  дерево , достаточно  близкое  к                                                     

             КСД .

Пример1.5.  Построение   дерева   для   того   же   графа,  что   и   в 

примере 1.3.  (описываемого  матрицей  D ).

Шаг1.  Выбираем  ребро  минимальной  длины  d(x₂ ,x₄)=d(x₄ ,x₂)=1 .

T={x₂ ,x₄} ;

        M={(x₂ ,x₄) , (x₄ ,x₂)} ;

        T \ x={x₄ ,x₃ ,x₅ ,x₆} .

Шаг2. Итер.1 Удалить  можно  ребро  (x₂ ,x₄).

D L(x₁)=d(x₂ ,x₁)+d(x₁ ,x₄)-d(x₂ ,x₄)=5+2-1=6 ;

D L(x₃)=d(x₂ ,x₃)+d(x₃ ,x₄)-d(x₂ ,x₄)=3+3-1=5 ;

D L(x₅)=d(x₂ ,x₅)+d(x₅ ,x₄)-d(x₂ ,x₄)=8+3-1=10 ;

D L(x₆)=d(x₂ ,x₆)+d(x₆ ,x₄)-d(x₂ ,x₄)=6+4-1=9 ;    

           x_r=x₃ ;T={x₂ ,x₃ ,x₄ } ;M={(x₂ ,x₃) , (x₃ ,x₄) , (x₄ ,x₂)} ; T \ x={x₁ ,x₅ ,x₆} ;

            Итер.2 Удалить  можно  ребра  (x₂ ,x₃)  или  (x₃ ,x₄)  или  (x₄ ,x₂) .

a)   ребро  маршрута  (x₂ ,x₄):

D L(x₁)=d(x₂,x₁)+d(x₁,x₃)-d(x₂,x₃)=5+4-3=6;

D L(x₅)=d(x₂,x₅)+d(x₅,x₃)-d(x₂,x₃)=8+7-3=12;

D L(x₆)=d(x₂,x₆)+d(x₆,x₃)-d(x₂,x₃)=6+9-3=12;

b)   ребро  маршрута  (x₃,x₄):

DL(x₁)=d(x₃,x₁)+d(x₁,x₄)-d(x₃,x₄)=4+2-3=3;

DL(x₅)=d(x₃,x₅)+d(x₅,x₄)-d(x₃,x₄)=7+3-3=7;

DL(x₆)=d(x₃,x₆)+d(x₆,x₄)-d(x₃,x₄)=9+4-3=10;

c)   ребро  маршрута  (x₄,x₂):

DL(x)=2+5-1=6;

DL(x)=3+8-1=10;

DL(x)=4+6-1=9;

       min    min   DL=3;  x_r=x₁;  (x_i*,x_j*)=(x₃,x₄);

  (x_i,x_j)ÎM  rÎx\T

       T={x₁,x₂,x₃,x₄};  M={(x₂,x₃),(x₃,x₁),(x₁,x₄),(x₄,x₂)};  x\T={x₅,x₆}.

 Итер 3. Удалить  можно  ребра  маршрута  (x₂,x₃)  или  (x₃,x₁)  или            (x₁,x₄) или  (x₄,x₂); 

 ребро  (x₂,x₃):  DL(x₅)=8+7-3=12;

DL(x₆)=6+9-3=12;