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

5. Полученную вершину х_s помещаем в кусок G₁: G₁={x_, x_s}. Переход к п.6.

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

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

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

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

10. Конец работы алгоритма. Задания для курсовой работы Задание 3

Последовательный алгоритм разбиения графа G=(X,E) на  кусков

G1, …g с числом вершин n1,…n в каждом куске. Замечание. Формирования g1 начинаем с вершины с наибольшей локальной степенью.

1. Вычисление матрицы смежности .

2. Определение локальной степени каждой вершины .

3. Выбор строки в матрице смежности, соответствующей вершине x_s наибольшей локальной степенью. Если max , то x_sG_1. x_iX _.

4. Формирование массива Г(х_s) вершин, смежных вершине х_s, причем х_s Г(х_s). Переход к п.5.

5. Если количество вершин n_t в списке Г(х_s) равно n₁ , то первый кусок сформирован и G₁= Г(х_s). Переход к п.8, иначе к п.6.

6. Если n_tn₁, то из множества вершины, не вошедших в список Г(х_s), выбирается вершина x_j, удовлетворяющая условию

,

где a(x_j) – число связей вершины x_j c x_i вершинами из списка Г(х_s). Если таких вершин несколько, то берется вершина с большим значением и добавляется в список Г(х_s). Переход к п.5.

7. Если n_t >n₁, то из списка Г(х_s) удаляются лишние вершины, то есть связанные с остающимися в куске G₁ меньшим числом ребер b(x_j).

8. Исключение из графа G куска G₁, то есть удаление из матрицы смежности С строк и столбцов, соответствующих номерам вершин из Г(х_s). Пересчет локальных степеней оставшихся вершин.

9. Если число сформированных кусков m<-1, то повторение алгоритма для формирования следующего куска с п.3. Если m=-1, то переход к п.10.

10. Конец работы алгоритма. Задания для курсовой работы Задание 4

Последовательный алгоритм разбиения графа G=(X,E)

На  кусков g1,…g с учетом запрещенных вершин.

Замечание. Дан список Q запрещенных вершин. Каждая вершина из Q жестко закрепляется за отдельным куском, причем в каждом куске может находиться не более одной вершины из списка Q. Формирование куска начинается с запрещенной вершины. Число вершин в куске равно ).

Алгоритм.

1. Вычисляем матрицу смежности .

2. Вычисляем локальную степень вершин .

3. Выделяем первую запрещенную вершину . Её помещаем в первый кусок: . Составляем список Г(х_) вершин, смежных х_.

4. Определяем для вершин x_iГ(x_) относительные веса. (x_i)=(x_i)-a_ij, где a_ij – число ребер, соединяющих вершину x_i c вошедшими вершинами x_j в кусок G₁; m – число вершин x_j в G₁ на текущем шаге работы алгоритма.

5. Выбираем вершину x_s с наименьшим относительным весом (x_s) = min (x_i). Если таких вершин несколько, то берем вершину x_i Г(x_), для которой (x_s) = max (x_i).