Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 29 стр.

                                     29

               12.2.2. Стандартный алгоритм (2-ой вариант)

  1) В графе G матрицы А ищем ППВ u.
  2) Строим СУС L0, L1,..., Ln с корнем в вершине u.
  3) Определяем m = [q/(n+1)], где q – порядок матрицы, n – длина построен-
     ной в 2) СУС.
                         n 2 
  4) Определяем k =           .
                          3 m 
  5) Если расстояние δ = [(n+1)/(k+1)] между разделителями меньше [n/2]
     и q>50, то перейдем к шагу 8) (т.е. применение МПС нецелесообразно).
  6) Положим i = 1 и S = ∅.
      6.1) Положим j = iδ. Если j ≥n, то перейдем к шагу 7), иначе продолжим
           вычисления.
      6.2) Пусть Si – множество всех вершин уровня Lj, смежных с вершинами
           из Lj+1.
      6.3) S = S ∪ Si.
       6.4) i = i+1 и перейдем к 6.1).
  7) Найдем p связных компонент R1, R2, ... , Rp, образовавшихся после удале-
      ния из графа вершин множества S (значение p может отличаться от (k+1),
      т.к. получившееся разбиение графа может иметь большее число блоков).
  8) Пронумеруем вершины каждого множества Rk (k = 1,...,p), используя об-
      ратный алгоритм Катхилл-Макки для каждого из частичных графов.
  9) Пронумеровать вершины множества S произвольным образом.

Задача 51. Реализовать МПС (2-ой вариант) для графа G из задачи 46.
  1) v = 8 – периферийная вершина.
  2) СУС для вершины v = 8 построена в задаче 46: n = 6.
            20 
  3) m =           =2 .
           6 +  1 
          6 2 
  4) k =            =3 .
             3 ⋅ 2 
          6 +1 
  5) δ =           =1 , q <50 .
           3 + 1  
  6) i = 1: S = ∅;

        6.1) j = 1:
        6.2) S1 = {9; 19};
        6.3) S = {9; 19};
        6.4) i = 2:

                6.1) j = 2: