Последовательный алгоритм компоновки с равными числу вершин в каждом куске

 

 

 

 

=

 

 

 

 

 

 

2) Выделяем третью запрещенную  вершину.

G3 = {X15}

3) Для вершины x_i ϵ Г(x_v) определяем относительные веса 

δ (x_v) = ρ(x_i)-   

где ρ(x_i) – локальная степень вершины x_i , ρ(x_i) = _; – число ребер, соединяющих вершину x_i с вершинами x_j , вошедшими в G3;

m – число вершин G3 на текущем шаге работы алгоритма. Переход к п.4.

Г (X15) = {X12}

4) Выбираем вершину Xs , для которой   ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(x_i). Переход к п.5.

δ (X12) = 3 min         b1215 = 1

5) Полученную вершину  Xs помещаем в кусок G3: G3={ x_v x_s }. Переход к п.6.

Xs = X12

6) Подсчитываем число n₃ вершин в куске G3. Если n₃ < n, где n  - заданное число вершин в каждом куске, то переход к п.8.

G3 = { X15, X12 }

8) Добавляем в список  Г(x_v) вершины, смежные вершинам, вошедшим в кусок G3. Переход к п.3.

Г (X15, X12) = { X8, X11, X13}

Переход к пункту № 3

3) Для вершины x_i ϵ Г(x_v) определяем относительные веса 

δ (x_v) = ρ(x_i)-   

где ρ(x_i) – локальная степень вершины x_i , ρ(x_i) = _; – число ребер, соединяющих вершину x_i с вершинами x_j , вошедшими в G3;

m – число вершин G3 на текущем шаге работы алгоритма. Переход к п.4.

Г (X15, X12) = { X8, X11, X13}

4) Выбираем вершину Xs , для которой   ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(x_i). Переход к п.5.

         δ (X8) = 6                       b1215 = 1

    δ (X11) = 2 min             b1215 = 1

    δ (X13) = 3                     b1215 = 1

5) Полученную вершину  Xs помещаем в кусок G3: G3={ x_v x_s }. Переход к п.6.

Xs = X11

6) Подсчитываем число  n₃ вершин в куске G3. Если n₃ < n, где n  - заданное число вершин в каждом куске, то переход к п.8.

G3 = { X15, X12, X11 }, т.к.  n_t < n

8) Добавляем в список  Г(x_v) вершины, смежные вершинам, вошедшим в кусок G3. Переход к п.3.

Г (X15, X12, X11) = { X8, X13}

     Переход к пункту № 3

3) Для вершины x_i ϵ Г(x_v) определяем относительные веса 

δ (x_v) = ρ(x_i)-   

где ρ(x_i) – локальная степень вершины x_i , ρ(x_i) = _; – число ребер, соединяющих вершину x_i с вершинами x_j , вошедшими в G3;

m – число вершин G3 на текущем шаге работы алгоритма. Переход к п.4.

Г (X15, X12, X11) = { X8, X13}

4) Выбираем вершину Xs , для которой   ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(x_i). Переход к п.5.

         δ (X8) = 5                       b1215 = 2

         δ (X13) = 2 min             b1215 = 2

5) Полученную вершину  Xs помещаем в кусок G3: G3={ x_v x_s }. Переход к п.6.

 Xs = X13

6) Подсчитываем число  n₃ вершин в куске G3. Если n₃ < n, где n  - заданное число вершин в каждом куске, то переход к п.8.

G3 = { X15, X12, X11, X13 }

7) Если n₃ = n, кусок G1 сформирован, тогда переход к п.9.

n₃ = n

     Переход к  пункту №9

9) Удаляем из матрицы  A строки и столбцы, соответствующие  номерам вершин, вошедших в кусок  G3. Для формирования следующего  куска G4, начиная со следующей  запрещенной вершины, процедура  повторяется с п.2. Если сформирован  последний кусок, переход к  п.10.

Удаляем из матрицы A { X15, X12, X11, X13 }

Оставшиеся вершины X4, X5, X8, X9 автоматически войдут в последний кусок. 

10) Конец работы алгоритма.