Итерационные алгоритмы разрезания графа на куски

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

Вспомним, что матрица смежности для графа G(X,E), имеющего n вершин – это матрица R=||r_ij||_n*n, элементы которой соответствуют числу ребер, соединяющих вершину x_i с вершиной x_j.

Т.к. матрица смежности полностью описывает граф, то разрезание графа G на lкусков G₁, G₂, … , G_l эквивалентно разбиению матрицы смежности R графа G на l клеток (подматриц).

Клетки по главной диагонали задают подграфы G_i^’, включающиеся в куски G_i, а остальные клетки определяют наличие ребер между кусками.

За критерий оптимальности можно брать минимум числа ребер между кусками (см. формулу(3.2) лекции 3)

(7.1)

,

либо максимум числа ребер внутри кусков

	(7.2)
или DG → max	(7.3)

(Согласно материалу лекции 3 множество U_ij определяет подмножество ребер U_ij ≤ U, попадающих в разрез между кусками G_i и G_j графа G,а множество U_ii определяет подмножество ребер, т.е. кол-во связей внутри куска G_i),

Разрезание графа будем сводить на каждом шаге к разрезанию графа на два куска. Число вершин первого куска равно числу вершин выделяемого куска, а число вершин второго куска – числу всех оставшихся вершин графа.

Таким образом, в первом куске пусть будет множество Е_i вершин, а во втором ØЕ_i = Е \ Е_i.

Тогда множество ребер разобьем на три класса:

1) внутренние ребра, лежащие в куске;G_i;

2) внешние ребра, лежащие в куске ØG_i;

3) соединяющие ребра между кусками G_i иØG_i.

Число внутренних ребер куска G_i равно

(7.4)

Где Sr(e_i) - сумма локальных степеней вершин куска G_i, K_iØi - число соединительных ребер кусков G_i и ØG_i

Число внешних ребер, которые являются внутренними для куска ØG_i равно

(7.5)

Для каждой вершины e_k введем число связности вершины (разность кол-ва внешних и внутренних связей k-го элемента)

Где:

- r_k(G_i) -число ребер, соединяющих вершину e_k с вершинами куска G_i (k-й элемент, i-й кусок);

- r_k(ØG_i) -число ребер, соединяющих вершину e_k с вершинами куска ØG_i.

Обозначим:

- a_k - число связности для вершин e_kÎE_i;

- Øa_k - число связности для вершин e_kÎØE_i.

Поясним понятие связности на примере графа G, разбитого на 2 части G₁ и G₂, приведенного на рис. 7.1. Тогда числа связности для вершин G₁ определяется следующим образом:

a(x₁)=r₁(G₂)-r₁(G₁)=1-2=-1;

a(x₂)=r₂(G₂)-r₂(G₁)=2-2=0;

a(x₃)=r₃(G₂)-r₃(G₁)=3-2=1;

Числа связности для вершин G₂:

a(x₄)=r₄(G₁)-r₄(G₂)=1-3=-2

a(x₅)=r₅(G₁)-r₅(G₂)=2-2=0;

a(x₆)=r₆(G₁)-r₆(G₂)=0-2=-2;

a(x₇)=r₇(G₁)-r₇(G₂)=3-1=2;

Очевидно, что число связности может быть положительным, отрицательным или равным нулю. Физический смысл числа связности следующий. Например, a(x₁)=-1означает, что при перестановке вершины x₁изG₁вG₂число ребер в сечении увеличится на 1. Значение a(x₂)=0говорит о том, что перестановка вершины x₂ изG₁вG₂ оставит без изменения число соединительных ребер.

Рассмотрим теперь итерационный алгоритм с использованием матрицы смежности. Он основан на теореме:

Перестановка двух произвольных вершин e_kÎE_i и e_qÎØE_i приводит к уменьшению числа соединительных ребер между кусками в случаях:

A) если e_k и e_q не смежные, и выполняется:

Б) если e_k и e_q смежные, и выполняется:

В общем случае

Докажем утверждение А). Очевидно, что перестановка целесообразна, еслиDK_iØi=K_iØi-K^’_iØi>0 (например, было 5 внешних реберных соединений, стало 2), где K_iØiиK^’_iØi- числа внешнего реберного соединения до и после перестановки и

Тогда

Аналогично доказывается утверждение Б).

Теперь опишем суть алгоритма

1. Разрезание начинаем выделением в матрицеR двух произвольных подматриц Q и ØQ. Порядок подматрицы Qравен числу вершин первого выделяемого куска, а порядок ØQ - числу всех оставшихся вершин.

2. Перестановка элементов из одного куска в другой будет соответствовать перестановке строк и столбцов матрицы R.

3. Сумма всех элементов подматрицы главной диагонали (деленная на два) соответствует числу внутренних ребер, а элементы, не принадлежащие главной диагонали, определяют соединяющие ребра между кусками. Тогда

	(7.13)
	(7.14)

Для каждой строки матрицы смежности подсчитываем a_k или Øa_q в зависимости от того, к какой подматрице принадлежит данная строка. Запишем эти числа справа матрицы.

4. Построим матрицу В =||b_kq||_ni*(n-ni),в которой строки определяются вершинами e_kÎE_i, а столбцы вершинами e_qÎØE_i. На пресечении k– ой строки и q – го столбца элемент

гдеr_kq - элемент матрицы R.

Элемент b_kq характеризует изменение числа соединительных ребер между кусками G_i и ØG_i при перестановке вершинe_kÎG_i и e_qÎØG_i.

Выбираем для перестановки пару с наибольшим положительным b_kq.

5. Осуществляется перестановка строк и столбцов k и q в матрице R и процесс снова повторяется пока в матрице Bвсе элементы не станут со знаком «-».

6. Исключается из графа Gкусок G₁, соответствующий подматрице Q₁ и процесс повторяется для матрицы ØQ₁ с выделением куска с n2 элементами и т. д.

Пример.

Задана матрица смежности R₀ графа G. Надо разрезать граф с рис. 7.1 на 3куска по 5, 3, 4 вершин

Согласно п.1 алгоритма выделяем в матрице R₀ две подматрицы, в одной из которых 5 строк, т.е. включаем в первый кусок элементы e₁, e₂, e₃, e₄, e₅ (т.к. разбиваем на куски по 5, 3, 4 вершин), в оставшейся части 7строк.

Согласно п.3 алгоритма для каждой строки матрицы смежности по формулам (7.13) и (7.14) подсчитываем a_k и Øa_k и записываем в столбец справа от матрицы смежности. Число соединительных ребер между G₁ и ØG₁ (число внешних связей) для этого разбиения K1=14 (сумма элементов выделенной части)

Согласно п.4 алгоритма по формуле (7.15) построим матрицу В. Для примера:

b₁₆= a₁+Øa₅-2r₁₆=4+1-2*0=5

b₄₁₁= a₄+Øa₁₁-2r₄₁₁=1-4-2*0=-3

Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b₁₆=5, т.е. из B₀ выбираем для перестановки элементы e₁ и e₆.

Согласно п.5 алгоритма в матрице R₀ переставляем строчки и столбцы, соответствующие e₁ и e₆ и смотрим, как изменится число внешних связей между кусками от этой перестановки.

Получается матрица R₁

Число соединительных ребер между G₁ и ØG₁ (число внешних связей) для этого разбиения K2=9 (сумма элементов выделенной части).

Число соединительных ребер между G₁ и ØG₁снизилось с 14 до 9, т.е. перестановка элементов e₁ и e₆ дает уменьшение числа соединительных ребер. Переход к п.4.

Согласно п.4 по формуле (7.15) строим матрицу В₁:

Согласно п.4 алгоритма выбираем для перестановки пару с наибольшим положительным b₃₁₀=5, т.е. из B₁ выбираем для перестановки элементы e₃ и e₁₀.

В матрице R₁ переставляем строчки и столбцы, соответствующие e₃ и e₁₀.

Число соединительных ребер между G₁ и ØG₁ снизилось до 4.

Согласно п.5 алгоритма т.к. в R^’₂ все значения α_ки α_qотрицательные, то в В₂ не будет положительных элементов, и процесс выделения подграфа G₁закончен,

E₁={e₆,e₂,e₁₀,e₄,e₅}

Строим кусок E₂, содержащий 3 вершиныВключаем в него элементы e₁, e₇, e₈.Согласно п.6 алгоритма, исключив из R^’₂ кусок, соответствующий G1, получим:

Строим матрицу B^’’₀:

Выбираем max b₈₉=6. Из B^’’₀ выбираем для перестановки элементы e₈ и e₉. В матрице R^’’₀ переставляем строчки и столбцы, соответствующие e₈ и e₉:

Число соединительных ребер между G₂и ØG₂снизилось с 7 до 1, т.е. перестановка элементов e₈ и e₉ дает уменьшение числа соединительных ребер.

Т.к. все α_ки α_q отрицательные, то в В^’’₁ все члены будут со знаком «–» и перестановки не может быть. Тогда

E₂={e₁,e₇,e₉}, E₃={e₈,e₃,e₁₁,e₁₂}.

Число соединительных ребер между кусками =5.

Число внутренних ребер равно 9+5+7=21.

∆(G)=21/5=4,2.

Результат разбиения приведен на рис. 7.2.

Оглавление

Лекция 7. 1

Итерационные алгоритмы разрезания графа на куски. 1